Quantum computation of discrete logarithms in semigroups

DOI10.1515/JMC-2013-0038zbMATH Open1304.68050arXiv1310.6238OpenAlexW1971243765MaRDI QIDQ490342FDOQ490342

Authors: Andrew M. Childs, Gábor Ivanyos 

Publication date: 22 January 2015

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Abstract: We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and discrete log 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 log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $kge2$ generators in a black-box abelian semigroup of order $N$ requires $ildeTheta(N^{frac12-frac12k})$ quantum queries.

Full work available at URL: https://arxiv.org/abs/1310.6238

Recommendations

• A reduction of semigroup DLP to classic DLP
• Quantum algorithm for discrete logarithm problem for matrices over finite group rings
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• scientific article; zbMATH DE number 1304334
• Quantum algorithm for solving hyperelliptic curve discrete logarithm problem

zbMATH Keywords

discrete logarithmquantum algorithmssemigroupssemigroup actionsconstructive membershiphidden shift problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cited In (16)

• Discrete quantum computation and Lagrange's four-square theorem
• DLP in semigroups: algorithms and lower bounds
• Individual attacks with generalized discrimination and inadequacy of some information measures
• Computing primitive idempotents in finite commutative rings and applications
• Quantum algorithms for typical hard problems: a perspective of cryptanalysis
• Semidirect product key exchange: the state of play
• A deterministic algorithm for the discrete logarithm problem in a semigroup
• Survey on SAP and its application in public-key cryptography
• A reduction of semigroup DLP to classic DLP
• Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem
• Cryptanalysis of Some Protocols Using Matrices over Group Rings
• EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability
• Quantum algorithm for discrete logarithm problem for matrices over finite group rings

This page was built for publication: Quantum computation of discrete logarithms in semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490342)