Skip to Main content Skip to Navigation
Conference papers

Improved Classical and Quantum Algorithms for Subset-Sum

Abstract : We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from 2^0.291n down to 2^0.283n , using more general representations with values in {−1, 0, 1, 2}. Next, we improve the state of the art of quantum algorithms for this problem in several directions. By combining the Howgrave-Graham-Joux algorithm (EUROCRYPT 2010) and quantum search, we devise an algorithm with asymptotic running time 2^0.236n , lower than the cost of the quantum walk based on the same classical algorithm proposed by Bernstein, Jeffery, Lange and Meurer (PQCRYPTO 2013). This algorithm has the advantage of using classical memory with quantum random access, while the previously known algorithms used the quantum walk framework, and required quantum memory with quantum random access. We also propose new quantum walks for subset-sum, performing better than the previous best time complexity of 2^0.226n given by Helm and May (TQC 2018). We combine our new techniques to reach a time 2^0.216n. This time is dependent on a heuristic on quantum walk updates, formalized by Helm and May, that is also required by the previous algorithms. We show how to partially overcome this heuristic, and we obtain an algorithm with quantum time 2^0.218n requiring only the standard classical subset-sum heuristics.
Document type :
Conference papers
Complete list of metadata
Contributor : André Schrottenloher Connect in order to contact the contributor
Submitted on : Tuesday, December 8, 2020 - 11:38:14 AM
Last modification on : Friday, January 21, 2022 - 3:22:46 AM
Long-term archiving on: : Tuesday, March 9, 2021 - 7:05:44 PM


Files produced by the author(s)



Xavier Bonnetain, Rémi Bricout, André Schrottenloher, Yixin Shen. Improved Classical and Quantum Algorithms for Subset-Sum. Asiacrypt 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2020, Daejeon / Virtual, South Korea. pp.633--666, ⟨10.1007/978-3-030-64834-3_22⟩. ⟨hal-03046017⟩



Les métriques sont temporairement indisponibles