0
$\begingroup$

I am working through Katz and Lindell, and Theorem 3.26 in the book proves that a construction based on a PRF is CPA-secure. The thrust of the scheme is that if $F_k$ is a PRF, with $k, m, r \in \{0, 1\}^n$ (key, message, random-string), then $c = (r, F_k(r) \oplus m)$.

The idea behind the proof is to first prove the security of the scheme using a truly random function $f_n$ in place of the PRF $F_k$, and then show that if the scheme is not secure using PRF $F_k$, then $F_k$ can be distinguished from a truly random function.

In the proof, the authors remark that the encryption scheme which uses the truly random function $f_n$ in place of PRF $F_k$ is not a legal encryption scheme, "because it is not efficient". I am wondering if someone can explain to me why this is the case? I would think the scheme would still be efficient, because even though the description of the truly random function $f_n$ is long, using it to determine which points map to what should be fast?

$\endgroup$

1 Answer 1

0
$\begingroup$

Consider a truly random function $F:\{0,1\}^n\to\{0,1\}^n$. By a basic argument in combinatorics, writing down a description of $F$ takes $n2^n$ bits. Concretely, we often want $n\approx 128$ (plausibly this could be smaller in the information theoretic setting though, say 80 on the low end). This is already significantly more storage than is available in any practical situations.

This is to say that even storing a description of the relevant function is infeasible. If we store the function as a lookup table of $2^n$ entries, then indexing into it (in constant time) takes exponentially long, ie the function is slow to compute as well.

$\endgroup$
10
  • $\begingroup$ I see. So we do not have a "hash function" for example that can efficiently lookup the input and determine the output in the table? $\endgroup$
    – user918212
    Jun 8, 2022 at 17:23
  • $\begingroup$ The primary concern is storage, everything else doesn't matter. A terabyte is $2^{40}$ bytes, or $2^{43}$ bits. To store the aforementioned random function, you would need devices to have $\approx 2^{80}$ terabytes of storage to devote to solely storing the aforementioned random function. $\endgroup$
    – Mark
    Jun 8, 2022 at 18:01
  • $\begingroup$ There are other issued as well (evaluation efficiency, and that "uniformly random" is not a property that third parties can verify, so there is a trust assumption), but the primary issue is that no computers on earth could possibly store the function. $\endgroup$
    – Mark
    Jun 8, 2022 at 18:02
  • $\begingroup$ But this primarily seems to be a practical concern, and strictly working with the definitions, there is no limitation in terms of storage -- only the speed at which the function evaluates an input with respect to the magnitude of the security parameter $\endgroup$
    – user918212
    Jun 8, 2022 at 18:27
  • $\begingroup$ There is a limitation in terms of definitions, due to the constant time evaluation issue I mentioned earlier. Moreover, one can (directly) have there be an issue in terms of complexity theory as well, but it is dependent on the underlying computational model in subtle ways. For example, evaluation time will be exponentially bad in standard TM models. In RAM models it may be faster, but RAM models are not thought to be realistic in the setting of extremely high storage for precisely the reasons described in this post (in particular, one can argue that the RAM model violates causality) $\endgroup$
    – Mark
    Jun 8, 2022 at 18:41

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.