Permutation Graphs, Fast Forward Permutations, and Sampling the Cycle Structure of a Permutation

Abstract. P ∈ SN is a 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 SN is Θ(N) if one does not use queries of the form P m (x), but is only Θ(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. 0.