**Permutation graphs, fast forward permutations, and**

*Boaz Tsaban*

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

**Category / Keywords: **foundations /

**Publication Info: **Journal of Algorithms 47 (2), 104--121.

**Date: **received 16 Jul 2003

**Contact author: **tsaban at math huji ac il

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Note: **It seems that a recent result of Goldwasser, Goldreich, and Nussbaum can be extended to prove the conjecture at the end of this paper.

**Version: **20030717:170702 (All versions of this report)

**Short URL: **ia.cr/2003/138

[ Cryptology ePrint archive ]