Improved Classical and Quantum Algorithms for Subset-Sum

Xavier Bonnetain, Rémi Bricout, André Schrottenloher +1

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 $\tilde{\mathc…