Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

Standard

Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems. / Bakharev, A. O.

In: Journal of Applied and Industrial Mathematics, Vol. 17, No. 3, 1, 09.2023, p. 459-482.

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

BibTeX

@article{09c8513c55284ceb98732ac1fddd0710,

title = "Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems",

abstract = "Due to the development of quantum computing, there is a need for the development andanalysis of cryptosystems resistant to attacks using a quantum computer (post-quantumcryptography algorithms). The security of many well-known post-quantum cryptosystems basedon lattice theory depends on the complexity of solving the shortest vector problem (SVP). In thispaper, a model of quantum oracle developed from Grover{\textquoteright}s algorithm is described to implementa hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used forattacks on cryptosystems whose security depends on solving the SVP. Upper bounds for thenumber of qubits and the depth of the circuit were obtained for two implementations of theproposed quantum oracle model: minimizing the number of qubits and minimizing the circuitdepth. The complexity of implementing the proposed quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed.",

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

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

note = "This work was supported by the Mathematical Center in Akademgorodok under the agreement with the Ministry of Science and Higher Education of Russia, agreement no. 075–15–2022–282.",

year = "2023",

month = sep,

doi = "10.1134/S1990478923030018",

language = "English",

volume = "17",

pages = "459--482",

journal = "Journal of Applied and Industrial Mathematics",

issn = "1990-4789",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "3",

}

RIS

TY - JOUR

T1 - Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

AU - Bakharev, A. O.

N1 - This work was supported by the Mathematical Center in Akademgorodok under the agreement with the Ministry of Science and Higher Education of Russia, agreement no. 075–15–2022–282.

PY - 2023/9

Y1 - 2023/9

N2 - Due to the development of quantum computing, there is a need for the development andanalysis of cryptosystems resistant to attacks using a quantum computer (post-quantumcryptography algorithms). The security of many well-known post-quantum cryptosystems basedon lattice theory depends on the complexity of solving the shortest vector problem (SVP). In thispaper, a model of quantum oracle developed from Grover’s algorithm is described to implementa hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used forattacks on cryptosystems whose security depends on solving the SVP. Upper bounds for thenumber of qubits and the depth of the circuit were obtained for two implementations of theproposed quantum oracle model: minimizing the number of qubits and minimizing the circuitdepth. The complexity of implementing the proposed quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed.

AB - Due to the development of quantum computing, there is a need for the development andanalysis of cryptosystems resistant to attacks using a quantum computer (post-quantumcryptography algorithms). The security of many well-known post-quantum cryptosystems basedon lattice theory depends on the complexity of solving the shortest vector problem (SVP). In thispaper, a model of quantum oracle developed from Grover’s algorithm is described to implementa hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used forattacks on cryptosystems whose security depends on solving the SVP. Upper bounds for thenumber of qubits and the depth of the circuit were obtained for two implementations of theproposed quantum oracle model: minimizing the number of qubits and minimizing the circuitdepth. The complexity of implementing the proposed quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed.

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-85175805595&origin=inward&txGid=7cfb545bdcb29cd4b17c52ba07b4ce42

UR - https://elibrary.ru/item.asp?id=63978955

UR - https://www.mendeley.com/catalogue/62e3c924-39ec-3ed8-bb6e-58b3b7b2dad9/

U2 - 10.1134/S1990478923030018

DO - 10.1134/S1990478923030018

M3 - Article

VL - 17

SP - 459

EP - 482

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 3

M1 - 1

ER -

ID: 59554055