7
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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