CryptoDB
Permutation graphs, fast forward permutations, and
| Authors: | |
|---|---|
| Download: | |
| Abstract: | A permutation $P\in S_N$ is a \emph{fast forward permutation} if for each $m$ the computational complexity of evaluating $P^m(x)$ is small independently of $m$ and $x$. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in $S_N$ is $\Theta(N)$ if one does not use queries of the form $P^m(x)$, but is only $\Theta(1)$ if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form $P^m(x)$ are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold. |
BibTeX
@misc{eprint-2003-11853,
title={Permutation graphs, fast forward permutations, and},
booktitle={IACR Eprint archive},
keywords={foundations /},
url={http://eprint.iacr.org/2003/138},
note={Journal of Algorithms 47 (2), 104--121. tsaban@math.huji.ac.il 12250 received 16 Jul 2003},
author={Boaz Tsaban},
year=2003
}