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?

  • $\begingroup$ The problem seems to be studied, and solved, by format-preserving encryption. We have tag for that. $\endgroup$ – fgrieu Apr 18 '16 at 9:35
  • 1
    $\begingroup$ @fgrieu Added the tag. $\endgroup$ – orlp Apr 18 '16 at 9:41
  • $\begingroup$ Is there even a PRF with such low space requirements? ​ ​ $\endgroup$ – user991 Apr 18 '16 at 9:46
  • $\begingroup$ @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. $\endgroup$ – orlp Apr 18 '16 at 9:57
  • $\begingroup$ Does it seem to have a security level significantly above 512 bits? ​ ​ $\endgroup$ – user991 Apr 18 '16 at 9:59

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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.