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

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]