Welcome to the resource topic for
**2003/138**

**Title:**

Permutation graphs, fast forward permutations, and

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

**ePrint:**
https://eprint.iacr.org/2003/138

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .