<p>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 <a href="https://en.wikipedia.org/wiki/Format-preserving_encryption" rel="nofollow">format-preserving encryption</a> (FPE) might be helpful.  Let me sketch a few different constructions of this sort.</p>

<p>(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.)</p>

<h2>A practical scheme, for smaller $n$</h2>

<p>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.</p>

<p>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$).</p>

<h2>Generalizing this to larger $n$</h2>

<p>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).</p>

<h2>A third possible construction</h2>

<p>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</p>

<p>$$\pi(x) = x^3 \bmod m.$$</p>

<p>Next, define $\sigma$ by</p>

<p>$$\sigma(i) = g(\pi(f(i)),$$</p>

<p>where $f,g$ are random bijective 2-independent hash functions.</p>

<p>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.</p>

<p>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$.</p>

<p>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.)</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-06-07T04:32:52.470Z
This is very interesting - I am traveling  for the next few weeks, but I would look into that when I am back. Thanks!
Sariel Har-Peled
CC BY-SA 3.0
2015-06-05T06:13:44.320Z
2015-06-05T06:13:44.320Z
D.W.
<p>Let <span class="math-container">$k&gt;0$</span> be a fixed constant.
Given an integer <span class="math-container">$n$</span>, we want to construct a permutation <span class="math-container">$\sigma \in S_n$</span> such that:</p>
<ol>
<li><p>The construction uses constant time and space (i.e. preprocessing takes constant time and space). We can use randomization.</p>
</li>
<li><p>Given <span class="math-container">$i\in[n]$</span>, <span class="math-container">$\sigma(i)$</span> can be computed in constant time and space.</p>
</li>
<li><p>The permutation <span class="math-container">$\sigma$</span> is <span class="math-container">$k$</span>-wise independent,
i.e., for all <span class="math-container">$i_1, \ldots, i_k$</span>,
the random variables <span class="math-container">$\sigma(i_1), \ldots, \sigma(i_k)$</span> are independent and
uniformly distributed over <span class="math-container">$[n]$</span>.</p>
</li>
</ol>
<p>The only thing I currently know uses logarithmic space and polynomial computation time per value of <span class="math-container">$\sigma(i)$</span> using pseudo-random generators.</p>
<hr />
<h3>Background</h3>
<p>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 <span class="math-container">$k$</span>-wise independent sequence
that can be computed in <span class="math-container">$O(1)$</span> time and
using constant space.
It would be nice to have something simpler, or just know what is known.</p>
<h2>Assumptions</h2>
<p>I am assuming the unit-cost RAM model. Every word in memory/register is of size <span class="math-container">$O(\log n)$</span>, and every basic arithmetic operation takes <span class="math-container">$O(1)$</span> time. I am willing to assume any reasonable cryptographic assumption (one way function, discrete log, etc).</p>
<h2>Current thingy</h2>
<p>As suggested by Kaveh, here is the &quot;easy&quot; hack that I currently have (this is quite standard): Let <span class="math-container">$\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$</span> be a polynomial over a prime <span class="math-container">$p$</span> (think about <span class="math-container">$p$</span> as being <span class="math-container">$n$</span>). Here, each <span class="math-container">$a_i$</span> is uniformly and randomly sampled from <span class="math-container">$[p]$</span>. It is easy to see that <span class="math-container">$\sigma(1), \sigma(2), \ldots, \sigma(n)$</span> is a sequence that has repetitions, but it is <span class="math-container">$k$</span>-wise independent, and roughly <span class="math-container">$n(1-1/e)$</span> of the numbers of <span class="math-container">$[n]$</span> appear in this sequence. Note, however, that since numbers repeat in this sequence, it is not a permutation.</p>

