Date de l'exposé : 06 mars 2020
Improved Classical and Quantum Algorithms for Subset-Sum
We present new classical and quantum algorithms for solving random hard instances
of the subset-sum problem, in which we are given n integers on n bits and try
to find a subset of them that sums to a given target. This classical NP-complete
problem has several applications in cryptography and underlies the security
of some proposed post-quantum cryptosystems.
At EUROCRYPT 2010, Howgrave-Graham and Joux (HGJ) introduced the representation
technique and presented an algorithm running in time $\bigOt{2^{0.337 n}}$.
This asymptotic time was improved by Becker, Coron, Joux (BCJ) at EUROCRYPT 2011.
We show how to improve this further.
We then move to the context of quantum algorithms. The two previous
quantum speedups in the literature are given by Bernstein, Jeffery, Lange
and Meurer (PQCRYPTO 2013) and Helm and May (TQC 2018), which are respectively
quantum versions of HGJ and BCJ. They both rely on the framework of quantum
walks, use exponential quantum memory with quantum random-access and require
an unproven conjecture on quantum walk updates.
We devise a new algorithm, using quantum search only,
that achieves the first quantum speedup in the model of \emph{classical}
memory with quantum random access. Next, we study improvements for the
quantum walks. We show how to avoid the quantum walk conjecture and give
a better quantum walk time complexity for subset-sum.