Welcome to the resource topic for 2014/023
Title:
Solving Random Subset Sum Problem by l_{p}-norm SVP Oracle
Authors: Gengran Hu, Yanbin Pan, 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.
ePrint: https://eprint.iacr.org/2014/023
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .