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?

  • $\begingroup$ What is the range of $n$ you are interested in? For example, if $n=2^{128}$ then the answer is pretty obvious. $\endgroup$ – Mikero Dec 20 '18 at 19:17
  • 2
    $\begingroup$ 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... $\endgroup$ – poncho Dec 20 '18 at 19:41
  • $\begingroup$ n is between 2^14 and 2^24 $\endgroup$ – Randomblue Dec 20 '18 at 22:31
  • $\begingroup$ @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. $\endgroup$ – Randomblue Dec 20 '18 at 22:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Aleph Dec 21 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.