Paper 2013/368

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

Jacques Patarin


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.

Note: A section and an appendix have been added

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown status
Pseudorandom functionspseudorandom permutationssecurity beyond the birthday boundLuby-Rackoff backwards.
Contact author(s)
valerie nachef @ u-cergy fr
2016-02-22: last of 2 revisions
2013-06-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jacques Patarin},
      title = {Security in $O(2^n)$ for the Xor of Two Random Permutations\\ -- Proof with the standard $H$ technique--},
      howpublished = {Cryptology ePrint Archive, Paper 2013/368},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.