Geodesic
Optimization of $S$-boxes GOST R 34.12-2015 > quantum circuits without ancilla qubits
Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 43-52 
D. V. Denisenko; M. V. Nikitenkova. Optimization of $S$-boxes GOST R 34.12-2015 <> quantum circuits without ancilla qubits. Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 43-52. http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a3/
@article{MVK_2020_11_2_a3,
     author = {D. V. Denisenko and M. V. Nikitenkova},
     title = {Optimization of $S$-boxes {GOST} {R} {34.12-2015~<<Magma>>} quantum circuits without ancilla qubits},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {43--52},
     year = {2020},
     volume = {11},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a3/}
}
TY  - JOUR
AU  - D. V. Denisenko
AU  - M. V. Nikitenkova
TI  - Optimization of $S$-boxes GOST R 34.12-2015 <> quantum circuits without ancilla qubits
JO  - Matematičeskie voprosy kriptografii
PY  - 2020
SP  - 43
EP  - 52
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a3/
LA  - en
ID  - MVK_2020_11_2_a3
ER  - 
%0 Journal Article
%A D. V. Denisenko
%A M. V. Nikitenkova
%T Optimization of $S$-boxes GOST R 34.12-2015 <> quantum circuits without ancilla qubits
%J Matematičeskie voprosy kriptografii
%D 2020
%P 43-52
%V 11
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a3/
%G en
%F MVK_2020_11_2_a3

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

We study the ways to implement $S$-boxes by quantum circuits with a minimal number of logical qubits and logical quantum gates without using ancilla qubits. New quantum circuits that implement the $S$-boxes of the GOST R 34.12-2015 “Magma” on 4 logical qubits are constructed. It means that for substitutions $s \in S(V_n)$ with a large number of cycles there exist quantum circuits on $n$ logical qubits that implement the substitution $s$ with fewer logical quantum gates compared with substitutions $g \in S(V_n)$ with a small number of cycles.

[1] Shor P.W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 26:5 (1997), 1484–1509 | DOI | MR | Zbl

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

[3] Simon D.R., “On the power of quantum computation”, SIAM J. Comput., 26:5 (1997), 1474–1483 | DOI | MR | Zbl

[4] Gainutdinova A.F., Comparative complexity of quantum and classical models of calculations., Thesis for the degree of Candidate of Phys.-Math. Sci., 2004

[5] Quantum Computing Report, https://quantumcomputingreport.com

[6] Quantum Computing: Progress and Prospects, Nat. Acad. Sci., Engin., and Medicine, The Nat. Acad. Press, Washington, DC, 2018, 202 pp.

[7] Denisenko D.V., “Quantum circuits for substitution implementation without ancilla qubits”, Zh. Exper. Teor. Fis., 155:6 (2019), 999–1008 (in Russian) | DOI

[8] Nielsen M.A., Chuang I.L., Quantum computation and quantum information, Cambridge Univ. Press, 2010, xxxii+676 pp. | MR | Zbl

[9] Kim P., Han D., Jeong K.C., “Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2”, Quantum Inf. Process., 17:339 (2018) | MR

[10] Grassl M., Langenberg B., Roetteler M., Steinwandt R., Applying Grover's algorithm to AES: quantum resourse estimation, Cryptology ePrint Archive, Report 2019/103, 2015 | MR

[11] Younes A., Miller J., Automated method for building CNOT based quantum circuits for Boolean functions, 2003, arXiv: quant-ph/0304099v1

[12] Jaques S., Schanck J. M., Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE, Cryptology ePrint Archive, Report 2019/103, 2019

[13] Submission requirements and evaluation criteria for the post-quantum cryptography standardization process, National Institute of Standards and Technology, 2017

[14] The Quipper Language, http://www.mathstat.dal.ca/s̃elinger/quipper/