Almost kappa-Wise Independent Random Permutation of the Cube

摘要

In the paper the authors give a very simple construction which converts a random01-string sigma of length polynomial in given integers n and k < 2(sup n) into a permutation pi of the cube (left brace)0,1(right brace)(sup n), which looks random in the sense that, for any sequence x(1),..., x(k) of distinct points in (left brace)9,1(right brace)(sup n), the images phi(x(1)),..., phi(x(k)) are approximately uniformly distributed among the set of all k-tuples of distinct points in (left brace)0,1(right brace)(sup n). (The result is interesting mainly when k is small compared with 2(sup n).) It is likely that the permutation is pseudo-random in the technical sense in which case it is known to have applications. For example, it would then be the basis of an extremely secure private-key cryptosystem. The proof that the permutation is almost k-wise independent uses techniques due to Jerrum and Sinclar and Diaconis and Stroock concerning rapidly mixing Markov chains.