# State of the art low memory arbitrary-domain PRP?

I am wondering what the state of the art is on low memory arbitrary-domain PRPs.

That is, I'm looking for an algorithm that implements bijective function $PRP : \mathbb{Z}_n \times \{0, 1\}^b \rightarrow \mathbb{Z}_n$, where $b$ is an acceptable security level (say, 256 bit).

Such a function is trivial to construct by using a Fisher-Yates shuffle with an appropriate source of pseudo-randomness on a full array of size $n$. However, I'm looking for an algorithm that does not use $O(n)$ memory, but rather on the order of $O(\log n)$.

Even more ideally, I'm looking for an algorithm with a flexible key schedule, such that no precomputation for a certain key is needed. Does this exist, or is it impossible?

• The problem seems to be studied, and solved, by format-preserving encryption. We have tag for that. – fgrieu Apr 18 '16 at 9:35
• @fgrieu Added the tag. – orlp Apr 18 '16 at 9:41
• Is there even a PRF with such low space requirements? ​ ​ – user991 Apr 18 '16 at 9:46
• @RickyDemer As an example, the core function used in Blake2 is a PRP on domain $\{0, 1\}^{512}$ that uses $2 \cdot 512$ bits of memory. – orlp Apr 18 '16 at 9:57
• Does it seem to have a security level significantly above 512 bits? ​ ​ – user991 Apr 18 '16 at 9:59

## 1 Answer

Okay, here's the algorithm for "a fixed security level of 2128":

If ​ n ≤ 2^(2^128) ​ then sometimes-recurse shuffle with 128 bits of security.
If ​ 2^(2^128) < n ​ then encryption just outputs the
plaintext and decryption just outputs the ciphertext.

The identity function can trivially be computed in O(1) space, so that algorithm
also uses only O(1) space. ​ (That's why, for true asymptotic analysis, one must
usually assume some relation between n and the security parameter.)