Using Simon's Algorithm to Attack Symmetric-Key Cryptographic Primitives
This work highlights vulnerabilities in classical cryptography for post-quantum security, though it is incremental as similar results were independently achieved by others.
The paper tackled the problem of assessing the security of symmetric-key cryptographic primitives against quantum attacks, showing that Simon's algorithm can be used to break the 3-round Feistel network and CBC-MAC, with attacks like forging tags for chosen-prefix messages.
We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon's algorithm can be used to show insecurity of commonly used cryptographic symmetric-key primitives. Specifically, these examples consist of a quantum distinguisher for the 3-round Feistel network and a forgery attack on CBC-MAC which forges a tag for a chosen-prefix message querying only other messages (of the same length). We assume that an adversary has quantum-oracle access to the respective classical primitives. Similar results have been achieved recently in independent work by Kaplan et al. Our findings shed new light on the post-quantum security of cryptographic schemes and underline that classical security proofs of cryptographic constructions need to be revisited in light of quantum attackers.