At EUROCRYPT 2006, the Nostradamus attack was originally proposed by Kelsey and Kohno, a cryptographic vulnerability in which a hash value y can be pre-determined by an adversary and a suffix S can later be fabricated such that H(P‖S) = y for a priori unknown prefix P. Their attack framework was shown to achieve a time complexity of O(n⋅22n/3), with n denoting the hash function’s output bit-length. At ASIACRYPT 2022, a quantum variant of the Nostradamus attack was introduced by Benedikt et al., and the time complexity was reduced from O(n⋅22n/3) to O(3n⋅23n/7). In ToSC 2023, the first dedicated Nostradamus attack targeting AES-like hash functions was proposed by Zhang et al., and subsequently at ToSC 2024 the meet-in-the-middle attack framework was improved by Dong et al., resulting in enhanced attack results. In this paper, a more efficient algorithm for constructing diamond structures is proposed. By designing an unbalanced diamond structure shaped as an unbalanced binary tree, the time complexity of the offline phase is reduced from O(3k⋅2(n+2k)/3) to O(2(n + 2k)/3) in the qRAM setting, where k represents the height of the diamond structure. In detail, the time complexity of the quantum Nostradamus attack is improved from O(3n⋅23n/7) to O(23n/7). Furthermore, this new offline structure is applied to the MITM Nostradamus attack targeting AES-MMO, yielding lower time complexity results in the qRAM setting.
This paper investigates a novel approach to cryptography analysis leveraging the principles of quantum error correction codes (QECCs). The core idea centers on exploiting the inherent redundancy and error-correcting capabilities of QECCs to analyze and potentially compromise cryptographic keys. Traditional cryptographic attacks often rely on brute-force, differential, or linear cryptanalysis. This work proposes a fundamentally different methodology, focusing on the structure and properties of QECCs to induce errors within the encoded key, which can then be exploited for decryption. The methodology involves constructing specific QECCs tailored to the cryptographic algorithm being analyzed, and then manipulating the encoding process to introduce vulnerabilities. The effectiveness of this approach is demonstrated through theoretical analysis and the development of a novel attack strategy. While experimental validation is not included in this paper, the presented framework provides a strong theoretical foundation and a promising direction for future research in quantum-resistant cryptography. The ultimate goal is to significantly enhance the security of cryptographic systems by targeting their underlying error correction mechanisms.
ABSTRACT Shallow nitrogen vacancy (NV) centers with long coherence times are promising candidates for applications in areas such as quantum computing and quantum sensing. However, as the NVs are only a few nanometers below the diamond's surface, it is a challenge to remove the different decoherence sources related to the surface, e.g., charge fluctuations and magnetic impurities. Here, the effect of ozone treatment on the chemical composition of diamond surfaces was correlated with its impact on the spin properties of the same individual shallow NV (depth < 20 nm) by comparing its coherence times, Ramsey and Hahn Echo (T 2 ), before and after the treatment. X‐ray photoelectron spectroscopy (XPS) shows a reduction in sp 2 bonds, and it was reported that an enhancement of the coherence times up to a factor of 3. Additionally, we investigate the effects of Ozone treatment on random single NVs engineered to have a depth of ∼30 nm, where an enhancement up to a factor of 10 on and up to a factor of 3 on T 2 have been observed.