Paper 2017/356

XOR of PRPs in a Quantum World

Bart Mennink and Alan Szepieniec


In the classical world, the XOR of pseudorandom permutations $E_{k_1}\oplus\cdots\oplus E_{k_r}$ for $r\geq2$ 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 $2$ pseudorandom permutations already yield optimal security. Next, we perform a quantum security analysis of the construction, and prove that it achieves security up to $\min\{|K|^{1/2}/r,|X|\}$ 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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. PQCRYPTO 2017
XOR of pseudorandom permutationsclassicalquantumclaw-findingproof transformation
Contact author(s)
alan szepieniec @ esat kuleuven be
2017-04-26: revised
2017-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bart Mennink and Alan Szepieniec},
      title = {XOR of PRPs in a Quantum World},
      howpublished = {Cryptology ePrint Archive, Paper 2017/356},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.