Paper 2021/1701

Cryptanalysis of the Cryptosystems Based on the Generalized Hidden Discrete Logarithm Problem

Ma Yanlong

Abstract

The hidden discrete logarithm problem(HDLP) over non-commutative associative algebras (FNAAs) in [1] was broken in [8] by reducing to discrete logarithm problem(DLP) in a finite field through analyzing the eigenvalues of the representation matrix. A generalized form of HDLP(GHDLP) was proposed in [11], which is claimed to be computationally hard under quantum computers. Based on this, several schemes are proposed. In this paper, we will show that GHDLP can also be reduced to DLP in a finite field by algebraic representation. With all the instruments in hand, we will show how some schemes based on GHDLP can be broken. Thus we conclude that these schemes are not secure under quantum attack. So constructing schemes based on GHDLP is fundamentally wrong.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Hidden discrete logarithmAlgebraic representationCryptanalysis
Contact author(s)
myl20 @ mails tsinghua edu cn
History
2021-12-31: received
Short URL
https://ia.cr/2021/1701
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1701,
      author = {Ma Yanlong},
      title = {Cryptanalysis of the Cryptosystems Based on the Generalized Hidden Discrete Logarithm Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1701},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1701}},
      url = {https://eprint.iacr.org/2021/1701}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.