# [Resource Topic] 2003/138: Permutation graphs, fast forward permutations, and

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.

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.