Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. More specifically, we show that a weaker derandomization tool suffices: all we need is a generator that produces ``pseudorandom walks" on undirected graphs with a consistent labelling. Such generators with sufficiently good parameters are implied by the proof that undirected connectivity is in logspace of Reingold, and made explicit by Reingold, Trevisan and Vadhan.

With this approach we are able to obtain families of k-wise almost independent permutations of size that is optimal up to polynomial factor. More precisely, if the distance from uniform for any k tuple should be at most delta, then the size of the description of a permutation in the family is O(kn + log 1/delta).

Postscript , gzipped
Postscript , PDF
. Slides: ppt

- Moni Naor and Omer Reingold,
, Postscript , gzipped Postscript*On the construction of pseudo-random permutations: Luby-Rackoff revisited* - Moni Naor and Omer Reingold,
J. of Cryptology, vol 14, 2001.*Constructing Pseudo-Random Permutations with a Prescribed Structure,**Abstract , Postscript , gzipped Postscript*

Back to On-Line Publications, Back to Recent Publications , Back to Publications by topic