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?
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) &lt; 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.)