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^p1)(1(\frac{1}{2^{p+1}2})^{(2^p1)})})))$ 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)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 SVPrandom subset sum problemslattice$l_p$norm
 Contact author(s)
 hudiran10 @ mails ucas ac cn
 History
 20140108: 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}, note = {\url{https://eprint.iacr.org/2014/023}}, url = {https://eprint.iacr.org/2014/023} }