Paper 2014/023 Original: eprint.iacr.org/2014/023 ↗

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

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.