Solving low-density multiple subset sum problems with SVP oracle

1. Garey M R and Johnson D S, Computer and Intractability: A Guide to the Theory of NP-Completeness, Freeman W H and San Francisco, 1979.

   Google Scholar 

2. Lenstra A K, Lenstra Jr H W, and Lovász L, Factoring polynomials with rational coefficients, Mathematische Ann., 1982, 261: 513–534.

   Google Scholar 

3. Schnorr C P, A hierarchy of polynomial lattice basis reduction algorithms, Theoretical Computer Science, 1987, 53: 201–224.

   Article  MathSciNet  MATH  Google Scholar 

4. Schnorr C P and Euchner M, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Mathematics of Programming, 1994, 66: 181–199.

   Article  MathSciNet  MATH  Google Scholar 

5. Feng Y, Wu W Y, Zhang J Z, and Chen J W, Exact bivariate polynomial factorization over Z by approximation of roots, Journal of Systems Science and Complexity, 2015, 28(1): 243–260.

   Article  MathSciNet  Google Scholar 

6. Lagarias J C and Odlyzko A M, Solving low-density subset sum problems, J. Assoc. Comp. Mach., 1985, 32(1): 229–246.

   Article  MathSciNet  MATH  Google Scholar 

7. Coster M J, Joux A, LaMacchia B A, Odlyzko A M, Schnorr C P, and Stern J, Improved lowdensity subset sum algorithms, Comput. Complexity, 1992, 2: 111–128.

   Article  MathSciNet  MATH  Google Scholar 

8. Li D and Ma S, Two notes on low-density subset sum algorithm, Proceedings of ISAAC’94, Ed. by Du D and Zhang X, Lecture Notes in Computer Science, Springer-Verlag, 1994, 834: 164–171.

   Google Scholar 

9. Wang H, Xiao H, and Xiao G, EMSSP and its lattice reduction analysis, J. of Xidian University, 2000, 27(5): 616–618 (in Chinese).

   Google Scholar 

10. Liu M J, Wang X Y, Bi J G, and Zheng X, Finding shortest lattice vector for lattice with gaps, previous version, available at http://eprint.iacr.org/2011/139.

11. Merkle R and Hellman M, Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, 1978, 24(5): 525–530.

    Article  Google Scholar 

12. Odlyzko A M, The rise and fall of knapsack cryptosystems, Proceedings of Symposia in Applied Mathematics, Ed. by Pomerance C, Cryptology and Computational Number Theory, Ameri. Math. Soc., 1990, 42: 75–88.

    Article  MathSciNet  Google Scholar 

13. Hästad J, Solving simultaneous modular equations of low degree, SIAM J. Comput., 1988, 17: 336–341.

    Article  MathSciNet  Google Scholar 

14. Mazo J E and Odlyzko A M, Lattice points in high-dimensional spheres, Monatsh. Math, 1990, 110: 47–61.

    Article  MathSciNet  MATH  Google Scholar 

15. Cohen H, A Course in Computational Algebraic Number Theory, Springer-Verlag, Germany, 1996.

    Google Scholar 

16. Micciancio D, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory, 2001, 47(3): 1212–1215.

    Article  MathSciNet  MATH  Google Scholar 

17. Kannan R, Minkowski’s convex body theorem and integer programming, Math. Oper. Res., 1987, 12(3): 415–440.

    Article  MathSciNet  MATH  Google Scholar 

18. Nguyen P Q and Stern J, Adapting density attacks to low-weight knapsacks, Proceedings of Asiacrypt 2005, Ed. by Lee P, Lecture Notes in Computer Science, Springer, 2005, 3788: 41–58.

    MathSciNet  Google Scholar 

Download references