Quantum Collision Attack with Respect to Primitive Security Margin

Abstract. Quantum computers can often accelerate symmetric-key cryptanalysis. Meanwhile, it is rare that quantum computers offer new cryptanalytic approaches. Particularly, the security margin of a primitive is evaluated by the ratio of the number of attack rounds to the total number of rounds. When there exists some classical cryptanalysis on X rounds against some scheme, quantum computers can reduce its complexity, but may not provide new attacks that can break more than X rounds. In this talk, I will explain that, for hash collisions, quantum computers may break more rounds than the classical computers do. The idea is then demonstrated for AES hashing modes, SHA-256, and SHA-512.

The presenter is affiliated with the NTT Social Informatics Laboratories (Japan) and is currently at NIST as a foreign guest researcher.