“Simon's Algorithm: Collision Finding” explains Simon's Algorithm, focusing on how it helps in finding collisions. It starts with an overview of how the algorithm works. A literature review is included, covering both Simon's algorithm and its uses in cryptography. The section then introduces Simon's problem, comparing how classical and quantum methods solve it, and explains how to build a quantum circuit for a blackbox function. Different examples of blackbox functions (oracles) are shown, such as 1-to-1 and 2-to-1 mappings, with detailed implementations of Simon's algorithm for both 4-bit and 8-bit cases. The section also looks at a suggested attack method on the Grain-128a cipher, explaining how the key and initialization vector (IV) are set up, how the keystream is generated, and how the authenticated tag is created. It provides a quantum circuit design for the Simon attack on Grain-4a, along with steps for carrying out the attack. The section also presents experimental results from several test cases and quantum resource estimates. It wraps up with a discussion of the results and thoughts on future improvements and developments in using Simon's algorithm for cryptographic attacks.
“Simon's Algorithm: Collision Finding” explains Simon's Algorithm, focusing on how it helps in finding collisions. It starts with an overview of how the algorithm works. A literature review is included, covering both Simon's algorithm and its uses in cryptography. The section then introduces Simon's problem, comparing how classical and quantum methods solve it, and explains how to build a quantum circuit for a blackbox function. Different examples of blackbox functions (oracles) are shown, such as 1-to-1 and 2-to-1 mappings, with detailed implementations of Simon's algorithm for both 4-bit and 8-bit cases. The section also looks at a suggested attack method on the Grain-128a cipher, explaining how the key and initialization vector (IV) are set up, how the keystream is generated, and how the authenticated tag is created. It provides a quantum circuit design for the Simon attack on Grain-4a, along with steps for carrying out the attack. The section also presents experimental results from several test cases and quantum resource estimates. It wraps up with a discussion of the results and thoughts on future improvements and developments in using Simon's algorithm for cryptographic attacks.
“Grover's Algorithm: Quantum Search” explores Grover's Algorithm in the context of quantum search, beginning with an overview of its mechanics. The section includes a literature survey that covers Grover's algorithm, stream ciphers, and the Grover attack, as well as quantum resource estimation. The section then introduces a simplified 4-bit Grain cipher (with a 4-bit key and 4-bit IV), detailing its design, initialization, and key stream generation. Following this, the chapter discusses about key recovery using Grover's algorithm, with an emphasis on quantum circuit development for the simplified Grain 4-bit cipher. It outlines key steps in the circuit, such as executing the Boolean function and XORing the NFSR's fourth bit. Further, the section details the development of a Grover attack quantum circuit, describing both single and double pair methods. Experimental results are provided across multiple cases, with a summary of test cases and classical computation times. Quantum resource estimation, including the costs associated with the simplified Grain 4-bit cipher and the Grover oracle, is analyzed. The section concludes with a discussion on the results, classical and quantum resource estimations, and the potential for future enhancements to the approach.
We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon’s algorithm can be used to show insecurity of commonly used cryptographic symmetric-key primitives. Specifically, these examples consist of a quantum distinguisher for the 3-round Feistel network and a forgery attack on CBC-MAC which forges a tag for a chosen-prefix message querying only other messages (of the same length). We assume that an adversary has quantum-oracle access to the respective classical primitives. Similar results have been achieved recently in independent work by Kaplan et al. [KLLNP16]. Our findings shed new light on the post-quantum security of cryptographic schemes and underline that classical security proofs of cryptographic constructions need to be revisited in light of quantum attackers.
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.
Simon's algorithm is one of the most widely used quantum algorithms in cryptanalysis of symmetric ciphers, which has a significant advantage over its classical counterparts. However, if the number of unwanted collisions of the target function is large or if the number of adversary's quantum superposition queries is limited, the Simon's algorithm is not able to unambiguously compute the actual period. This problem can lead to the failure of period-finding-based quantum attacks. In this paper we first show that using Simon's algorithm, one can find proper partial periods of Boolean vector functions, such that the corresponding probabilities, independent of the target function, are directly related to the number of quantum queries. Next, we examine how to use the partial period instead of actual one in quantum period-finding-based attacks. As a result, the advantage of our proposed relaxing method is twofold: It improves success probabilities of quantum period-finding-based distinguishers, provided that the adversary is limited to a specified small number of queries, in contrast to the previous ones. On the other hand, our proposed method generalizes the previous forgery attacks on modes of operation for message authentication codes.
Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.
In this paper, we proposed a simplified version of the Grain-128 stream cipher and developed a corresponding quantum circuit. Leveraging Grover's algorithm, we demonstrate the ability to recover a key given plaintext, initialization vector (IV), and corresponding ciphertext through various methods, including single pair, double pair series, and double pair parallel approaches. Using the Qiskit Quantum Development Kit (QDK), we conduct these attacks and estimate the required quantum resources. Our research reveals that the simplified grain cipher is vulnerable to quantum attacks, showing how quantum computing could affect cryptographic systems.