Quantum computation of discrete logarithms in semigroups

DOI10.1515/JMC-2013-0038MaRDI QIDQ490342zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Gábor Ivanyos

Publication date 22 January 2015

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1310.6238, http://eprints.sztaki.hu/7931/

zbMATH Keywords

constructive membershipdiscrete logarithmhidden shift problemquantum algorithmssemigroup actionssemigroups

Mathematics Subject Classification ID

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

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.

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

Cited in

(20)

• Survey on SAP and its application in public-key cryptography
• Quantum algorithms for computing general discrete logarithms and orders with tradeoffs
• DLP in semigroups: algorithms and lower bounds
• Individual attacks with generalized discrimination and inadequacy of some information measures
• A deterministic algorithm for the discrete logarithm problem in a semigroup
• On post-processing in the quantum algorithm for computing short discrete logarithms
• Quantum algorithm for discrete logarithm problem for matrices over finite group rings
• Quantum algorithms for typical hard problems: a perspective of cryptanalysis
• Discrete quantum computation and Lagrange's four-square theorem
• A reduction of semigroup DLP to classic DLP
• EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
• Cryptanalysis of some protocols using matrices over group rings
• Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability
• Computing primitive idempotents in finite commutative rings and applications
• Semidirect product key exchange: the state of play
• 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
• On the classical hardness of the semidirect discrete logarithm problem in finite groups
• On the semidirect discrete logarithm problem in finite groups
• A subexponential quantum algorithm for the semidirect discrete logarithm problem

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)