Paper 2013/707

A reduction of Semigroup DLP to classic DLP

Matan Banin and Boaz Tsaban

Abstract

We present a polynomial-time reduction of the discrete logarithm problem in any periodic (or torsion) semigroup (SGDLP) to the classic DLP 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 complexity whenever the classic DLP in the corresponding groups has subexponential complexity. We also consider several natural constructions of nonperiodic semigroups, and provide polynomial time solutions for the DLP in these semigroups.

Note: To appear in Designs Codes and Cryptography

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problemquantum algorithmssemigroups.
Contact author(s)
tsaban @ math biu ac il
History
2015-11-02: last of 2 revisions
2013-11-03: received
See all versions
Short URL
https://ia.cr/2013/707
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/707,
      author = {Matan Banin and Boaz Tsaban},
      title = {A reduction of Semigroup DLP to classic DLP},
      howpublished = {Cryptology ePrint Archive, Paper 2013/707},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/707}},
      url = {https://eprint.iacr.org/2013/707}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.