# Locally computable random permutation

Let $$A$$ be a set of size $$n$$. Given a random seed $$s$$, I am looking to build a pseudo-random random permutation $$\pi_s: A \rightarrow A$$ such that $$\pi_s(a)$$ is fast to compute for every $$a \in A$$. By "fast to compute" I mean significantly faster than $$O(n)$$ time, e.g. $$O(1)$$ or $$O(\log n)$$ time.

One suggestion is to use Feistel networks or MiMC. Any other suggestions?

• What is the range of $n$ you are interested in? For example, if $n=2^{128}$ then the answer is pretty obvious. – Mikero Dec 20 '18 at 19:17
• Format preserving encryption tries to solve exactly what you're asking for; current solutions have issues for tiny $n$ (less than 100, say), however other than that, it appears to work quite well... – poncho Dec 20 '18 at 19:41
• n is between 2^14 and 2^24 – Randomblue Dec 20 '18 at 22:31
• @poncho: The Wikipedia page on format preserving encryption gives an example: :"One simple way to create an FPE algorithm on {0,...,N-1} is to assign a pseudorandom weight to each integer, then sort by weight." The sort takes at least O(N), so this particular scheme seems to fail the "fast to compute" requirement. – Randomblue Dec 20 '18 at 22:39
• If $n$ is between $2^{14}$ and $2^{24}$ then why are you bothering with asymptotics? I suppose you could use a length doubler together with a small block cipher. – Aleph Dec 21 '18 at 16:35