The Discrete Logarithm Problem in non-representable rings

Matan Banin; Boaz Tsaban

Paper 2012/320

The Discrete Logarithm Problem in non-representable rings

Matan Banin and Boaz Tsaban

Abstract

Bergman's Ring $E_{p}$ , parameterized by a prime number $p$ , is a ring with $p^{5}$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_{p}$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems. We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in to the classical Discrete Logarithm Problem in , the -element field. In particular, the Discrete Logarithm Problem in can be solved, by conventional computers, in sub-exponential time. Along the way, we collect a number of useful basic reductions for the toolbox of discrete logarithm solvers.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Discrete Logarithm Problem Bergman Ring Linear Representation
Contact author(s): tsaban @ math biu ac il
History: 2012-06-12: received
Short URL: https://ia.cr/2012/320
License: CC BY

BibTeX

@misc{cryptoeprint:2012/320,
      author = {Matan Banin and Boaz Tsaban},
      title = {The Discrete Logarithm Problem in non-representable rings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/320},
      year = {2012},
      url = {https://eprint.iacr.org/2012/320}
}