Cryptology ePrint Archive: Report 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\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.

Category / Keywords: secret-key cryptography / XOR of pseudorandom permutations, classical, quantum, claw-finding, proof transformation

Original Publication (in the same form): PQCRYPTO 2017

Date: received 20 Apr 2017, last revised 26 Apr 2017

Contact author: alan szepieniec at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20170426:174811 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]