Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $$F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $$\mathcal F$$, and there is no P.P.T. algorithm $$\mathcal A$$ able to distinguish $$x\mapsto F(k,x)$$ from a random function for unknown random $$k$$ and non-vanishing probability.

Is the algorithm $$\mathcal A$$ allowed to invoke the algorithm $$\mathcal F$$ implementing $$(k,x)\mapsto F(k,x)$$? Or even more generally, part of it?

That seems necessary to decide if the following $$G$$ is a PRF or not.

• Let $$H:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$$ be a PRF.
• Let $$P_c:\ \{0,1\}^n\to\{0,1\}^n$$ be a PRP with key fixed to arbitrary constant $$c$$, with both $$P$$ and $${P_c}^{-1}$$ computable by a P.P.T. algorithm.
• Define $$G:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$$ by (assimilating bitstrings to integers per big-endian convention) $$G(k,x)\underset{\text{def}}=\begin{cases} {P_c}(k\bmod2^{\lfloor n/2\rfloor})&\text{if }x=0^n\\ 1^n&\text{if }x=1^n\text{ and }P_c^{-1}(k)<2^{\lfloor n/2\rfloor}\\ H(k,x)&\text{otherwise} \end{cases}$$

Essentially, $$G$$ is the PRF $$H$$, except it has a set of weak keys $$k$$ of size $$2^{\lfloor n/2\rfloor}$$, such that whatever $$k$$, $$G(k,0^n)$$ is a weak key; and when $$k$$ is a weak key, $$G(k,1^n)$$ is $$1^n$$.

We can build a distinguisher for $$G$$ that

• submits $$x=0^n$$, gets $$y$$
• applies the algorithm for $$G$$ to input $$(y,1^n)$$
• tests if the outcome is $$1^n$$, which will always be the case for $$G$$, and only with vanishing probability for a random function.

However there seems to be no distinguisher if we can neither apply the algorithm for $$G$$, nor analyze it to extract $$c$$.

Motivation is this question, which asks if $$F_2(k,x)\underset{\text{def}}=F(F(k,0^n),x)$$ is a PRF, assuming $$F$$ is a PRF. If the above $$G$$ was a PRF, $$F=G$$ would be a counterexample.

• In: "We can build a distinguisher for $F$ that" and the following text - do you mean $G$? Nov 21 '20 at 23:47
• @cisnjxqu: yes! Thanks, fixed.
– fgrieu
Nov 22 '20 at 0:00

The adversary $$\mathcal{A}$$ is allowed to invoke the algorithm $$\mathcal{F}$$ (if it is P.P.T.) in any PRF definiton known to me.

We are generally interested in security against every possible P.P.T. algorithm $$\mathcal{A}$$ and require that for every such algorithm $$\mathcal{A}$$ it holds that $$\mathcal{A}$$ can only distinguish from a random function with non-negligible probability.
If $$\mathcal{F}$$ is a P.P.T. algorithm, there exists an adversary $$\mathcal{A}$$ that includes the $$\mathcal{F}$$ functionality. This adversary is able to invoke $$\mathcal{F}$$ and we require from our PRF, that it is secure against that adversary too. The same argument holds for parts of the algorithm $$\mathcal{F}$$.

As far as I understood it, for your example the important question is the following:

Does the adversary $$\mathcal{A}$$ know $$c$$?

Again, we need indistinguishability against all adversaries from a PRF, which means that we need indistinguishability even against an adversary that knows this fixed $$c$$.

• I agree with this answer, and would like to add that this is essentially the formalization of Kerckhoffs principle: the security of $F$ should solely depend on the secrecy of the key $k$. Nov 22 '20 at 0:20

Yes, adversaries may hardcode many things. This is a general theme in crypto and TCS.

In this post, I will present a more foundational point of view and review some formal definitions to hopefully answer (1) why/which hardcoding is allowed, and (2) how that is dealt with in crypto definitions. Since the answer to (2) is so fundamental, here is a copy of it from below:

Takeaway: When formalizing security definitions, values that adversaries should not be able to know are modeled by random variables over which the probability of winning the experiment is taken over, often sampled uniformly at random from an exponentially sized set.

Discussion based on the Definition of PRFs

Let us look at a pretty formal definition of a PRF (cf. [KL14]):

Def. (PRF): An efficiently computable function $$F\colon\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$$ is called a pseudo-random function (PRF) if for all PPT adversaries $$\mathcal{A}$$ there is a negligible function $$\mathrm{negl}\colon\mathbb{N}\to\mathbb{N}$$ such that for all $$n \in \mathbb{N}$$ we have $$\left|\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1] - \Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-))=1]\right|\leq \mathrm{negl}(n).$$

If you're unfamiliar with the notation: the notation $$\Pr_{k\leftarrow_€\ \{0,1\}^n}[\cdot]$$ means that the probability of $$\cdot$$ is taken over the sampling of $$k$$ from $$\{0,1\}^n$$ uniformly at random (signified by $$\leftarrow_€$$; should actually be a dollar sign, but StackExchange's renderer doesn't like this). Analogously for the right term in above's inequality where $$f\leftarrow_€\{0,1\}^n\to\{0,1\}^n$$ means that $$f$$ is sampled from all functions $$\{0,1\}^n\to\{0,1\}^n$$ uniformly at random.

Now consider this definition in the following context:

As per the original post, let $$H$$ be a PRF, $$c$$ some arbitrary fixed constant, $$P_c$$ a PRP, and $$G$$ a function.

Why should adversaries be disallowed to use $$H$$, $$c$$, $$P_c$$, or $$G$$?

Clearly, the definition ranges over all PPT adversaries.

Even if it made sense, how would you (in the mathematical formalization) disallow adversaries from using "outside variables"? What are "outside variables" anyway?

I don't have a concise answer to these questions myself; instead they should just recalibrate your current intuition to the formalism. Disallowing things that are not even clearly specified ("outside things") is non-trivial and doesn't make sense most of the time. Indeed, we could spin Kerckhoff's principle as saying that the adversary is allowed to hardcode anything except the key, that one is disallowed. But here, "the key" is a clear specification and disallowing that can be handled very nicely in the formalism. See below.

In the formal definition above, how are adversaries disallowed from hardcoding the key $$k$$?

While this question might make sense intuitively, it is ill-posed! (Some logicians prefer to answer such questions with "mu.")

What does "the key $$k$$" refer to? Do you mean the $$k$$ from the definition? But that's not visible to adversaries $$\mathcal{A}$$: take a look at the quantifier order. Roughly, you have the following chain of variables being introduced ("bound" in CS lingo):

$$\forall \mathcal{A}\ \exists \mathrm{negl}\ \forall n\ \ldots\ \Pr_{k\leftarrow_€\ \{0,1\}^n}[\ldots]\ \ldots$$

Since adversaries $$\mathcal{A}$$ are bound more outside (i.e. first) than $$k$$, from the adversaries' POV there is no "the key $$k$$". Importantly, this argument says adversaries cannot possibly get syntactically ahold of "the key $$k$$".* The only place in the definition above where "the key $$k$$" syntactically makes sense is in the body of $$\Pr_{k\leftarrow_€\ \{0,1\}^n}[\mathcal{A}(1^n, F(k,-))=1]$$, i.e. the subterm $$\mathcal{A}(1^n, F(k,-))=1$$. That's the only term having syntactic access to "the key $$k$$".

Mind you, there are at least two different (but not mutually exclusive) semantic ways I can think of to get ahold of some/many key(s):

1. Adversaries could enumerate all possible values from $$\{0,1\}^n$$ that $$k$$ can be bound to. Fortunately, for PPT adversaries such bruteforcing is impossible with size exponential (or even superpolynomial) in the security parameter $$n$$.
2. For every possible value of $$k$$ (i.e. in $$\{0,1\}^n$$), there could be an adversary $$\mathcal{A}_k$$ that depends on $$k$$ and actually fulfills $$\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$$ and $$\Pr_{f\leftarrow_€\ \{0,1\}^n\to\{0,1\}^n}[\mathcal{A}(1^n, f(-)) = 1] = 0$$. This almost looks like it would make our whole security definition for PRFs useless since $$|1 - 0| = 1$$ and that can never be less than negligible function. However, crucially observe that I said it fulfills $$\Pr[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$$ and not $$\Pr_{k\leftarrow_€\{0,1\}^n}[\mathcal{A}_k(1^n, F(k, -))] = 1] = 1$$. It makes a big difference whether the probability is taken over a sampling of a random variable or not.

Necessary Conditions for Security Definitions

In summary, there are three necessary conditions for the intuitive yet informal phrase "adversaries don't know the key":

1. syntactically, keys are inaccessible at the place where adversaries arebound,
2. semantically, keys are sampled from a set with size superpolynomial in the security parameter,
3. and semantically again, keys are bound random variables that probabilities are taken over.

