Quantum superposition attacks on symmetric encryption protocols

Quantum computers derive their computational power from the ability to manipulate superposition states of quantum registers. The generic quantum attack against a symmetric encryption scheme with key length n using Grover's algorithm has O(2^(n/2)) time complexity. For this kind of attack, an adversary only needs classical access to an encryption oracle. In this talk I discuss adversaries with quantum superposition access to encryption and decryption oracles. First I review and extend work by Kuwakado and Morii showing that a quantum computer with superposition access to an encryption oracle can break the Even-Mansour block cipher with key length n using only O(n) queries. Then, improving on recent work by Boneh and Zhandry, I discuss indistinguishability notions in chosen plaintext and chosen ciphertext attacks by a quantum adversary with superposition oracle access and give constructions that achieve these security notions.