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\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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. PQCRYPTO 2017
Keywords
XOR of pseudorandom permutationsclassicalquantumclaw-findingproof transformation
Contact author(s)
alan szepieniec @ esat kuleuven be
History
2017-04-26: revised
2017-04-26: received
See all versions
Short URL
https://ia.cr/2017/356
License
Creative Commons Attribution
CC BY

BibTeX

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