Paper 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.

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
LatticecryptanalysisGoldreich-Goldwasser-Halevi
Contact author(s)
nyang @ emerald yonsei ac kr
History
2003-03-26: withdrawn
2000-04-24: received
See all versions
Short URL
https://ia.cr/2000/012
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.