Cryptology ePrint Archive: Report 2014/023

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

Gengran Hu and 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.

Category / Keywords: public-key cryptography / SVP, random subset sum problems, lattice, $l_p$-norm

Date: received 7 Jan 2014

Contact author: hudiran10 at mails ucas ac cn

Available format(s): PDF | BibTeX Citation

Note: To appear in PKC2014

Version: 20140108:175146 (All versions of this report)

Short URL: ia.cr/2014/023

Discussion forum: Show discussion | Start new discussion