Can we construct a k-wise independent permutation on [n] using only constant time and space?

Question

Let $k>0$ be a fixed constant. Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:

1. The construction uses constant time and space (i.e. preprocessing takes constant time and space). We can use randomization.

2. Given $i\in[n]$, $\sigma(i)$ can be computed in constant time and space.

3. The permutation $\sigma$ is $k$-wise independent, i.e., for all $i_1, \ldots, i_k$, the random variables $\sigma(i_1), \ldots, \sigma(i_k)$ are independent and uniformly distributed over $[n]$.

The only thing I currently know uses logarithmic space and polynomial computation time per value of $\sigma(i)$ using pseudo-random generators.

---

Background

I needed something like the above for some recent work, and I ended up using something weaker: I allowed repeated entries and verified that all the numbers that I needed were covered (i.e., a mess). Specifically, I got a $k$-wise independent sequence that can be computed in $O(1)$ time and using constant space. It would be nice to have something simpler, or just know what is known.

Assumptions

I am assuming the unit-cost RAM model. Every word in memory/register is of size $O(\log n)$, and every basic arithmetic operation takes $O(1)$ time. I am willing to assume any reasonable cryptographic assumption (one way function, discrete log, etc).

Current thingy

As suggested by Kaveh, here is the "easy" hack that I currently have (this is quite standard): Let $\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$ be a polynomial over a prime $p$ (think about $p$ as being $n$). Here, each $a_i$ is uniformly and randomly sampled from $[p]$. It is easy to see that $\sigma(1), \sigma(2), \ldots, \sigma(n)$ is a sequence that has repetitions, but it is $k$-wise independent, and roughly $n(1-1/e)$ of the numbers of $[n]$ appear in this sequence. Note, however, that since numbers repeat in this sequence, it is not a permutation.

Answer 1

If you are willing to use cryptographic techniques and rely upon cryptographic assumptions and to accept a computational notion of $k$-wise independence, it's posible that format-preserving encryption (FPE) might be helpful. Let me sketch a few different constructions of this sort.

(By "computational notion of $k$-wise independence", I mean that no adversary with a reasonable running time can distinguish $\sigma$ from a $k$-wise independent permutation, except with negligible advantage. These schemes won't be information-theoretically $k$-wise independent, but they'll be "essentially as good as $k$-wise independent", assuming all of the computation in sight is computationally bounded.)

A practical scheme, for smaller $n$

In particular, use a FPE construction to build a block cipher (pseudorandom permutation, PRP) with the signature $\sigma_k : [n] \to [n]$. For values of $n$ that are smaller than $2^{128}$, probably the best scheme is to use a Feistel construction with a fixed number of rounds (say, 10) and a round function that is a PRF derived from AES. The running time to evaluate $\sigma_k(i)$ for a single value of $i$ will be $O(1)$ AES invocations. Each AES invocation runs in constant time.

Finally, note that any pseudorandom permutation is automatically $k$-wise independent. In particular, the Luby-Rackoff theorem guarantees that with at least 3 rounds, you get (approximate) $k$-wise independence if $k \ll n^{1/4}$, assuming AES is secure. With more rounds, it's likely that there will be a stronger result, but the theorems are harder to prove and become more technical, though it's widely believed that a constant number of rounds should suffice to get extremely high security (and thus essentially perfect $k$-wise independence for all reasonable values of $k$).

Generalizing this to larger $n$

When $n$ is larger, things get weirder, because the unit-cost RAM model implicitly allows up to $O(\lg n)$ parallelism for free. It's not clear to me what the cost of PRPs should be in this model (constant? increasing with $n$? I don't know).

A third possible construction

Let $m$ be a RSA modulus that is a bit larger than $2n$. Define $G$ to be the subgroup of $(\mathbb{Z}/m\mathbb{Z})^*$ containing the elements whose Jacobi symbol is $+1$. Define $\pi : G \to G$ by

$$\pi(x) = x^3 \bmod m.$$

Next, define $\sigma$ by

$$\sigma(i) = g(\pi(f(i)),$$

where $f,g$ are random bijective 2-independent hash functions.

I suspect this construction has a chance of being (approximately) $k$-wise independent, under a RSA-like assumption. I have no proof, just an intuition. The main known regularity of $\pi$ is that it is multiplicatively homomorphic: $\pi(xy) = \pi(x) \pi(y)$. I do not know of any other relevant regularities, even $k$-wise dependence. Applying a 2-independent hash before and after $\pi$ provably eliminates this regularity: if $\pi$ is $k$-wise independence except for multiplicative homomorphicity, then the 2-wise independent hashes seem like they should provide full $k$-wise independence. But this is super-sketchy and light-years from a proof of $k$-wise independence.

Note that you'll need to use format-preserving encryption techniques (e.g., the cycling technique) to ensure that $f,g$ work on $G$ rather than on $(\mathbb{Z}/m\mathbb{Z})$. This scheme should have $O(1)$ (expected) running time to evaluate $\sigma(i)$ at a given input $i$, with suitable choice of $f,g$.

Also, in some sense this candidate construction is abusing the unit-cost RAM model by relying upon the ability to operate on $\lg n$-bit numbers in $O(1)$ time, for large values of $n$, which isn't really reasonable in practice. (This last construction won't be secure for small values of $n$, so this last approach fundamentally relies upon the large-$n$ regime for it to have a chance of working... exactly the regime where the unit-cost RAM model is most dubious.)

I freely admit that this one is quite a stretch, but I mention it in case it triggers some inspiration for a better solution.

For instance, it might be possible to replace $G$ by a suitable elliptic curve group, so that we have $\pi(x) = e x$ over $G$ (recall that elliptic curve groups usually use additive notation rather than multiplicative notation). The good thing about this is that it is not totally unreasonable to conjecture that, if the elliptic curve group $G$ is chosen right, $G$ will behave like a "black-box group", which I think might effectively imply that $\pi$ will be $k$-wise independent "except for effects implied by multiplicative homomorphism". I don't have a complete construction ready to propose (the missing piece is how to choose $G$ and how to construct $f,g$ and how to prove $k$-wise independence from this), but it might be possible to put the pieces together somehow.