In quantum cryptanalysis, Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problem, and elliptic curve discrete logarithm problems, widely used in cryptographic applications in cyberspace. Shor's quantum algorithm can potentially crack most protocols and schemes of asymmetric encryption (public key cryptography). In general, all known quantum algorithms can be divided into two groups: providing exponential gain (for example, Shor's algorithm) and providing quadratic gain (for example, Grover's algorithm). Particular attention is paid to the Shor quantum algorithm and other polynomial algorithms capable of solving cryptanalysis problems with the required reliability and complexity in polynomial time. For quantum computing, all cryptographies are divided into quantum-secure and quantum-insecure. Algorithms and cryptosystems of symmetric encryption are attributed to quantum-secure but with at least twice the key length increased. This chapter presents an overview of the concepts discussed in the subsequent chapters of this book.
Abstract The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup
G⋊End(G) G⋊End(G) for a finite semigroupG. Given
g∈G,σ∈End(G) g∈G,σ∈End(G) , and
h=∏i=0t−1σi(g) h=∏i=0t-1σi(g) for some integert, the SDLP
(G,σ) (G,σ) , forgandh, asks to determinet. As Shor’s algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. For generic semigroups, the best known algorithm for the SDLP is based on Kuperberg’s subexponential time quantum algorithm. Still, the problem plays a central role in the security of certain proposed cryptosystems in the family ofsemidirect product key exchange. This includes a recently proposed signature protocol called SPDH-Sign. In this paper, we show that the SDLP is even easier in some important special cases. Specifically, for a finite groupG, we describe quantum algorithms for the SDLP in
G⋊Aut(G) G⋊Aut(G) for the following two classes of instances: the first one is whenGis solvable and the second is whenGis a matrix group and a power of
σ σ with a polynomially small exponent is an inner automorphism ofG. We further extend the results to groups composed of factors from these classes. A consequence is that SPDH-Sign and similar cryptosystems whose security assumption is based on the presumed hardness of the SDLP in the cases described above are insecure against quantum attacks. The quantum ingredients we rely on are not new: these are Shor’s factoring and discrete logarithm algorithms and well-known generalizations.
We survey the computational assumptions of various cryptographic schemes, and discuss the security threat posed by Shor's quantum algorithm. One-way functions form the basis of public-key cryptography. Although we have candidate hard problems that are believed to be one-way, none has been proven to be so. Therefore the security of the corresponding cryptographic schemes depends on the intractability assumptions of these problems. Two major species of such problems, factoring and discrete logarithm, are widely believed to be intractable, and serve as the basis of many popular schemes. However, these two problems turned out to be polynomial-time solvable on a hypothetical quantum computer using Shor's algorithm. This is the most worrisome long-term threat to current public-key cryptosystems. In the thesis we provide a review of existing cryptosystems, with a focus on their underlying computational assumptions and the security. Other than factoring and discrete logarithm, schemes have been proposed based on error-correcting codes, subset-sum and subset-product problems, lattice, polynomials, combinatorial group theory, number fields, etc. Many are to be furtherly evaluated in future research.