Random access random permutations

Question

I have a large number of parallel processes and a large integer $n$, and want to randomly partition the integers $[0,n)$ among the processes with only $O(1)$ communication.
One nice way to do this would to generate a pseudorandom permutation $pi in S_n$ represented as a small function, so that only the random key/seed need be exchanged.  Is there a good way to do this?

Geoffrey Irving · Answer

Pick $2^k$ slightly larger than $n$, generate a block cypher $f in S_{2^k}$ operating on $k$ bit blocks, and construct a permutation on $[0,n)$ by walking along cycles of $f$ until we get back in the desired range.  Specifically, given $x < n$ we set
$$g(x) = f^p(x) = f(f(f(...x...)))$$
where $p$ is the least positive integer s.t. $f^p(x) < n$.

If $2^k = O(n)$, and the block cypher is good, the walk takes $O(1)$ expected time.  Note that $p$ is necessarily finite, since eventually we will walk back around the cycle and find $f^p(x) = x$.

For more details, see

Black and Rogaway, Ciphers with Arbitrary Finite Domains, 2001.
http://blog.notdot.net/2007/9/Damn-Cool-Algorithms-Part-2-Secure-permutations-with-block-ciphers

Here is an example implementation using a truncated TEA block cypher as described in (2):

https://github.com/otherlab/core/blob/f09fbd19dbaa7b9033eb0888594273a6a3d592a5/random/permute.cpp

Random access random permutations

One Answer

Add your own answers!

Ask a Question