Geodesic
Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing
Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 117-123.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper, we study lattice-based cryptographic problems, in particular Learning With Errors (LWE) and Short Integer Solution (SIS) lattice problems, which are considered to be known cryptographic primitives that are supposed to be secure against both classical and quantum attacks. We formulated the LWE and SIS problems as Mixed-Integer Programming (MIP) model and then converted them to Quadratic Unconstrained Binary Optimization (QUBO) problem, which can be solved by using a quantum annealer. Quantum annealing searches for the global minimum of an input objective function subjected to the given constraints to optimize the given model. We have estimated the q-bits required for the Quantum Processing Unit (QPU). Our results show that this approach can solve certain instances of the LWE and SIS problems efficiently.
Keywords: post-quantum cryptography, lattice-based cryptography, learning with errorss, short integer solution, quadratic unconstraint binary optimization, quantum processing unit. 
@article{PDMA_2023_16_a29,
     author = {A. Qayyum and M. Haris},
     title = {Cryptanalysis of {LWE} and {SIS-based} cryptosystems by using quantum annealing},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {117--123},
     publisher = {mathdoc},
     number = {16},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2023_16_a29/}
}
TY  - JOUR
AU  - A. Qayyum
AU  - M. Haris
TI  - Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2023
SP  - 117
EP  - 123
IS  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2023_16_a29/
LA  - en
ID  - PDMA_2023_16_a29
ER  - 
%0 Journal Article
%A A. Qayyum
%A M. Haris
%T Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2023
%P 117-123
%N 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2023_16_a29/
%G en
%F PDMA_2023_16_a29
A. Qayyum; M. Haris. Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing. Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 117-123. http://geodesic.mathdoc.fr/item/PDMA_2023_16_a29/

[1] Bos J., Ducas L., Kiltz E., et al., “CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM.”, IEEE Europ. Symp. EuroS (London, UK, 2018), 353–367

[2] Ducas L., Kiltz E., Lepoint T., et al., “Crystals-dilithium: A lattice-based digital signature scheme”, IACR Trans. Cryptographic Hardware Embedded Systems, 2018, no. 1, 238–268 | DOI | MR

[3] Fouque P. A., Hoffstein J., Kirchner P., et al., Falcon: Fast-Fourier lattice-based compact signatures over NTRU, Submission to the NIST post-quantum cryptography standardization process, 2018 https://www.di.ens.fr/p̃rest/Publications/falcon.pdf

[4] Bernstein D. J., Hulsing A., Kolbl S., et al., “The SPHINCS+ signature framework”, Proc. 2019 ACM SIGSAC Conf. CCS'19 (London, UK, 2019), 2129–2146

[5] Peikert C., “A decade of lattice cryptography”, Found. Trends Theor. Comput. Sci., 10:4 (2016), 283–424 | DOI | MR

[6] Lentra A., Lenstra H., and Lovasz L., “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR

[7] Chen Y. and Nguyen P. Q., “BKZ 2.0: Better lattice security estimates”, LNCS, 7073, 2011, 1–20 | MR | Zbl

[8] Ishiguro T., Kiyomoto S., Miyake Y., and Takagi T., “Parallel gauss sieve algorithm: Solving the SVP challenge over a 128-dimensional ideal lattice”, LNCS, 8383, 2014, 411–428 | MR | Zbl

[9] Hanrot G. and Stehle D., “Improved analysis of Kannan's shortest lattice vector algorithm”, LNCS, 4622, 2007, 170–186 | MR | Zbl

[10] Doulgerakis E., Laarhoven T., and de Weger B., “Finding closest lattice vectors using approximate voronoi cells”, LNCS, 11505, 2019, 3–22 | MR | Zbl

[11] Babai L., “On Lovász' lattice reduction and the nearest lattice point problem”, Combinatorica, 1986, no. 6, 1–13 | DOI | MR | Zbl

[12] Date P., Patton R., Schuman C., and Patok P., “Efficiently embedding QUBO problems on adiabatic quantum computers”, Quantum Inform. Processing, 2019, no. 18, 1–31 | MR

[13] Glover F., Kochenberger G., and Hennig R., “Quantum bridge analytics I: a tutorial on formulating and using QUBO models”, Ann. Operations Res., 314:1 (2022), 141–183 | DOI | MR | Zbl

[14] Micciancio D. and Goldwasser S., Complexity of Lattice Problems, Springer, N.Y., 2002 | MR

[15] Regev O., “On lattices, learning with errors, random linear codes, and cryptography”, J. ACM, 56:6 (2009), 1–40 | DOI | MR