CC BY-SA 3.0
2015-06-01T00:26:01.977Z
I edited the question a bit, I hope I haven't changed it. Btw, doesn't constant time imply constant space (i.e. mentioning constant space seems redundant). I think it would be helpful in understanding the question if you explain the construction you mention in the background section.
Kaveh
CC BY-SA 3.0
2015-06-01T02:25:00.037Z
What's your model of computation (time and space complexity)?
usul
CC BY-SA 3.0
2015-06-01T02:55:29.167Z
The seed length needs to be at least $\log n$. So it's not clear to me how we can even compute a single $\sigma(i)$ in constant time. The model needs to be clearly specified.
Thomas Steinke
CC BY-SA 3.0
2015-06-01T05:40:58.617Z
I require constant amount of computation per entry of the permutation - so the overall computation time can be linear for the whole permutation.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-01T05:41:33.367Z
As for the space - I am assuming the word model - so every word takes constant amount of space even if it has logarithmic number of bits.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-01T16:53:13.997Z
Partial solution: Suppose $n$ is a prime power and $k=2$. Let $\mathbb{F}$ be a field with $|\mathbb{F}|=n$. Set $\sigma(x)=ax+b$ for random $a,b \in \mathbb{F}$ with $a \ne 0$. Then $\sigma$ is a pairwise independent permutation on $n$ elements that can be computed in "constant time." Maybe this generalizes.
Thomas Steinke
CC BY-SA 3.0
2015-06-01T16:55:40.093Z
Yeh. I knew this ;). The problem is that $k$ has to be much larger, and only the linear polynomials are permutations, not the higher degree ones.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-03T07:45:18.160Z
@SarielHar-Peled Given any Galois field I think one can induce all the permutations of it by using an appropriate Dickson polynomial - the degree of the Dickson polynomial you would need to use depends polynomialy on the size of the Galois field you chose to work on. Does this help?
Student
CC BY-SA 3.0
2015-06-03T14:46:08.530Z
Interesting connection, but this does not seem useful...You need a family of such polynomials that is significantly larger to get k-wise independent sequence - at least (roughly) $n^k$.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-04T19:24:45.020Z
@SarielHar-Peled Could you elaborate how you got this $n^k$ estimate? The hack you explained I think will not work if $p$ is not a prime. But if $p$ is at least a prime-power then I think my proposal is the next option that might work.
Student
CC BY-SA 3.0
2015-06-05T02:00:05.923Z
I am assuming the standard unit cost RAM model, where every word is $O( \log n )$ bits and every basic operation takes constant time. I am assuming $k$ is a constant. I am willing to accept cryptographic assumptions if it helps.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-05T02:04:11.507Z
The $\Omega(n^k)$ follows by a counting argument. Consider fixed $k$ variables in the generated sequence. By assumption, these variables are uniformly distributed, and look independent (because of the $k$-wide independent assumption). As such, there are $n^k$ different values this $k$-tuple can accept, which is a lower bound on the size of the function set we pick our pseudo-random generator from.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-05T17:25:35.083Z
@SarielHar-Peled Thanks for the explanation! If my construction is correct then there is a chance that it might also be optimal. For example you can see this paper : http://www.tau.ac.il/~nogaa/PDFS/kwiseperm4.pdf  Can we work/publish something on this question? :D
Student
<cc.complexity-theory><ds.algorithms><cr.crypto-security><derandomization><k-wise-independence>
Can we construct a k-wise independent permutation on [n] using only constant time and space?
Sariel Har-Peled
# Can we construct a k-wise independent permutation on [n] using only constant time and space?

(Asked by: username_0 on 2015-05-31)

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 username_1, 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.

**Tags:** cc.complexity-theory, ds.algorithms, cr.crypto-security, derandomization, k-wise-independence

> **Comments:**
> **username_1**: I edited the question a bit, I hope I haven't changed it. Btw, doesn't constant time imply constant space (i.e. mentioning constant space seems redundant). I think it would be helpful in understanding the question if you explain the construction you mention in the background section.  
> **username_2**: What's your model of computation (time and space complexity)?  
> **username_3**: The seed length needs to be at least $\log n$. So it's not clear to me how we can even compute a single $\sigma(i)$ in constant time. The model needs to be clearly specified.  
> **username_0**: I require constant amount of computation per entry of the permutation - so the overall computation time can be linear for the whole permutation.  
> **username_0**: As for the space - I am assuming the word model - so every word takes constant amount of space even if it has logarithmic number of bits.  
> **username_3**: Partial solution: Suppose $n$ is a prime power and $k=2$. Let $\mathbb{F}$ be a field with $|\mathbb{F}|=n$. Set $\sigma(x)=ax+b$ for random $a,b \in \mathbb{F}$ with $a \ne 0$. Then $\sigma$ is a pairwise independent permutation on $n$ elements that can be computed in "constant time." Maybe this generalizes.  
> **username_0**: Yeh. I knew this ;). The problem is that $k$ has to be much larger, and only the linear polynomials are permutations, not the higher degree ones.  
> **username_4**: @SarielHar-Peled Given any Galois field I think one can induce all the permutations of it by using an appropriate Dickson polynomial - the degree of the Dickson polynomial you would need to use depends polynomialy on the size of the Galois field you chose to work on. Does this help?  
> **username_0**: Interesting connection, but this does not seem useful...You need a family of such polynomials that is significantly larger to get k-wise independent sequence - at least (roughly) $n^k$.  
> **username_4**: @SarielHar-Peled Could you elaborate how you got this $n^k$ estimate? The hack you explained I think will not work if $p$ is not a prime. But if $p$ is at least a prime-power then I think my proposal is the next option that might work.  
> **username_0**: I am assuming the standard unit cost RAM model, where every word is $O( \log n )$ bits and every basic operation takes constant time. I am assuming $k$ is a constant. I am willing to accept cryptographic assumptions if it helps.  
> **username_0**: The $\Omega(n^k)$ follows by a counting argument. Consider fixed $k$ variables in the generated sequence. By assumption, these variables are uniformly distributed, and look independent (because of the $k$-wide independent assumption). As such, there are $n^k$ different values this $k$-tuple can accept, which is a lower bound on the size of the function set we pick our pseudo-random generator from.  
> **username_4**: @SarielHar-Peled Thanks for the explanation! If my construction is correct then there is a chance that it might also be optimal. For example you can see this paper : http://www.tau.ac.il/~nogaa/PDFS/kwiseperm4.pdf  Can we work/publish something on this question? :D  

---

## 1 answers

### Answer by username_5 on 2015-06-05. Score: 3

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: This is very interesting - I am traveling  for the next few weeks, but I would look into that when I am back. Thanks!  

---

