1
$\begingroup$

Assume the $\mathcal{F} = \{\, f_{s} \,\}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

Let $F_{n}$ be a distribution of functions $f_s$ where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$, and let $RF_n$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^n$ to $\{\, 0,1 \,\}^n$.

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left[ A^{F_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

How about let $F^{\prime}_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$ with any fixed $s$, and let $RF^{\prime}_n$ denote the uniform distribution over the set $\{\, 0,1 \,\}^n$.

So $F^{\prime}_{n} = f_{s}\left( \{\, 0,1 \,\}^{n} \right)$ for a fixed $s \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left[ A^{F^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition implies that $A$ can ask the query of $f_{s}$ for a fixed key $s$ at most $poly(n)$ times.

Is the first definition is correct? Why not choose the another one?

Or even they are both wrong, $F_{n} = f_{\{\, 0,1 \,\}^{n}}\left( \{\, 0,1 \,\}^{n} \right)$?? It makes me confused.

$\endgroup$
2
$\begingroup$

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Nope. That's not right. Consider the set of functions $\{f_s : s \in \{0,1\}^n\}$. According to what you have written, $F_n$ is a random variable that is drawn uniformly at random from that set. (I find this a confusing choice of notation, but I'm going with your proposed definitions.)

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

Actually, what it means is that $s$ is the same for every query, but $x$ can be different for each query. Yes, $A$ can only ask polynomially queries -- that's a crucial restriction.

How about let $F_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$

First off: Please don't redefine the meaning of existing notation. $F_n$ was already defined to mean something else. Don't define it to mean two different things in two different parts of your post. That's just confusing.

Second, that definition doesn't make sense. There's nothing such thing as a function whose input is uniformly distributed over something. That doesn't make sense. A function is a function; its a mapping from inputs to outputs. You don't get to specify an input distribution; a function is whatever it is. Think of a function as a truth table -- there's no way to specify an input distribution, as that's not part of the definition of a function.


I suggest finding a textbook on theoretical cryptography -- e.g., Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell -- and follow the definitions there. I wouldn't recommend relying upon Wikipedia for definitions or to learn from.

$\endgroup$
  • $\begingroup$ Thanks, I have made my question more clear. I read a lecture and it use the game to define it as follow: "Game: (1) $s$ is chosen at random in $\{\, 0,1\,\}^n$. (2) Adversary gets black-box access to the function $f_s$ for as long as it wishes. (3) Adversary outputs a bit $v \in \{\, 0,1\,\}$." That is why I thought $s$ is fixed at first. You mean $F_n$ is a random variable (function) from the set, right? So , when $A$ ask the query of the oracle, $s$ is chosen randomly and $A$ does not know. But why the input $x$ must be the same? I do not understand. $\endgroup$ – TeamBright Mar 4 '18 at 18:22
  • $\begingroup$ I have read the book you suggest about the definition of PRFs. it use the notion $A^{f_{s} \left( \cdot \right)}\left( 1^{n} \right)$ to denote the oracle algorithm. It means that $A$ can ask the query of $f_{s}$ with any input he want without knowing the key $s$, right? $\endgroup$ – TeamBright Mar 4 '18 at 18:31
  • $\begingroup$ @TeamBright, correct, and correct. I don't understand your question about why the input must be the same. $\endgroup$ – D.W. Mar 4 '18 at 19:43
  • $\begingroup$ I think I have known what I want to know. Your answer says that my second view is correct. Maybe you want say that the first part of it is true and the last part is wrong. So maybe you want to check it. $\endgroup$ – TeamBright Mar 4 '18 at 19:54
  • $\begingroup$ @TeamBright, you're right. I mis-read what you wrote. See revised answer. $\endgroup$ – D.W. Mar 5 '18 at 2:20

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.