Document Open Access Logo

Subset Sum Quantumly in 1.17^n

Authors Alexander Helm, Alexander May

PDF

File

Thumbnail PDF
PDF
LIPIcs.TQC.2018.5.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Subset sum
  • Quantum walk
  • Representation technique

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the quantum complexity of solving the subset sum problem, where the elements a_1, ..., a_n are randomly chosen from Z_{2^{l(n)}} and t = sum_i a_i in Z_{2^{l(n)}} is a sum of n/2 elements. In 2013, Bernstein, Jeffery, Lange and Meurer constructed a quantum subset sum algorithm with heuristic time complexity 2^{0.241n}, by enhancing the classical subset sum algorithm of Howgrave-Graham and Joux with a quantum random walk technique. We improve on this by defining a quantum random walk for the classical subset sum algorithm of Becker, Coron and Joux. The new algorithm only needs heuristic running time and memory 2^{0.226n}, for almost all random subset sum instances.

Cite As Get BibTex

Alexander Helm and Alexander May. Subset Sum Quantumly in 1.17^n. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TQC.2018.5

Author Details

Alexander Helm
  • Horst Görtz Institute for IT-Security, Ruhr University Bochum, Germany
Alexander May
  • Horst Görtz Institute for IT-Security, Ruhr University Bochum, Germany

Funding

  • Helm, Alexander: Founded by NRW Research Training Group SecHuman.

References

  1. Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum walks on graphs. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 50-59. ACM, 2001. Google Scholar
  2. Miklós Ajtai. The shortest vector problem in l2 is np-hard for randomized reductions. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 10-19. ACM, 1998. Google Scholar
  3. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210-239, 2007. URL: http://dx.doi.org/10.1137/S0097539705447311.
  4. Per Austrin, Mikko Koivisto, Petteri Kaski, and Jesper Nederlof. Dense subset sum may be the hardest. arXiv preprint arXiv:1508.06019, 2015. Google Scholar
  5. Anja Becker, Jean-Sébastien Coron, and Antoine Joux. Improved generic algorithms for hard knapsacks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 364-385. Springer, 2011. Google Scholar
  6. Daniel J Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. Quantum algorithms for the subset-sum problem. In International Workshop on Post-Quantum Cryptography, pages 16-33. Springer, 2013. Google Scholar
  7. Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer. Quantum Algorithms for the Subset-Sum Problem, pages 16-33. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38616-9_2.
  8. Ernest F Brickell. Solving low density knapsacks. In Advances in Cryptology, pages 25-37. Springer, 1984. Google Scholar
  9. Matthijs J Coster, Brian A LaMacchia, Andrew M Odlyzko, and Claus P Schnorr. An improved low-density subset sum algorithm. In Workshop on the Theory and Application of of Cryptographic Techniques, pages 54-67. Springer, 1991. Google Scholar
  10. Sebastian Faust, Daniel Masny, and Daniele Venturi. Chosen-ciphertext security from subset sum. In Public-Key Cryptography-PKC 2016, pages 35-46. Springer, 2016. Google Scholar
  11. Zvi Galil and Oded Margalit. An almost linear-time algorithm for the dense subset-sum problem. SIAM Journal on Computing, 20(6):1157-1189, 1991. Google Scholar
  12. Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219. ACM, 1996. Google Scholar
  13. Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. Journal of the ACM (JACM), 21(2):277-292, 1974. Google Scholar
  14. Nick Howgrave-Graham and Antoine Joux. New generic algorithms for hard knapsacks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 235-256. Springer, 2010. Google Scholar
  15. Antoine Joux and Jacques Stern. Improving the critical density of the lagarias-odlyzko attack against subset sum problems. In International Symposium on Fundamentals of Computation Theory, pages 258-264. Springer, 1991. Google Scholar
  16. Ghazal Kachigar and Jean-Pierre Tillich. Quantum information set decoding algorithms. CoRR, abs/1703.00263, 2017. URL: http://arxiv.org/abs/1703.00263,
  17. Jeffrey C Lagarias and Andrew M Odlyzko. Solving low-density subset sum problems. Journal of the ACM (JACM), 32(1):229-246, 1985. Google Scholar
  18. Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. Public-key cryptographic primitives provably as secure as subset sum. In Theory of Cryptography Conference, pages 382-400. Springer, 2010. Google Scholar
  19. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, 2011. Google Scholar
  20. Andrew M Odlyzko. The rise and fall of knapsack cryptosystems. Cryptology and computational number theory, 42:75-88, 1990. Google Scholar
  21. Richard Schroeppel and Adi Shamir. A T=O(2^n/2). SIAM journal on Computing, 10(3):456-464, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact