Welcome to the resource topic for 2017/356
Title:
XOR of PRPs in a Quantum World
Authors: Bart Mennink, 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.
ePrint: https://eprint.iacr.org/2017/356
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .