Abstract We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order p 3 {p}^{3} and exponent p 2 {p}^{2} for certain exponentially large parameters. This implies an attack on SPDH-Sign, Pronounced “SPUD-Sign”. a signature scheme based on the SDLP, for such parameters. In particular, SDLP instances over such groups are parameterised by an n < ( p − 1 ) p 6 n\lt \left(p-1){p}^{6} : we develop a method to solve instances when n ≤ poly ( log p ) ⋅ p n\le {\rm{poly}}\left(\log p)\hspace{0.25em}\cdot p . Letting λ \lambda be the security parameter of SPDH-Sign, which is taken p = exp λ p=\exp \lambda , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large p p . However, for n ≈ p 2 n\approx {p}^{2} and larger, our method no longer completely solves the SDLP instances. We also study the linear hidden shift problem for a group action corresponding to SDLP and take a step towards proving the quantum polynomial time equivalence of SDLP and the semidirect computational Diffie–Hellman problem.
Abstract We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order p 3 {p}^{3} and exponent p 2 {p}^{2} for certain exponentially large parameters. This implies an attack on SPDH-Sign, Pronounced “SPUD-Sign”. a signature scheme based on the SDLP, for such parameters. In particular, SDLP instances over such groups are parameterised by an n < ( p − 1 ) p 6 n\lt \left(p-1){p}^{6} : we develop a method to solve instances when n ≤ poly ( log p ) ⋅ p n\le {\rm{poly}}\left(\log p)\hspace{0.25em}\cdot p . Letting λ \lambda be the security parameter of SPDH-Sign, which is taken p = exp λ p=\exp \lambda , we find we may solve instances of SDLP corresponding to SPDH-Sign instances with exponentially large p p . However, for n ≈ p 2 n\approx {p}^{2} and larger, our method no longer completely solves the SDLP instances. We also study the linear hidden shift problem for a group action corresponding to SDLP and take a step towards proving the quantum polynomial time equivalence of SDLP and the semidirect computational Diffie–Hellman problem.
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.
Abstract. We propose a polynomial time quantum algorithm for solving the discrete logarithm problem in matrices over finite group rings. The hardness of this problem was recently employed in the design of a key-exchange protocol proposed by D. Kahrobaei, C. Koupparis, and V. Shpilrain [4]. Our result implies that the Kahrobaei et al. protocol does not belong to the realm of post-quantum cryptography. Keywords and phrases: Group-based cryptography, semidirect product, matrix monoids, group-rings, Diffie-Hellman, key-exchange, discrete logarithm problem, quantum algorithms, post-quantum cryptography.
Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively.
In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form G=A⋊φZpk, with A finite Abelian, p prime, k∈N and the action of Zpk is generated by the scalar automorphism a↦μa, for some μ∈ZExp(A)×, where Exp(A) is the exponent of A. Our algorithm is efficient when A has bounded generator rank and Exp(A)/p=polylog(∣G∣). This includes the case A=ZN for N∈N and k=1, studied by Bacon, Childs and van Dam (FOCS 2005), and A=Zqr with q prime and r∈N studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).
The security of popular public key-cryptographic protocols, such as RSA, Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA), is endangered by the advent of quantum computers. Shor brought a big breakthrough with his quantum algorithm that can be used to factor an arbitrarily large integer into the product of its prime factors, hence jeopardizing the security of RSA, and that at the same time also solves the Discrete Logarithm Problem, which raises issues for certain Diffie-Hellman based cryptosystems and digital signatures. It is hence crucial to upgrade our current tools for post-quantum cryptography: it should be infeasible, even using quantum algorithms, to break the new cryptosystems. Popular candidates include for example elliptic curve or lattice-based cryptography, but they share something in common: they are specific cases of the more general Hidden Subgroup and connected Hidden Shift Problem.
This thesis contains a collection of efficient quantum algorithms and classical pre- and post-processing algorithms for various number- and group-theoretical problems with concrete cryptanalytical applications. More specifically, the focus is on the integer factoring problem (IFP), the discrete logarithm problem (DLP), and the order-finding problem (OFP), and on certain important variations of these problems. It is for example explained how the OFP and complete IFP may be solved efficiently in a single run of a reduced version of Shor's algorithm for the OFP with very high success probability, as evidenced by a lower bound that is 1 − o(1), how the short DLP in groups of unknown order may be solved efficiently and with an advantage over Shor's algorithm for the DLP (that furthermore requires the order to be known), as evidenced by a lower bound on the single-run success probability that is 1 − o(1), how the RSA IFP may be solved efficiently and with an advantage over Shor's algorithm for the IFP, by reducing the RSA IFP to a short DLP, how the DLP may heuristically be solved efficiently, and with high success probability that is 1 − o(1), in a single run of a reduced version of Shor’s algorithm for the DLP that admits efficient implementation, how the DLP may be solved in groups of unknown order, such as Schnorr groups, by jointly solving an OFP and a DLP at lower overall cost but higher per-run cost compared to first solving the OFP and then the DLP, how tradeoffs — between the number of group operations that are evaluated quantumly and the number of runs that are required — may be achieved in all of the aforementioned algorithms, and how all of the aforementioned algorithms may be simulated efficiently classically, for arbitrary large cryptographically relevant problem instances, when the solution to the instance is known, enabling the number of runs required when performing tradeoffs to be tightly estimated. It is furthermore for example explained how Regev's recent quantum algorithm for the IFP may be extended to the DLP and OFP, yielding i) a reduction in the circuit size and depth by a factor compared to Shor for these problems when working in , for N an n-bit integer, at the expense of performing runs, and ii) slight improvements of Regev's orginal algorithm for the IFP, how the above algorithms may be simulated efficiently classically, for large special-form problem instances that are classically tractable, and that Regev’s post-processing, and the post-processing for our extensions, are robust to an arbitrarily large fraction < 1 of the runs being bad. The above has implications for cryptography based on the intractability of the IFP and DLP — including but not limited to for widely used schemes such as RSA, DSA and Diffie–Hellman. The algorithms in this thesis are all derived from, and make notable improvements to, the seminal works of Shor. Some of the contributions are joint works with other authors.
Abstract We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete logarithm problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete logarithm problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to k ≥ 2 generators in a black-box abelian semigroup of order N requires Θ ˜ ( N 1 2 - 1 2 k ) Θ~(N21−2k1) quantum queries.