If any of those conditions is broken, then most likely the security definition doesn't make sense and doesn't capture what we think it should capture.

Takeaway: When formalizing security definitions, values that adversaries should not be able to know are modeled by random variables over which the probability of winning the experiment is taken over, often sampled uniformly at random from an exponentially sized set.

This concludes the answer to question (1) on why/which hardcoding is allowed.

Another example with "public values" in crypto

Here's another example of a security definition taken from [Sch20]:

Def. (Privacy of RingCT): A RingCT scheme $$\Omega$$ is private if for all PPT adversaries $$\mathcal{A}$$ and positive integers $$\alpha, \beta \in \mathrm{poly}(\lambda)$$, $$\Pr[\mathrm{Privacy}_{\Omega,\mathcal{A}}(\lambda, \alpha, \beta) = 1] \leq \frac{1}{2} + \mathrm{negl}(\lambda)$$

What a RingCT scheme is and how $$\mathrm{Privacy}$$ is defined does not matter at all. More useful for this discussion is the scope of $$\alpha$$ and $$\beta$$.

May adversaries $$\mathcal{A}$$ hardcode $$\alpha$$ and $$\beta$$?

Yes, they may, even for two different reasons (of which one would suffice): - Condition 1. from above is broken: syntactically — as known from logic, we can reorder consecutive universal quantifiers as in $$\forall \mathcal{A} \forall \alpha \forall \beta \ldots$$ as much as we like. Hence, we can reorder to $$\forall \alpha \forall \beta \forall \mathcal{A} \ldots$$. - Condition 3. from above is broken: $$\alpha, \beta$$ are not bound random variables over which the probability is taken. Thus, for every such $$\alpha, \beta$$ you may come up with an adversary $$\mathcal{A}_{\alpha, \beta}$$.

Another example from TCS

In the beginning, I promised that (dis)allowing hardcoding things is also a theme in theoretical computer science. More precisely, this happens in complexity theory, a subfield which is also closely related to cryptography.

There, we define languages $$L \subseteq \{0,1\}^\ast$$ as sets and then ask ourselves how hard it is for a Turing machine to decide for some $$w \in \{0,1\}^\ast$$ that it gets as input whether $$w \in L$$ or not. Concretely, we define:

Def. (Decidable Language).: A language $$L$$ is decidable if there is a Turing machine $$M$$ such that

• for all $$w \in L$$, $$M$$ with input $$w$$ halts acceptingly,
• and for all $$w' \not\in L$$, $$M$$ with input $$w'$$ rejects.

Recall the three conditions from above necessary for security definitions in crypto to make sense. How do they fit here?

Condition 1 is fulfilled since $$w$$ and $$w'$$ are more inner bound than $$M$$. Even though $$M$$ receives both as inputs — which would be unimaginable in crypto if they were keys, there is still a crucial difference between $$M$$ required to cope with all those inputs and $$M$$ required to exist for all those inputs. (The latter would be $$\forall w \in L.\ \exists M.\ \ldots$$) This difference is a common point of confusion when we take $$L$$ to be the Halting problem (an undecidable language). For every ("fixed") $$w \in H$$ there is a Turing machine $$M_w$$ that accepts iff. $$w \in H$$.2

Moreover, condition 2. is also fulfilled here since languages are usually countably infinite. (Otherwise if they were finite, it would be boring to talk about computational complexity.)

Finally, condition 3 is not applicable here since no probabilities are involved.

Footnotes and References

1: Explanation of how I mean "syntactically" requires some CS background: whenever you instantiate the security definition, at the place where you instantiate the adversary $$\mathcal{A}$$ with a term $$t$$, $$t$$ cannot possibly include some $$k$$ because $$k$$ is simply not visible in that context.

2: With classical logic, you might argue that for all $$w \in \{0,1\}^\ast$$, either $$w \in H$$ or $$w \not\in H$$. In the first case, take the machine that accepts immediately as $$M_w$$, and in the second case take the machine that rejects immedatiely.

[KL14]: Katz, J., & Lindell, Y. (2014). Introduction to modern cryptography. CRC Press.

[Sch20]: Dominique Schröder. (2020). Privacy Preserving Cryptocurrencies. Unpublished lecture notes for equinamed course given by author in summer 2020 at FAU Erlangen-Nürnberg. https://www.chaac.tf.fau.eu/teaching/lectures/.

• The MathJax within the spoiler does not render for me. Nov 22 '20 at 13:15