## CryptoDB

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

Authors: DaeHun Nyang JooSeok Song URL: http://eprint.iacr.org/2000/012 Search ePrint Search Google 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
}