You are looking at a specific version 20030717:170702 of this paper. See the latest version.

Paper 2003/138

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.

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.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Journal of Algorithms 47 (2), 104--121.
Contact author(s)
tsaban @ math huji ac il
History
2003-07-17: received
Short URL
https://ia.cr/2003/138
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.