Geodesic
Quantum differential and linear cryptanalysis
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 3, pp. 67-88 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study quantum versions of differential and linear cryptanalysis based on a combination of the quantum minimum/maximum search algorithm and the quantum counting algorithm. We obtain estimates of the complexity and the required resources for the quantum differential and quantum linear cryptanalysis of block ciphers. It is shown that the implementation of the quantum linear method requires smaller logical qubits than the implementation of the quantum differential method. It is noted that the acceleration of calculations due to “quantum parallelism” in the quantum differential and linear cryptanalysis based on a combination of Grover’s quantum algorithms and quantum counting algorithm is apparently absent. 
@article{MVK_2021_12_3_a3,
     author = {D. V. Denisenko},
     title = {Quantum differential and linear cryptanalysis},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {67--88},
     year = {2021},
     volume = {12},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_3_a3/}
}
TY  - JOUR
AU  - D. V. Denisenko
TI  - Quantum differential and linear cryptanalysis
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 67
EP  - 88
VL  - 12
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_3_a3/
LA  - en
ID  - MVK_2021_12_3_a3
ER  - 
%0 Journal Article
%A D. V. Denisenko
%T Quantum differential and linear cryptanalysis
%J Matematičeskie voprosy kriptografii
%D 2021
%P 67-88
%V 12
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_3_a3/
%G en
%F MVK_2021_12_3_a3
D. V. Denisenko. Quantum differential and linear cryptanalysis. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 3, pp. 67-88. http://geodesic.mathdoc.fr/item/MVK_2021_12_3_a3/

[1] Biham E., Shamir A., Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, NY, 1993, ix+188 pp. | Zbl

[2] Matsui M., “Linear cryptanalysis method for DES cipher”, EUROCRYPT 1993, Lect. Notes Comput. Sci., 765, 1994, 386–397 | DOI | Zbl

[3] Xie H., Yang L., “Using Bernstein–Vazirani algorithm to attack block ciphers”, Designs, Codes and Cryptography, 87 (2019), 1161–1182 | DOI | Zbl

[4] Li H., Yang L., “A quantum algorithm to approximate the linear structures of Boolean functions”, Math. Struct. Comput. Sci., 28:1 (2018), 1–13 | DOI | Zbl

[5] Li H.-W., Yang L., “Quantum differential cryptanalysis to the block ciphers”, 6th Int. Conf. ATIS 2015, Commun. Comput. Inf. Sci., 557, Springer-Verlag, 2015, 44–51

[6] Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M., “Quantum differential and linear cryptanalysis”, IACR Trans. Symm. Cryptol., 1 (2016), 71–94 | DOI

[7] Zhou Q., Lu S., Zhang A., Sun J., “Quantum differential cryptanalysis”, Quantum Inf. Process., 14 (2015), 2101–2109 | DOI | Zbl

[8] Grover L.K., “Quantum mechanics helps in searching for a needle in a haystack”, Physical Review Letters, 79:2 (1997), 325–328 | DOI

[9] Brassard G., Hoyer P., Tapp A., “Quantum counting”, ICALP, Lect. Notes Comput. Sci., 1443, 1998, 820–831 | DOI

[10] Denisenko D. V., “Application of the quantum counting to estimation the weights of Boolean functions in Quipper”, J. Exper. Theor. Physics, 130 (2020), 643–648 | DOI

[11] Durr C., Høyer P., A quantum algorithm for finding the minimum, 1996, arXiv: quant-ph/9607014

[12] Nielsen M.A., Chuang I.L., Quantum computation and quantum information, Cambridge Univ. Press, 2010, 702 pp. | Zbl

[13] Denisenko D. V., “Quantum circuits for S-box implementation without ancilla qubits”, J. Exper. Theor. Physics, 128:6 (2019), 847–855 | DOI

[14] Denisenko D. V., Nikitenkova M. V., “Optimization of S-boxes GOST R 34.12-2015 “Magma” quantum circuits without ancilla qubits”, CTCrypt 2019 https://ctcrypt.ru/files/files/2019/materials/12_Denisenko.pdf

[15] Bernstein E., Vazirani U., “Quantum complexity theory”, Proc. 25th Annu. ACM Symp. Theory of Computing, ACM, 1993, 11–20 | Zbl

[16] Benenti G., Casati G., Strini G., Principles of Quantum Computation and Information, World Scientific, 2004, 272 pp. | Zbl

[17] Denisenko D. V., Nikitenkova M. V., “Application of Grover's quantum algorithm for SDES key searching”, J. Exper. Theor. Physics, 128 (2019), 25–44 | DOI

[18] Roetteler M., Steinwandt R., “A note on quantum related-key attacks”, Inf. Process. Lett., 115 (2015), 40–44 | DOI | Zbl

[19] Cuccaro S. A., Draper T. G., Kutin S. A., Moulton D. P., A new quantum ripple-carry addition circuit, 2004, arXiv: quant-ph/0410184

[20] Draper T. G., Kutin S. A., Rains E. M., Svore K. M., “A logarithmic-depth quantum carry-lookahead adder”, Quantum Inf. Comput., 6:4 (2006), 351–369 | Zbl

[21] Kaye P., Reversible addition circuit using one ancillary bit with application to quantum computing, 2004, arXiv: quant-ph/0408173