Paper 2017/356

XOR of PRPs in a Quantum World

Bart Mennink and Alan Szepieniec

Abstract

In the classical world, the XOR of pseudorandom permutations $E_{k_1}\oplus \cdots \oplus E_{k_r}$ for $r\ge 2$ is a well-established way to design a pseudorandom function with ``optimal'' security: security up to approximately $min\{|K|,|X|\}$ queries, where $K$ and $X$ are the key and state space of the block cipher $E$. We investigate security of this construction against adversaries who have access to quantum computers. We first present a key recovery attack in $|K{|}^{r/(r+1)}$ complexity. The attack relies on a clever application of a claw-finding algorithm and testifies of a significant gap with the classical setting where $$ pseudorandom permutations already yield optimal security. Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to $$ queries. The analysis relies on a generic characterization of classical and quantum distinguishers and a universal transformation of classical security proofs to the quantum setting that is of general interest.