arXiv:math/0411098math.CO
Simple Permutations Mix Even Better
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We study the random composition of a small family of O(n^3) simple permutations on {0,1}^n. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor, n^2*k^2 compositions of random permutations from this family suffice. In addition, our results give an explicit construction of a degree O(n^3) Cayley graph of the alternating group of 2^n objects with a spectral gap Omega(2^{-n}/n^2), which is a substantial improvement over previous constructions.
Strictly speaking, shift and xor alone will not net you a secure cipher, seeing that those are both linear GF(2) operations. You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc. But on the subject of extremely simple…
pbsdView on HNParent context