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.