Paper 2023/056

Quantum Annealing for Subset Product and Noisy Subset Product

Trey Li
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Quantum AnnealingIsingQUBOSubset Product ProblemNoisy Subset Product ProblemLatticeClosest Vector Problem
Contact author(s)
treyquantum @ gmail com
History
2023-01-19: approved
2023-01-18: received
See all versions
Short URL
https://ia.cr/2023/056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/056,
      author = {Trey Li},
      title = {Quantum Annealing for Subset Product and Noisy Subset Product},
      howpublished = {Cryptology ePrint Archive, Paper 2023/056},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/056}},
      url = {https://eprint.iacr.org/2023/056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.