Cryptology ePrint Archive: Report 2000/012

Chosen Message Attack Against Goldreich-Goldwasser-Halevi's Signature Scheme from Crypto'97

DaeHun Nyang and JooSeok Song

Abstract: The Goldreich-Goldwasser-Halevi(GGH)'s signature scheme from Crypto '99 is cryptanalyzed, which is based on the well-known lattice problem. We mount a chosen message attack on the signature scheme, and show the signature scheme is vulnerable to the attack. We collects $n$ lattice points that are linearly independent each other, and constructs a new basis that generates a sub-lattice of the original lattice. The sub-lattice is shown to be sufficient to generate a valid signature. Empirical results are presented to show the effectiveness of the attack. Finally, we show that the cube-like parameter used for the private-key generation is harmful to the security of the scheme.

Category / Keywords: public-key cryptography / Lattice, cryptanalysis, Goldreich-Goldwasser-Halevi

Date: received 24 Apr 2000, withdrawn 26 Mar 2003

Contact author: nyang at emerald yonsei ac kr

Available format(s): (-- withdrawn --)

Version: 20030326:085933 (All versions of this report)

Short URL: ia.cr/2000/012

Discussion forum: Show discussion | Start new discussion