Paper 2023/056 Original: eprint.iacr.org/2023/056 ↗

Quantum Annealing for Subset Product and Noisy Subset Product

Abstract

In recent works of Li the noisy subset product problem (also known as subset product with errors) was invented and applied to cryptography. To better understand its hardness, we give a quantum annealing algorithm for it. Our algorithm is the first algorithm for the problem. We also give the first quantum annealing algorithm for the subset product problem. The efficiencies of both algorithms rely on the fundamental efficiency of quantum annealing. At the end we give two lattice algorithms for both problems via solving the closest vector problem. The complexities of the lattice algorithms depend on the complexities of solving the closest vector problem in two special lattices. They are efficient when the special closest vector problems fall into the regime of bounded distance decoding problems that can be efficiently solved using existing methods based on the LLL algorithm or Babai's nearest plane algorithm.