Geodesic
Quantum attacks against iterated block ciphers
Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 2, pp. 71-90 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the amplification of security against quantum attacks provided by iteration of block ciphers. We prove that (in contrast to the classical Meet-in-the-middle attack) for quantum adversaries two iterated ideal block ciphers are more much difficult to attack than a single one. The optimality of the quantized Meet-in-the-middle attack is proved. It is shown that contrary to the classical case, the quantum dissection attack against 4-encryption has a better time complexity than a quantum Meet-in-the-middle attack. 
@article{MVK_2016_7_2_a6,
     author = {M. Kaplan},
     title = {Quantum attacks against iterated block ciphers},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {71--90},
     year = {2016},
     volume = {7},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a6/}
}
TY  - JOUR
AU  - M. Kaplan
TI  - Quantum attacks against iterated block ciphers
JO  - Matematičeskie voprosy kriptografii
PY  - 2016
SP  - 71
EP  - 90
VL  - 7
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a6/
LA  - en
ID  - MVK_2016_7_2_a6
ER  - 
%0 Journal Article
%A M. Kaplan
%T Quantum attacks against iterated block ciphers
%J Matematičeskie voprosy kriptografii
%D 2016
%P 71-90
%V 7
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a6/
%G en
%F MVK_2016_7_2_a6
M. Kaplan. Quantum attacks against iterated block ciphers. Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 2, pp. 71-90. http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a6/

[1] Ambainis A., “Quantum walk algorithm for element distinctness”, SIAM J. Comput., 37:1 (2007), 210–239 | DOI | MR | Zbl

[2] Aaronson S., Shi Y., “Quantum lower bounds for the collision and the element distinctness problems”, J. ACM, 51:4 (2004), 595–605 | DOI | MR | Zbl

[3] Buhrman H., Dürr C., Heiligman M., Høyer P., Magniez F., Santha M., de Wolf R., “Quantum algorithms for element distinctness”, SIAM J. Comput., 34:6 (2005), 1324–1330 | DOI | MR | Zbl

[4] Bernstein D., “Grover vs. McEliece”, Post-Quantum Cryptography, PQCrypto 2010 Proceedings, Lect. Notes Comput. Sci., 6061, 2010, 73–80 | DOI | MR | Zbl

[5] Brassard G., Høyer P., Kalach K., Kaplan M., Laplante S., Salvail L., “Merkle puzzles in a quantum world”, Advances in Cryptology-CRYPTO 2011, Lect. Notes Comput. Sci., 6841, 2011, 391–410 | DOI | MR | Zbl

[6] Brassard G., Høyer P., Tapp A., “Quantum cryptanalysis of hash and claw-free functions”, LATIN'98: Theoretical Informatics, Lect. Notes Comput. Sci., 1380, 1998, 163–169 | DOI | MR

[7] Dinur I., Dunkelman O., Keller N., Shamir A., “Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems”, Advances in Cryptology-CRYPTO 2012, Lect. Notes Comput. Sci., 7417, 2012, 719–740 | DOI | MR | Zbl

[8] Diffie W., Hellman M. E., “Exhaustive cryptanalysis of the NBS data encryption standard”, Computer, 10:6 (1977), 74–84 | DOI

[9] Høyer P., Lee T., Špalek R., “Negative weights make adversaries stronger”, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC'07 (2007), 526–535 | MR

[10] Lee T., Mittal R., Reichardt B. W., Špalek R., Szegedy M., “Quantum query complexity of state conversion”, 2011 IEEE 52nd Annual IEEE Symposium on Foundations of Computer Science-FOCS 2011 (2011), 344–353 | MR | Zbl

[11] Merkle R., Hellman M., “On the security of multiple encryption”, Commun. ACM, 24:7 (1981), 465–467 | DOI | MR

[12] Magniez F., Nayak A., Roland J., Santha M., “Search via quantum walk”, SIAM J. Comput., 40:1 (2011), 142–164 | DOI | MR | Zbl

[13] Santha M., “Quantum walk based search algorithms”, Theory and Applications of Models of Computation, TAMC 2008, Lect. Notes Comput. Sci., 4978, 2008, 31–46 | DOI | MR | Zbl