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

Note: A section and an appendix have been added

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

BibTeX

@misc{cryptoeprint:2013/368,
      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{https://eprint.iacr.org/2013/368}},
      url = {https://eprint.iacr.org/2013/368}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.