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
-
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} }