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 .