Paper 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.
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
-
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},
url = {https://eprint.iacr.org/2023/056}
}
