On the reduction of the Bounded Distance Decoding problem to the Ising problem via dual lattice basis reduction
Abstract
We propose a method for reducing the Bounded Distance Decoding problem (BDD) to the Ising problem based on dual lattice basis reduction. We prove that ½ n² + O(n·log n) Ising variables suffice when the dual basis is LLL-reduced, and 3/2 n·log n + O(n) suffice for a Korkin—Zolotarev-reduced dual basis, improving previously known bounds. These results determine the qubit requirements for solving BDD on a quantum adiabatic computer.
Full Text:
PDF (Russian)References
R. L. Rivest, A. Shamir, and L. M. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
T. El Gamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", in Advances in Cryptology — CRYPTO'84, vol. 196, Lect. Notes Comput. Sci. Springer, 1984, pp. 10–18.
T. Albash and D. A. Lidar, "Adiabatic quantum computation", Rev. Mod. Phys., vol. 90, p. 015002, Jan. 2018.
E. Farhi, J. Goldstone, and S. Gutmann, "A Quantum Approximate Optimization Algorithm", arXiv:1411.4028, 2014.
T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model", Phys. Rev. E, vol. 58, no. 5, pp. 5355–5363, 1998.
J.-F. Biasse, X. Bonnetain, E. Kirshanova, et al., "Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography", IET Inf. Secur., vol. 16, no. 4, pp. 577–602, 2022.
D. Joseph, A. Callison, C. Ling, and F. Mintert, "Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later", arXiv:2006.14057, 2021.
I. V. Lysakov, "Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method", Mat. Vopr. Kriptogr., vol. 14, no. 2, pp. 111–122, 2023.
G. Kochenberger, J.-K. Hao, F. Glover, et al., "The unconstrained binary quadratic programming problem: A survey", J. Comb. Optim., vol. 28, pp. 58–81, 2014.
NTRU NIST PQC submission, 2020. [Online]. Available: https://ntru.org/release/NIST-PQSubmission-NTRU-20201016.tar.gz
И. В. Лысаков. «Об оценке временной сложности адиабатических вычислений для одного класса целочисленных решёток», Матем. вопр. криптогр., Т. 16, вып. 1, 121–143, 2025.
И. В. Лысаков, «Сведение задачи поиска ближайшего вектора для целочисленных решёток к задаче Изинга», Дискрет. матем., Т. 37, вып. 3, 94–114, 2025
M. R. Albrecht, M. Prokop, Y. Shen, and P. Wallden, "Variational quantum solutions to the Shortest Vector Problem", Cryptology ePrint Archive, Paper 2022/233, 2022.
J. C. Lagarias, H. W. Lenstra, and C. P. Schnorr, "Korkin–Zolotarev bases and successive minima of a lattice and its reciprocal lattice", Combinatorica, vol. 10, no. 3, pp. 281–312, 1990.
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, "Factoring polynomials with rational coefficients", Math. Ann., vol. 261, pp. 515–534, 1982.
D. Micciancio and S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Springer, 2002.
H. Minkowski, Geometrie der Zahlen, Leipzig: Teubner, 1910.
W. Banaszczyk, "New bounds in some transference theorems in the geometry of numbers", Math. Ann., vol. 296, no. 4, pp. 625–636, 1993.
L. Babai, "On Lovász' lattice reduction and the nearest lattice point problem", in STACS 85, K. Mehlhorn, Ed. Berlin: Springer, 1985, pp. 13–20.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность ИТ-КОНГРЕСС ВМК МГУ 2026 СНЭ
ISSN: 2307-8162