Cryptology ePrint Archive: Report 2013/368

Security in $O(2^n)$ for the Xor of Two Random Permutations\\ -- Proof with the standard $H$ technique--

Jacques Patarin

Abstract: Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. In~\cite{P08a}, it is proved that we have security against CPA-2 attacks when $m \ll O(2^n)$, where $m$ is the number of queries and $n$ is the number of bits of the inputs and outputs of the bijections. In this paper, we will obtain similar (but slightly different) results by using the ``standard H technique'' instead of the ``$H_{\sigma}$ technique''. It will be interesting to compare the two techniques, their similarities and the differences between the proofs and the results.

Category / Keywords: secret-key cryptography / Pseudorandom functions, pseudorandom permutations, security beyond the birthday bound, Luby-Rackoff backwards.

Date: received 10 Jun 2013, last revised 22 Feb 2016

Contact author: valerie nachef at u-cergy fr

Available format(s): PDF | BibTeX Citation

Note: A section and an appendix have been added

Version: 20160222:204643 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]