A reduction of Semigroup DLP to classic DLP

Matan Banin; Boaz Tsaban

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 problem quantum algorithms semigroups.
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: 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},
      url = {https://eprint.iacr.org/2013/707}
}