Solving Random Subset Sum Problem by lp-norm SVP Oracle

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 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 is an element of 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/(1/2(p) log(2) (2(p+1) - 2) + log(2) (1 + 1/(2(p) -1)(1-(1/(2(p+1) - 2)(2(p-1)))))) for p >= 3(asymptotically, delta(p) approximate to 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 >= 3 can help solve almost all random subset sum instances with density one, which are thought to be the most difficult instances.