In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The public-key cryptosystems, including RSA, ElGamal, ECC and the related variants, play an ingredient role in securing the confidential communication over the Internet during the past decades. The fundamental principle of designing a secure public-key cryptosystem is to lay its security on the difficulty of certain mathematical problems. For instances, RSA [1] builds up its security on the hardness of integer factorization problem (IFP), and the security of ElGamal and ECC [2] is based on the difficulty of solving the discrete logarithm problem (DLP) and the DLP over elliptic curves (ECDLP), respectively. Even with the system parameters well optimized, the classical algorithms ever known, such as those toward IFP, DLP and ECDLP, are no longer efficient to our problem, as the resource required would grow in a sub-exponential manner over the scale of the problem.
Quantum computing is an interdisciplinary subject between quantum mechanics and computer science. Shor’s algorithm [3] and Grover’s quantum search algorithm [4] are the two most widely used quantum algorithms at present. Shor’s algorithm is applied to solve large integer factorization problem and discrete logarithm problem. Grover’s quantum search algorithm is adopted to search a number of specific targets in a disordered database. Both of them are of great significance in the perspective of cryptanalysis. Shor’s quantum algorithm manifests a serious threat toward the security of RSA, ElGamal and ECC, since both the IFP problem and the DLP problem (including the ECDLP problem) can be solved efficiently with Shor’s quantum algorithms. Grover’s quantum algorithm is also used to speed up the task of collision finding. Therefore, to secure confidential communication in the so-called post-quantum era, some new public-key cryptosystems, which aim at resisting known quantum algorithmic attacks, appear on the stage of the modern cryptography. NIST launched the competition on post-quantum cryptography in 2016, and 26 outstanding designs have been selected for the second round evaluation so far.
Advertisement
As one of the most well-developed branches of post-quantum cryptography, lattice cryptography enjoys a high implementation efficiency and strong security reductions. In particular, Regev built the connection between the hardness of lattice problems and the hardness of the dihedral subgroup problem in 2002 [5]. However, at present, our confidence toward lattice cryptography is based merely on a heuristic reduction from the hardness of certain lattice problem to the hardness of certain quantum difficult problem, while the reverse reduction required by the logic framework of provable security is still open. Recently, Wen et al. made the first breakthrough toward building such kind of reverse reduction. Therefore, from the perspective of cryptanalysis, it is interesting to made a survey on quantum algorithms for classical hard problems, including lattice problems, IFP, DLP, ECDLP, as well as other related variants.
The rest of the paper is organized as follows: In Sect. 2, we reviewed quantum Fourier transform, for understanding quantum algorithms mentioned in this survey. The background for basis of qubit, quantum gates and quantum circuits is not involved in this work, since we believe it can be found in other textbooks on quantum computations, such as [6, 7]. In Sect. 3, we summarized the quantum algorithms for period findings, which helps to understand why some symmetric cipher, such as RC6, tends to be insecure in the post-quantum era. Quantum algorithms for factoring integers, including Shor’s algorithm based on quantum circuit model and Jiang’s algorithm based on quantum adiabatic model, are summarized in Sect. 4. This is a key to understand why public-key cryptosystems based on difficulty of IFP are no longer secure. In Sect. 5, we explored the quantum algorithms for the DLP problem and their variants over elliptic curves, matrices of group rings, etc. This tell us why ElGamal, ECC as well the related variants are secure when large-scale quantum computers are available. Then, in Sects. 6 and 7, we introduced quantum algorithms for the hidden subgroup problem and the hidden shift problems, respectively, as two common frameworks of designs quantum algorithm. In Sect. 8, we presented quantum algorithms for the dihedral subgroup problem and its relation with lattice problems, in order to understand the potential of lattice cryptography in resisting known quantum attacks. Finally, we conclude the paper in Sect. 9.
2 Quantum Fourier transform
The quantum Fourier transform (QFT), with exponential speedup compared to the classical fast Fourier transform, has played an important role in quantum computation as a vital part of many quantum algorithms [8]. The QFT over \({\mathbb {Z}}_N\), the group of integers modulo N under addition, is a unitary operator \(F_{\mathbb {Z}_N}\) that effects on a basis state as follows:
Further, we can derive QFT over any finite abelian group G. We know that any finite abelian group G can be expressed as a direct product of cyclic subgroups of prime power orders \(G\cong {\mathbb {Z}}_{p_1}\times \cdots \times {\mathbb {Z}}_{p_r}\). Thus, in this case the QFT over G is the quantum operator \(F_G= F_{p_1}\otimes \cdots \otimes F_{p_r}\).
Without loss of generality, assuming \(n=\lceil \log N\rceil \), then the circuit of QFT over \({\mathbb {Z}}_N\), as depicted in Fig. 1, can be implemented exactly by using \(\frac{n(n-1)}{2}\) of controlled rotation gates, plus with n Hadamard gates, leading to the gate complexity \(O(n^2)\). Recently, Su et al. [9] suggested that QFT over n-qubits can be approximate with \(O(n\log n)\) T-gates.
Fig. 1
The circuit of quantum Fourier transform [10]. \({\left| {\varphi _{0}}\right\rangle },\ldots ,{\left| {\varphi _{n-1}}\right\rangle }\) are input bits, and \({\left| {z_{0}}\right\rangle },\ldots ,{\left| {z_{n-1}}\right\rangle }\) are output bits. \(R_{n}\) is two-bit quantum controlled rotation
×
Advertisement
3 Quantum algorithms for finding periods
A function over the domain \(\mathcal {D}\) is called periodic if there is a unique and smallest \(r>0\) (called period) so that \(f(x)=f(x+r)\) holds for every \(x\in \mathcal {D}\). Say, the sine and cosine functions, respectively, have periods \(2\pi \) and \(\pi \) over \({\mathbb {R}}\). Although this definition does not require r to be integer and \(\mathcal {D}\) to be discrete, for the problems discussed in this survey, we only consider the settings of r being a positive integer and \(\mathcal {D}\) being a discrete ring, say \({\mathbb {Z}}\) or \({\mathbb {Z}}_n\) (for some \(n\in {\mathbb {N}}\)). Intuitively, without any other heuristic information on f, say regarding f as a black box, any classical algorithm for determining whether f has a period r needs to evaluate f on, in the worse case, all elements in \(\mathcal {D}\), leading to the time complexity \(\mathcal {O}(|\mathcal {D}|)\) and space complexity \(\mathcal {O}(1)\).
However, quantum computers can work exponentially faster than any classical computers toward the period finding problem. The first breakthrough on this issue can be traced back to the landmark work due to Simon [11]. Simon’s algorithm is not only the first algorithm that represents a substantial advance in relativized time complexity vs. classical computing, but also a turning point in the development of quantum computation technology considering that it contains the key ingredients of the relevant algorithms that follow, including the notably Shor’s quantum algorithm for integer factoring problem [7]. Very recently, Dong [12] proposed indistinguishable attack and key-recover attack toward one of the well-known cipher structure—the extended Feistel structures, including the typical block ciphers such as CAST256 and RC6.
Simon’s algorithm is proposed to deal with the following problem [13]: Given a Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}^n\) that satisfies the so-called Simon commitment condition
the objective is to find \(s\in \{0,1\}^n\). Considering that \(\oplus \) is the addition over binary field, the Simon’s commitment condition is equivalent to that f has period r over \({\mathbb {Z}}_2^n\). Now, suppose that a quantum circuit \(U_f\) for implementing \({\left| {x}\right\rangle }{\left| {0}\right\rangle }\rightarrow {\left| {x}\right\rangle }{\left| {f(x)}\right\rangle }\) is at hand, then the Simon’s algorithm is depicted in Fig. 2, and a modified version due to Mosca consists of the following eight steps [13]:
Fig. 2
The circuit of Simon’s algorithm [13]. \(H^{\otimes n}\) is n-bit Hadamard gate
Step 1 Initializing two registers with 2n qubit states
Step 6 Measure the first register to obtain a string \(y_{i}\in \{0,1 \}^{n}\), and \(y_{i}\) can be viewed as a n dimension vector \(\mathbf {y_{i}}\).
Step 7 If \(i=n\) , go to the next step; otherwise, let \(i\leftarrow i+1\) and go to Step 2.
Step 8 Let \(M=[y_1,\ldots ,y_n]\). Then, M is invertible with high probability. Now, we can solve the system \(M\cdot s=0\) to get s, say by using the well-known classical Gaussian elimination algorithm.
To summary, the above description of Simon’s algorithm requires O(n) quantum operators over 2n qubits, plus a classical post-processing with time complexity \(O(n^3)\).
×
4 Quantum algorithms for factoring integer
The integer factorization problem (IFP) is given an integer N, output prime numbers p, q, where \(N=pq\) . It is an important problem in number theory and has attracted significant attention due to its importance in data encryption [14]. For example, the IFP is used as the basic hardness assumption for RSA cryptosystem. Up to now, the most effective classical algorithm for solving IFP is the general number field sieve [15], while the number of operations required still grows sub-exponentially with the bit length of the integer to be factorized. Quantum computing can effectively reduce the complexity of solving certain problems, and it has attracted much attention in recent years [6]. Some tested quantum computing platforms are already available, such as cloud quantum computers from IBM [16, 17] based on nuclear magnetic resonance (NMR) [18] and D-Wave’s quantum annealing system.
Researchers are currently focusing on two main research directions to solve the IFP via quantum computing: Shor’s quantum factoring algorithm and quantum adiabatic computing (QAC).
4.1 Shor’s integer factorization algorithm
It is a challenge to implement Shor’s algorithm [19], since it is founded on the quantum circuit model. Vandersypen et al. [20] used a molecule with seven spin-1/2 nuclei to factor 15, yet the experiments cannot be applied to a larger number. Martín-López et al. [21] re-utilized qubits to factor 21 with Shor’s algorithm by adopting an iterative protocol. Geller et al. [22] employed Fermat numbers and eight qubits to factor 51 and 85, which are the largest numbers to be factored by Shor’s algorithm so far. According to Gidney [23], there should be \(2k+1\) qubits to factor k-bit integers.
From the perspective of universal quantum computation, there is still a long way to go before it could be practical.
Shor’s algorithm [3] transforms the problem of factoring a given number N into an equivalent problem: Given a random positive integer a , where \(a<N\), \(\gcd (a,N)=1\), find the order r of a, i.e., \(a^{r}\equiv 1\pmod N\). Then, p and q can be find by Euclidean algorithm. Suppose \(t=\lceil \log N\rceil \) and a quantum circuit \(U_f\) for implementing \(|x\rangle |0\rangle \rightarrow |x\rangle |a^{x}\bmod N\rangle \) is at hand, then the Shor’s algorithm consists of the following seven steps:
Step 1 Initialize two t-qubit registers as follows:
Step 6 Measure the first register; we can observe the value \(\lfloor \frac{kN}{r}\rceil \) with a probability no less than \(\frac{4}{\pi ^2r}\).
Step 7 Finally, the period r can be derived by using the classical continued fraction expansion (CFE) method in polynomial time [10].
During the past decades, there are many attempts to implement Shor’s algorithm over different quantum prototype computers. The number of qubits and quantum gate complexities needed for these implementations is summarized in Table 1.
Table 1
Different implementations of Shor’s algorithms, comparison of the number of qubits and quantum gate needed
4.2 Factorization by using quantum adiabatic computing
Another promising method for integer factorization is QAC [29‐31], which was put forward by Burges [32, 33] at first. QAC is being used on the IFP mainly in two ways: (1) NMR [18, 34, 35] and (2) quantum annealing leveraging the D-Wave system [36]. D-Wave’s quantum computing system is playing a more important role than ever [33]. Although it is the strength of the NMR on long coherence time, high-accuracy quantum control, as well as NMR can be effective implementation on Grover’s algorithm [37] using QAC [31, 38]. D-Wave’s superconducting quantum computer is standing out in terms of the number of qubits. Wang et al. [39] suggested that quantum annealing could potentially be applied to cryptanalysis, representing them to combinational optimization problems to be mapped to the D-Wave machine’s theoretical model. Li et al. [40] applied both theoretical reductions and Hamiltonian transformations to successfully factor 291311, while Jiang et al. [41] recently proposed a generalized quadratic unconstrained binary optimization (QUBO) model, which is used to represent the multiplication table and the model is able to factor 376298 with 94 qubits. Wang et al. [33] optimize the problem Hamiltonian to reduce the number of qubits involved in the final Hamiltonian while maintaining the QUBO coefficients in a reasonable range, enabling the improved algorithm to factorize larger integers with fewer qubits. This algorithm using D-Wave’s hybrid quantum/classical simulator qbsolv confirmed that performance was improved; it can factorize 1,005,973 with only 89 qubits, a new record for quantum factorized integers.
A quantum system remains in its instantaneous eigenstate if the system Hamiltonian varies slowly enough and if there is a gap between this eigenvalue and the rest of the Hamiltonian’s spectrum [35]. It has been proved to be equivalent to the conventional circuit model. A quantum computer algorithm can be viewed as a specification of a Hamiltonian H(t) and an initial state \(|\psi (0)\rangle \).
The time-dependent Hamiltonian of the quantum system is
Wang et al. improve the algorithm of Jiang et al. [41]. To compute the number of carry variables every column block needs, they use the target value, maximum carry and prodf function values for the column blocks to reduce the number of carry variables needed. They replace \(p_{1}\) and \(p_{2}\) with \(q_{1}\) or \(1-q_{1}\) and \(q_{2}\) or \(1-q_{2}\), respectively, thus further decreasing the number of qubits needed for the final QUBO model. Take \(N=143\) as an example; the algorithm steps are as follows:
Step 4 Replace \(p_{1}q_{1}\), \(p_{1}q_{2}\), \(p_{2}q_{2}\) and \(p_{2}q_{1}\) with \(t_{1}\), \(t_{2}\), \(t_{3}\) and \(t_{4}\), respectively. Further, rename the variables \(p_1,p_2,q_1,q_2,c_1,\ldots ,c_4,t_1,\ldots ,t_4\) as \(v_1,\ldots ,v_12\), and replace \(v_{i}=\frac{1-s_{i}}{2}\) (\(i=1,\ldots ,12\)) to make the variables lie in the domain \(\{-1,1\}\). Now, the above cost function f can be rewritten as
Step 5 Now, we can review the above cost function as an Ising Hamiltonian with local fields, and the values of \(h_i\) and \(J_{ij}\) can be derived accordingly (See Fig. 3 for details).
Step 6 Solve the Ising Hamiltonian system by calling qbsolv, the Python library provided by D-Wave systems, and map the results back to the prime factorization of N.
Fig. 3
Ising Hamiltonian system for factoring 143
×
To summary, the qubits needed for different implementations of quantum factorization based on QAC are shown in Table 3.
Table 3
Different implementations of quantum factorization based on QAC
Comparison of the largest integer can be factorized
5 Quantum algorithms for discrete logarithmic problems
Let \(G=\langle g \rangle \) be a cyclic group of order p and g be a generator of G. The discrete logarithmic problem (DLP) over G is to find an integer r such that \(g^r=y\) for given \(y\in G\). Diffie–Hellman key exchange protocol, ElGamal encryption and most elliptic curve cryptosystems are based on the difficulty of computing discrete logarithms. At present, the best known classical algorithm for solving DLP is the so-called index-calculate method (ICM) that requires sub-exponential classical operations.
In 1994, Shor [3] put forward a polynomial time quantum algorithm to solve the discrete logarithmic problem in group. Proos et al. [42] further extended Shor’s quantum DLP algorithm to elliptic curves [42‐44]. In 2012, Myasnikov et al. proposed a quantum algorithm for the DLP over matrices of finite group rings [45]. Childs [46] described an effective quantum algorithm for computing discrete logarithms over semigroups. Recently, further generalized Shor’s quantum DLP algorithms are proposed for different algebraic structures [47‐50].
With the identity \(g^r=y\), if we define a binary function \(f:{\mathbb {Z}}_{p-1}\times {\mathbb {Z}}_{p-1}\rightarrow {\mathbb {Z}}_p\) as follows:
is at hand, then Shor’s discrete logarithm algorithm is depicted in Fig. 4. A modified version of Shor’s quantum DLP algorithm, due to Wang [51], consists of the following six steps:
Step 6 Measure the first two registers to get \({\left| {u_0}\right\rangle }{\left| {ru_0}\right\rangle }\), and then, derive r by \(r=ru_{0}u_{0}^{-1}\bmod (p-1)\) (assuming that \(\gcd (u_0,p-1)=1\) with high probability).
The complexities of Shor’s quantum DLP algorithm and some related algorithms are collected in Table 4.
The comparison of time and space complexities is in table
6 Quantum algorithms for abelian hidden subgroup problems
Let H be the subgroup of group G, S be any set and \(f : G \rightarrow S\) a function that distinguishes cosets of H, i.e., \(\forall g_{1}, g_{2} \in G, f (g_{1}) = f (g_{2}) \Leftrightarrow g_{1}H = g_{2} H\). The hidden subgroup problem (HSP) is to find the subgroup H using f. To solve this problem classically, \(\Omega (|G|)\) queries on f are required, while it is solvable on a quantum computer using merely \(O(\log |G|)\)f-queries.
In 1995, Kitaev [52] gave a polynomial quantum algorithms to solve the abelian stabilizer problem (ASP) and prove that the integer factorization and discrete logarithm problems can be solved as special cases. In 1995, Dan and Lipton [53] first built the relationship between quantum algorithm and HSP and designed a quantum algorithm to solve the hidden linear function. In 1997, Brassard and Hoyer [54] extended the Simon’s problem to HSP. In 1998, Jozsa [55] gave a unified description of Deustch–Jozsa’s algorithm, Simon’s algorithm and Shor’s algorithm in the form of HSP. Subsequently, Mosca [56, 57] and Jozsa [58] introduced the more general abelian HSP and gave quantum Fourier transform to solve it. Abelian HSP mainly focuses on finite abelian groups, and related algorithms can be seen in [57, 59].
The algorithm of general finite abelian HSP rewrote by Damgard [60] consists of the following six steps:
where \(\sum _{h\in H} \chi _{g}(h)=0\) if and only if \(g\notin H^{\perp }\).
Othogonal subgroup \(H^{\perp }\) defined as \(H^{\perp }=\{ g\in G|\chi _{g}(h)=1,\quad \forall h\in H \}\). \(|\varphi _{4}\rangle \) can be further simplied to
Step 6 Measure the first register, and we can obtain \(H^{\perp }\); then, H can be obtained by \(H=(H^{\perp })^{\perp }\).
7 Quantum algorithms for hidden shift problems
Given a finite group G, a finite set R and two maps \(f,g: G\rightarrow R\), the hidden shift problem is to find some \(s\in G\) such that \(f(x) = g(x+s)\) for all \(x\in G\). At least \(\sqrt{N}\) queries are necessary for hidden shift problem by reduction from Grover’s problem. However, on quantum computer, only \(\mathcal {O}(1)\) queries can solve certain special cases of hidden shift problems. The hidden shift problem was first introduced and studied by van Dam et al. [61, 62] in 2003. The shifted Legendre symbol algorithm [63, 64] is classified as this special case, and no classical algorithm in \(\mathcal {O}(\hbox {polylog}N)\) time has been found to solve these problems. In addition, the shifted Legendre symbol problem’s quantum algorithm will destroy the specific cryptographic pseudorandom generator and it has the ability to make quantum queries to the generator [62]. There has a connection between the hidden shift problem and the hidden subgroup problem, hidden subgroup problem over dihedral group is equivalent to the hidden shift problem over \(\mathbb {Z}_{N}\), and graph isomorphism can be cast as a hidden shift problem over \(S_{n}\) [10‐12]. The study of the hidden shift problem can give an arguably more natural view to tackle the graph isomorphism problem [12]. Based on the “pretty good measurement,” Childs et al. [65] proposed a quantum algorithm for the generalized hidden shift problem: \(f\in \mathbb {Z}_{M}\times \mathbb {Z}_{N}\) satisfying \(f(b,x) = f(b+1,x+s)\) for \(b\in {\mathbb {Z}}_M\) and \(x,s\in {\mathbb {Z}}_N\). In 2010, Roetteler [66] gave an efficient quantum algorithm for solving the hidden shift problem for several classes of the so-called bent functions. Gavinsky et al. [67] gave an efficient quantum algorithm for solving the hidden shift problem for the average case Boolean functions in 2001. Ozols et al. [68] gave another quantum algorithm for the Boolean hidden shift problem based on a quantum analogue of the rejection sampling.
The quantum algorithm for a generalized hidden shift problem by Childs is as follows:
Then, the hidden shift s can be identified using the pretty good measurement with at least a constant probability [65].
8 Quantum algorithms for dihedral hidden subgroup problems and lattice problems
The dihedral group is a symmetric group generated by the reflection and rotation. It contains 2N elements:
$$\begin{aligned} D_{N}=\langle s , r |s^{2}=r^{N}=1,srs =r^{-1}\rangle \end{aligned}$$
where s can be viewed as a reflection about some fixed axis, and r is a rotation by an angle \(\frac{2\pi }{N}\). Moreover, \(D_N\) is isomorphic to a semidirect product of the two cyclic groups \({\mathbb {Z}}_2\) and \({\mathbb {Z}}_N\) of order 2 and N, respectively,
The homomorphism \(\phi : {\mathbb {Z}}_2\rightarrow \mathrm {Aut}({\mathbb {Z}}_N)\) is specified by
$$\begin{aligned} \phi (0)(b)=b,\quad \text{ and }\quad \phi (1)(b)=-b. \end{aligned}$$
An element \((a,b)\in D_N\) is a rotation if \(a = 0\), and a reflection if \(a = 1\) [69]. Now, let us consider a hidden subgroup \(H=\{(0,0),(1,d)\}\) for some unknown \(d\in {\mathbb {Z}}_N\). That is, H is the subgroup group generated by an unknown reflection \(r=(1,d)\). The dihedral hidden subgroup problem (dHSP) with respect to H is to find d. This problem is also formulated quantum as the so-called dihedral coset problem (DCP): Given many superpositions \(\{ \frac{1}{\sqrt{2}}(|0,x_{i}\rangle + |1,x_{i}+d\rangle ): x_i\in {\mathbb {Z}}_N \}_{i\le \ell }\) (i.e., the coset of H), the objective is to find d.
In 1998, Ettingcr and Hoyer [69] were the first to study dihedral hidden subgroup problems (dHSP). They divided the dihedral group into two subgroups of rotation and reflection and searched for the hidden subgroups of each subgroup, respectively. They claimed that it is enough to solve dHSP if the generator of the hidden subgroup of the reflected subgroup is known. In 2002, Regev [5] found the connection between the unique shortest vector problem (uSVP) and dHSP and pointed out that if dHSP can be effectively solved, the unique shortest vector problem of lattice can also be effectively solved. Kuperberg [76] first proposed a sub-exponential quantum algorithm of dHSP. In 2004, Regev [5] abstracted Kuperberg’s sieve method as a pipeline, reducing the quantum space complexity of the original algorithm to polynomial level, but the time complexity is still sub-exponential. In 2011, Kuperberg [76] improved the original algorithm and Regev’s polynomial space algorithm and proposed another sub-exponential quantum algorithm of dHSP. The time complexity of the improved algorithm is slightly reduced, but in the worst case, the algorithm is Regev’s algorithm. In 2016, Roetteler [71] first raised a quantum algorithm that can solve a special type of dHSP problem in polynomial time and space complexities: When \(N=2^{m}-1\), more than \(\mathcal {O}(2^{m^{2}})\) instances are easy to solve among dHSP problem on the dihedral group \(D_{N}\) , that is, the total number of easily solved instances increases exponentially with m.
In recent years, significant progress has been made in lattice-based cryptography among the post-quantum public-key cryptography. Many lattice-based public-key encryption schemes have been proposed in light of the fact that some lattice problems [72‐74] such as unique shortest vector problem (uSVP) are the foundation of the trapdoor one-way function. However, uSVP can be reduced to a kind of non-abelian hidden subgroup problem [5]: the dihedral hidden subgroup problem. Therefore, the study on quantum algorithm for the dihedral hidden subgroup problem has great significance for the security of lattice-based cryptography.
8.1 Kuperberg’s quantum algorithm for dHSP
In 2003, Kuperberg [76] reduced the dHSP to finding the slope d when \(N=2^n\) and \(H = \langle (1,d)\rangle \). Suppose the black box \(f: D_N\rightarrow R\) for hidden H is given and \(U_f\) (i.e., the quantum circuit for implement f) is at hand, where R is the range of f. That is, f on each coset of H is constant. Now, a quantum algorithm for determining the parity of d, due to Kuperberg, is depicted in Fig. 5 [51] and described as the following eight steps:
Fig. 5
Determining the parity of d [51]. \(F_{N}\) is Fourier transform, and H is Hadamard gate
Step 5 Measure the first register, ignore the global phase \(e^{\frac{2\pi iz_{0}x}{2^n}}\) and the first register, and the second register collapses to
Step 8 Measure the second register. If 0 is observed, d is even; otherwise, d is odd.
After the parity (i.e., the least significant bit) of d is found, Kuperberg suggested to use the sieving idea to find all bits of d iteratively. The following steps are Kuperberg’s sieve idea, reformulated by Regev [5].
When d is even. Then, consider the black box \(f': D_{N/2}\rightarrow R\) given by \(f(a, b) := f(a, 2b)\). Note that this function hides the subgroup \(H'=\langle (1, d')\rangle \) of \(D_{N/2}\) with \(d'=d/2\).
When d is odd. Then, consider the black box \(f'': D_{N/2}\rightarrow R\) given by \(f(a, b) := f(a, 2b+1)\). Note that this function hides the subgroup \(H''=\langle (1, d'')\rangle \) of \(D_{N/2}\) with \(d''=(d-1)/2\).
We can now obtain the second least significant bit of d (i.e., the parity of \(d'\) or \(d''\)) by calling the above algorithm with either \(f'\) or \(f''\) [5]. By continuing this process iteratively, we can find all the bits of d (Table 5).
Given \(m \ge n\) samples of the form \((a,b)\in \mathbb {Z}_{q}^{n}\times \mathbb {Z}_{q}\), with \(a\leftarrow \mathbb {Z}_{q}^{n}\) and \(b=\langle a,s \rangle +e\), where \(e\leftarrow D_{\mathbb {Z},\alpha q}\) and \( s\in _{R} \mathbb {Z}_{q}^{n}\), the learning with errors (LWE) problem is to find the secret vector s. The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal.
In 2005, Regev [75] first proposed the LWE problem and proved that the LWE problem is difficult under proper assumptions. Since then, this problem has proved to be as difficult as the worst-case lattice problem, which has become the basis of a large number of encryption applications in recent years.
Regev [5] showed that uSVP and, therefore, also BDD and LWE are no harder to solve than the DCP problem. The best known algorithm for DCP, due to Kuperberg [76], runs in time\(2^{O(\log l+\log N/ \log l)} \)which does not improve upon classical methods for solving LWE. Regev showed that DCP can be solved given efficient algorithms for the subset-sum problem (which is classically defined), however in a regime of parameters that appear harder to solve than LWE itself. In 2013, Li et al. [77] present a quantum algorithm to generate the input of the two-point problem which hides the solution of LWE; then they give a new reduction from two-point problem to dihedral coset problem. Their reduction implicates that any algorithm solved DCP in sub-exponential time would lead a quantum algorithm for LWE. In 2016, Eldar and Shor [78] proposed a quantum algorithm to solve the bounded-distance-decoding (BDD) problem on lattice and claimed that some parameters of the algorithm could be improved to attack the cryptographic system based on the LWE problem. Although the algorithm found has problem later [78], the technique of “smoothing” analysis of lattices by using systematic normal form (SysNF) provided a new idea for the direct solution of lattices. Subsequently, they systematically explained how to use SysNF technology to effectively carry out discrete Fourier transform [79] (DFT) in the any distribution that is sufficiently ”smooth” of any lattice, which provided a new possible approach for analyzing lattice point structure based on DFT eigenvector and solving SVP equilateral lattice problem.
In 2018, Brakerski et al. [80] show the equivalence between LWE and the extrapolated dihedral coset problem (EDCP) by building quantum reductions between them. The EDCP problem over \(D_N\) is specified as follows: Given \(\ell \) many registers in a normalized state corresponding to
where \(x_i\in \mathbb {Z}_{N}^{n}\) (\(i=1,\ldots ,\ell \)), and \(s\in \mathbb {Z}_{N}^{n}\) is fixed, the objective of EDCP is to find the secret value s.
(1) Quantum reduction from LWE to EDCP.
An instance of LWE problem over the lattice \(\mathcal {L}(A)\), \(A\in {\mathbb {Z}}_q^{m\times n}\), can be reduced to an instance of EDCP problem over the dihedral group \(D_N\), \(N=2^n\), according to the following quantum steps (Fig. 6):
Fig. 6
From LWE to EDCP [80]. GR02 is the algorithm in [81], \(F_{Z_{q}^{n}}\) is Fourier transform over \(Z_{q}^{n}\), and \(U_{g}\) is an unitary transformation. The output state is \(U_\mathrm{{EDCP}}\)
Step 1 Initialize the four registers with required qubits
Step 3 Apply GR02 algorithm [81] in the first register, which is a quantum process to create a superposition state according to given probability distribution
With the rapid development of quantum computing, it broke through the defense line of the classic cryptosystems, which makes the post-quantum cryptography become the frontier of research. In order to search the novel cryptography which is resistant to quantum attack, it is of great necessity to conduct a systematical analysis of the quantum algorithms that could solve the typical hard problems. In this paper, we start from the typical hard problems: integer factorization problem, discrete logarithmic problem and dihedral hidden subgroup problems in the public-key cryptosystem (respectively, RSA, ElGamal, ECC); then, we analyze the latest development of quantum algorithms; besides, the limitation of typical cryptosystem (RSA, ElGamal, ECC) and its vulnerability to quantum attacks, as well as the explanation to the resistance of lattice cryptography to quantum attacks are all elaborated. For future research, analyzing the isogeny, multivariable and seeking for the quantum algorithms for problems such as hash collision should be of guiding significance.
Acknowledgements
This work was supported by the National Key Research and Development Program of China (2018YFE0126000), the National Natural Science Foundation of China (NSFC) (No. 61972050), the Shandong provincial Key R&D Program of China (Grant No. 2018CXGC0701) and the 111 Project (No. B08004).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
