Geodesic
Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method
Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 111-122 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we study closest vector problem (CVP) and bounded distance decoding problem (BDD) which arise in cryptanalysis of lattice-based cryptosystems. We propose an algorithm for solving bounded distance decoding (BDD) problem using quantum annealing. We provide estimates for the number of qubits required to run this algorithm for lattices that have Hermite normal form with a single pivot element not equal to 1, and for lattices defined by the public keys of NTRUEncrypt cryptosystem. 
@article{MVK_2023_14_2_a6,
     author = {I. V. Lysakov},
     title = {Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {111--122},
     year = {2023},
     volume = {14},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a6/}
}
TY  - JOUR
AU  - I. V. Lysakov
TI  - Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method
JO  - Matematičeskie voprosy kriptografii
PY  - 2023
SP  - 111
EP  - 122
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a6/
LA  - en
ID  - MVK_2023_14_2_a6
ER  - 
%0 Journal Article
%A I. V. Lysakov
%T Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method
%J Matematičeskie voprosy kriptografii
%D 2023
%P 111-122
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a6/
%G en
%F MVK_2023_14_2_a6
I. V. Lysakov. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method. Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 111-122. http://geodesic.mathdoc.fr/item/MVK_2023_14_2_a6/

[1] Ajtai M., Kumar R., Sivakumar D., “A sieve algorithm for the shortest lattice vector problem”, Proc. 33th Annu. ACM Symp. Theory of Computing, STOC'01, 601–610 | MR | Zbl

[2] Aharonov D., Regev O., “A lattice problem in Quantum NP”, Proc. 44th Symp. Found. Comput. Sci., FOCS 2003, 2003, 210–219 | MR

[3] Cohen H., A Course in Computational Algebraic Number Theory, Springer Publ. Co., Berlin–Heidelberg, 2010 | MR

[4] D-Wave, https://www.dwavesys.com

[5] Elgamal T., “A public-key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inf. Theory, 31 (1985), 469–472 | DOI | MR | Zbl

[6] Fincke U., Pohst M., “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Math. Comp., 44 (1985), 463–471 | DOI | MR | Zbl

[7] Grover L. K., “A fast quantum mechanical algorithm for database search”, Proc. 28th Annu. ACM Symp. Theory of Computing, STOC'96, 1996, 212–219 | MR | Zbl

[8] Kadowaki T., Nishimori H., “Quantum annealing in the transverse Ising model”, Phys. Rev. E — Stat. Phys., 58:5 (1998), 5355–5363 | DOI

[9] Minkowski H., Geometrie der Zahlen, Teubner, Leipzig, 1910 | MR

[10] Joseph D., Callison A., Ling C., Mintert F., “Two quantum Ising algorithms for the shortest-vector problem: one for now and one for later”, Phys. Rev. A, 103:3 (2021), 032433 | DOI | MR

[11] Laarhoven T., Mosca M., J. van der Pol, “Solving the shortest vector problem in lattices faster using Quantum Search”, Lect. Notes Comput. Sci., 7932, 2013, 83–101 | DOI | Zbl

[12] Kannan R., “Improved algorithms for integer programming and related lattice problems”, Proc. 15th Annu. ACM Symp. Theory of Computing, STOC'83, 1983, 193–206

[13] Micciancio D., Voulgaris P., “A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations”, Proc. 42th Annu. ACM Symp. Theory of Computing, STOC'10, 2010, 351–358 | MR | Zbl

[14] NIST PQC, https://csrc.nist.gov/Projects/post-quantum-cryptography

[15] NTRU NIST PQC submission 2020, https://ntru.org/release/NIST-PQSubmission-NTRU-20201016.tar.gz

[16] Post M., “On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications”, ACM SIGSAM Bulletin, 15:1 (1981), 37–44 | DOI

[17] Rivest R. L., Shamir A., Adleman L., “A method for obtaining digital signatures and public-key cryptosystems”, Communic. ACM, 21:2 (1976), 120–126 | DOI | MR

[18] Shor P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Review, 41:3 (1999), 303–322 | DOI | MR