A reduction of semigroup DLP to classic DLP
From MaRDI portal
Publication:306053
DOI10.1007/S10623-015-0130-2zbMATH Open1379.94029arXiv1310.7903OpenAlexW2125635884MaRDI QIDQ306053FDOQ306053
Publication date: 31 August 2016
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Abstract: We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion) semigroup (SGDLP) to the same problem in a subgroup of the same semigroup. It follows that SGDLP can be solved in polynomial time by quantum computers, and that SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.
Full work available at URL: https://arxiv.org/abs/1310.7903
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Elliptic Curve Cryptosystems
- Quantum algorithm for discrete logarithm problem for matrices over finite group rings
- Public key exchange using matrices over group rings
- Quantum computation of discrete logarithms in semigroups
Cited In (7)
- DLP in semigroups: algorithms and lower bounds
- An extension of the noncommutative Bergman's ring with a large number of noninvertible elements
- 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
- Reduction of the semigroup-action problem on a module to the hidden-subgroup problem
- Cryptanalysis of Some Protocols Using Matrices over Group Rings
This page was built for publication: A reduction of semigroup DLP to classic DLP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306053)
