Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

Details Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

2002-07-08

arxiv.org/abs/cs/0207027v6

Journal of Algorithms 47 (2003), 104--121

Computer Science

Cryptography and Security

Corrected a small error

Scientific paper

10.1016/S0196-6774(03)00017-8

A permutation P on {1,..,N} 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 on {1,..,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.

Affiliated with

Also associated with

No associations

Rating

Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172495