Abstract Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon’s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.
Abstract Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon’s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.
Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, we first propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition and construct their specific quantum circuits. Unlike previous related works, our quantum algorithms are universal. Specifically, the two quantum algorithms can both compute the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled with other registers and keep the data qubits unchanged. On this basis, we apply the two quantum algorithms as a subroutine to parallel Simon's algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm, respectively. Afterwards, we construct a quantum classifier within Grover Meets Simon algorithm and the test oracle within Alg-PolyQ2 algorithm in detail, including their respective quantum circuits. To our knowledge, no such specific analysis has been done before. We rigorously analyze the success probability of those algorithms to ensure that the success probability based on the proposed quantum algorithms will not be lower than that of those original algorithms. Finally, we discuss the lower bound of the number of CNOT gates for solving quantum linear systems of equations with coherent superposition, and our quantum algorithms reach the optimum in terms of minimizing the number of CNOT gates. Furthermore, our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers, within the effective working time of an ion trap quantum computer.
Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.
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.
Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.
A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.
Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that Ax=b. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state |x⟩ corresponding to the solution of the linear system of equations in O(κ2rpolylog(mn)/ϵ) time for a general m×n dimensional A, which is superior to existing quantum algorithms, where κ is the condition number, r is the rank of matrix A and ϵ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.