A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems

Standard

A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems. / Bakharev, A. O.

In: Journal of Applied and Industrial Mathematics, Vol. 18, No. 3, 06.2024, p. 395-411.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{dbbc755ca6b44d709197373102d3ffc6,

title = "A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems",

abstract = "Abstract: Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetriccryptography currently in use. Most attacks on these cryptosystems can be reduced to theshortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oraclemodel from Grover{\textquoteright}s algorithm to implement a hybrid quantum-classical algorithm based on theGaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle isproposed and analyzed. Two implementations of the new quantum oracle model are proposed andestimated. The complexity of implementing the new quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed. Comparison of obtained results for new and existingmodels of quantum oracle is given.",

keywords = "Grover{\textquoteright}s algorithm, lattice-based cryptography, post-quantum cryptography, public-key cryptography, quantum computation, quantum search",

author = "Bakharev, {A. O.}",

note = "This research was supported by the Mathematical Center in Akademgorodok under agreement no. 075-201315-20132022-2013282 with the Ministry of Science and Higher Education of the Russian Federation.",

year = "2024",

month = jun,

doi = "10.1134/S1990478924030037",

language = "English",

volume = "18",

pages = "395--411",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "3",

}

RIS

TY - JOUR

T1 - A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems

AU - Bakharev, A. O.

N1 - This research was supported by the Mathematical Center in Akademgorodok under agreement no. 075-201315-20132022-2013282 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2024/6

Y1 - 2024/6

N2 - Abstract: Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetriccryptography currently in use. Most attacks on these cryptosystems can be reduced to theshortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oraclemodel from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on theGaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle isproposed and analyzed. Two implementations of the new quantum oracle model are proposed andestimated. The complexity of implementing the new quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed. Comparison of obtained results for new and existingmodels of quantum oracle is given.

AB - Abstract: Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetriccryptography currently in use. Most attacks on these cryptosystems can be reduced to theshortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oraclemodel from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on theGaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle isproposed and analyzed. Two implementations of the new quantum oracle model are proposed andestimated. The complexity of implementing the new quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed. Comparison of obtained results for new and existingmodels of quantum oracle is given.

KW - Grover’s algorithm

KW - lattice-based cryptography

KW - post-quantum cryptography

KW - public-key cryptography

KW - quantum computation

KW - quantum search

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85211119696&origin=inward&txGid=d69dd69e59ab0c825ff5a0c3f7db00f6

UR - https://www.mendeley.com/catalogue/78bcb745-3b00-36da-a6fb-6659b345ed62/

U2 - 10.1134/S1990478924030037

DO - 10.1134/S1990478924030037

M3 - Article

VL - 18

SP - 395

EP - 411

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

ER -

ID: 61285834