Paper 2020/168

Improved Classical and Quantum Algorithms for Subset-Sum

Xavier Bonnetain, Rémi Bricout, André Schrottenloher, and Yixin Shen

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 $\widetilde{\mathcal{O}} \left(2^{0.291 n}\right)$ downto $\widetilde{\mathcal{O}} \left(2^{0.283 n}\right)$, 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 cost $\widetilde{\mathcal{O}} \left(2^{0.236 n}\right)$, 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 $\widetilde{\mathcal{O}} \left(2^{0.226 n}\right)$ given by Helm and May (TQC 2018). We combine our new techniques to reach a time $\widetilde{\mathcal{O}} \left(2^{0.216 n}\right)$. 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 $\widetilde{\mathcal{O}} \left(2^{0.218 n}\right)$ requiring only the standard classical subset-sum heuristics.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Keywords
subset-sumrepresentation techniquequantum searchquantum walklist merging
Contact author(s)
xbonnetain @ uwaterloo ca
remi bricout @ inria fr
andre schrottenloher @ inria fr
yixin shen @ irif fr
History
2020-11-10: revised
2020-02-14: received
See all versions
Short URL
https://ia.cr/2020/168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/168,
      author = {Xavier Bonnetain and Rémi Bricout and André Schrottenloher and Yixin Shen},
      title = {Improved Classical and Quantum Algorithms for Subset-Sum},
      howpublished = {Cryptology ePrint Archive, Paper 2020/168},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/168}},
      url = {https://eprint.iacr.org/2020/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.