International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
DaeHun Nyang
JooSeok Song
Download:
URL: http://eprint.iacr.org/2000/012
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11356,
  title={Chosen Message Attack Against Goldreich-Goldwasser-Halevi's Signature Scheme from Crypto'97},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Lattice, cryptanalysis, Goldreich-Goldwasser-Halevi},
  url={http://eprint.iacr.org/2000/012},
  note={ nyang@emerald.yonsei.ac.kr 12137 received 24 Apr 2000, withdrawn 26 Mar 2003},
  author={DaeHun Nyang and JooSeok Song},
  year=2000
}