International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Low-Density Attack Revisited

Authors:
Tetsuya Izu
Jun Kogure
Takeshi Koshiba
Takeshi Shimoyama
Download:
URL: http://eprint.iacr.org/2007/066
Search ePrint
Search Google
Abstract: The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density < 0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.'s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.
BibTeX
@misc{eprint-2007-13348,
  title={Low-Density Attack Revisited},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / subset sum problem, knapsack-based cryptosystem, low-density attack, lattice problem},
  url={http://eprint.iacr.org/2007/066},
  note={ koshiba@tcs.ics.saitama-u.ac.jp 13565 received 20 Feb 2007},
  author={Tetsuya Izu and Jun Kogure and Takeshi Koshiba and Takeshi Shimoyama},
  year=2007
}