Solving Random Subset Sum Problem by $l_{p}$-norm SVP Oracle

Gengran Hu; Yanbin Pan; Feng Zhang

Paper 2014/023

Solving Random Subset Sum Problem by -norm SVP Oracle

Gengran Hu, Yanbin Pan, and Feng Zhang

Abstract

It is well known that almost all random subset sum instances with density less than 0.6463... can be solved with an -norm SVP oracle by Lagarias and Odlyzko. Later, Coster \emph{et al.} improved the bound to 0.9408... by using a different lattice. In this paper, we generalize this classical result to -norm. More precisely, we show that for , an -norm SVP oracle can be used to solve almost all random subset sum instances with density bounded by , where and for (asymptotically, ). Since goes increasingly to infinity when tends to infinity, it can be concluded that an -norm SVP oracle with bigger can solve more subset sum instances. An interesting phenomenon is that an -norm SVP oracle with can help solve almost all random subset sum instances with density one, which are thought to be the most difficult instances.

Note: To appear in PKC2014

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: SVP random subset sum problems lattice -norm
Contact author(s): hudiran10 @ mails ucas ac cn
History: 2014-01-08: received
Short URL: https://ia.cr/2014/023
License: CC BY

BibTeX

@misc{cryptoeprint:2014/023,
      author = {Gengran Hu and Yanbin Pan and Feng Zhang},
      title = {Solving Random Subset Sum Problem by $l_{p}$-norm {SVP} Oracle},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/023},
      year = {2014},
      url = {https://eprint.iacr.org/2014/023}
}