Paper 2014/023

Solving Random Subset Sum Problem by $l_{p}$-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 $l_{2}$-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 $l_p$-norm. More precisely, we show that for $p\in \mathbb{Z}^{+}$, an $l_p$-norm SVP oracle can be used to solve almost all random subset sum instances with density bounded by $\delta_p$, where $\delta_1=0.5761$ and $\delta_p = 1/(\frac{1}{2^p}\log_2(2^{p+1}-2)+\log_2(1+\frac{1}{(2^p-1)(1-(\frac{1}{2^{p+1}-2})^{(2^p-1)})})))$ for $p\geq 3$(asymptotically, $\delta_p\approx 2^p/(p+2)$). Since $\delta_p$ goes increasingly to infinity when $p$ tends to infinity, it can be concluded that an $l_p$-norm SVP oracle with bigger $p$ can solve more subset sum instances. An interesting phenomenon is that an $l_p$-norm SVP oracle with $p\geq 3$ 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
SVPrandom subset sum problemslattice$l_p$-norm
Contact author(s)
hudiran10 @ mails ucas ac cn
History
2014-01-08: received
Short URL
https://ia.cr/2014/023
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/023}},
      url = {https://eprint.iacr.org/2014/023}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.