Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Hidden discrete logarithm, Algebraic representation, Cryptanalysis

Date: received 30 Dec 2021

Contact author: myl20 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20211231:122232 (All versions of this report)

Short URL: ia.cr/2021/1701


[ Cryptology ePrint archive ]