Paper 2008/010

A Proof of Security in $O(2^n)$ for the Xor of Two Random Permutations\\ -- Proof with the ``$H_{\sigma}$ technique''--

Jacques Patarin

Abstract

Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. The aim of this paper is to get precise security results for this construction. Since such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example), this problem is interesting both from a theoretical and from a practical point of view. In \cite{SL}, it was proved that Xoring two random permutations gives a secure pseudorandom function if $m \ll 2^{\frac {2n}{3}}$. By ``secure'' we mean here that the scheme will resist all adaptive chosen plaintext attacks limited to $m$ queries (even with unlimited computing power). More generally in \cite{SL} it is also proved that with $k$ Xor, instead of 2, we have security when $m \ll 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m \ll O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m\ll O(2^n /n^{2/3})$). Moreover our proof is very different from the proof strategy suggested in \cite{BI} (we do not use Azuma inequality and Chernoff bounds for example, but we will use the ``$H_{\sigma}$ technique'' as we will explain), and we will get precise and explicit $O$ functions. Another interesting point of our proof is that we will show that this (cryptographic) problem of security is directly related to a very simple to describe and purely combinatorial problem.

Note: A new conjecture is added to Section 10

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Keywords
pseudorandom functionspseudorandom permutationssecurity beyond the birthday bound
Contact author(s)
valerie nachef @ u-cergy fr
History
2016-02-22: last of 5 revisions
2008-01-07: received
See all versions
Short URL
https://ia.cr/2008/010
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/010,
      author = {Jacques Patarin},
      title = {A Proof of Security in $O(2^n)$ for the Xor of Two Random Permutations\\ -- Proof with the ``$H_{\sigma}$ technique''--},
      howpublished = {Cryptology ePrint Archive, Paper 2008/010},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/010}},
      url = {https://eprint.iacr.org/2008/010}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.