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?

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

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$

Your Answer

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

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