Paper 2011/567
On the sparse subset sum problem from Gentry-Halevi's implementation of fully homomorphic encryption
Moon Sung Lee
Abstract
In Gentry's fully homoomrphic cryptosystem, a sparse subset sum problem is used and a big set is included in the public key. In the implementation of a variant of Gentry's scheme, to reduce the size of the public key, Gentry and Halevi used a specific form of a sparse subset sum problem with geometric progressions. In this note, we show that their sparse subset sum challenges are rather easy given the aggressive choice of parameters. Our experiment shows that even their large instance of a sparse subset sum problem could be solved within two days with probability of about $44\%$. A more conservative parameter choice can easily avoid our attack.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- sparse subset sumlattice reductiondimension reduction methodgeometric progressionhomomorphic encryption
- Contact author(s)
- mslee @ nims re kr
- History
- 2011-10-22: received
- Short URL
- https://ia.cr/2011/567
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/567,
author = {Moon Sung Lee},
title = {On the sparse subset sum problem from Gentry-Halevi's implementation of fully homomorphic encryption},
howpublished = {Cryptology ePrint Archive, Paper 2011/567},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/567}},
url = {https://eprint.iacr.org/2011/567}
}
