CryptoDB
A Proof of Security in O(2^n) for the Xor of Two Random Permutations
| Authors: | |
|---|---|
| Download: | |
| Abstract: |
\begin{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 << 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 << 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m << O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m< |
BibTeX
@misc{eprint-2008-17687,
title={A Proof of Security in O(2^n) for the Xor of Two Random Permutations},
booktitle={IACR Eprint archive},
keywords={pseudorandom functions, pseudorandom permutations, security beyond the birthday bound},
url={http://eprint.iacr.org/2008/010},
note={ valerie.nachef@u-cergy.fr 14029 received 7 Jan 2008, last revised 30 May 2008},
author={Jacques Patarin},
year=2008
}