### 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)
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

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.