nach oben

Designs, Codes and Cryptography

Erschienen in:

01.10.2016

A reduction of Semigroup DLP to classic DLP

verfasst von: Matan Banin, Boaz Tsaban

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2016

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present a polynomial-time reduction of the discrete logarithm problem (DLP) in any periodic (or torsion) semigroup (Semigroup DLP) to the classic DLP in a subgroup of the same semigroup. It follows that Semigroup DLP can be solved in polynomial time by quantum computers, and that Semigroup DLP 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.

Vorheriger Artikel Policy-based signature scheme from lattices

Nächster Artikel homomorphic hash functions: worst case to average case reduction and short collision search

The nonperiodic case is discussed briefly in Sect. 3 below.

It does not matter whether we first minimize l and then n, or vice versa.

Koblitz N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987).

Miller V.: Use of elliptic curves in cryptography. In: Advances in Cryptology—CRYPTO’85 Proceedings. Springer, Berlin (1986).

Odoni R., Varadharajan V., Sanders P.: Public key distribution in matrix rings. Electron. Lett. 20, 386–387 (1984).

Menezes A., Wu Y.: The discrete logarithm problem in GL\((n, q)\). Ars Comb. 47, 23–32 (1997).

Kahrobaei D., Koupparis C., Shpilrain V.: Public key exchange using matrices over group rings. Groups Complex. Cryptol. 5, 97–115 (2013).

McCurley K.: The discrete logarithm problem. In: Proceedings of Symposia in Appplied Mathematics, vol. 42, pp. 49–74. American Mathematical Society, Providence (1989).

Myasnikov A., Ushakov A.: Quantum algorithm for discrete logarithm problem for matrices over finite group rings. Groups Complex. Cryptol. 6, 31–36 (2014).

Childs A., Ivanyos G.: Quantum computation of discrete logarithms in semigroups. J. Math. Cryptol. 8, 405–416 (2014).

Bach E., Shallit J.: Algorithmic number theory. In: Efficient Algorithms. MIT Press Series in the Foundations of Computing, vol. I. Cambridge (1996).

10.

Shoup V.: Lower bounds for discrete logarithms and related problems. In: Advances in Cryptology—EUROCRYPT 97. Lecture Notes in Computer Science, vol. 1233, pp. 256–266, Springer, Berlin (1997).

Titel: A reduction of Semigroup DLP to classic DLP
verfasst von: Matan Banin
Boaz Tsaban
Publikationsdatum: 01.10.2016
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2016
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-015-0130-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2016

A note on relative hemisystems of Hermitian generalised quadrangles

New infinite series of 2-designs over the binary and ternary field

Two classes of cyclic codes and their weight enumerator

homomorphic hash functions: worst case to average case reduction and short collision search

A generalization of Kung’s theorem

Policy-based signature scheme from lattices