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/