2
$\begingroup$

Let $\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|}$.

We define a family of functions $\mathcal{H} = \{ h_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$, where $h_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$ and $h_{s}\left( \cdot \right) = f_{s}\left( f_{s} \left( \cdot \right) \right)$.

Let $F_{n}$ ($H_{n}$) be the distribution of functions $f_{s}$ ($h_{s}$), where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$. And let $R_{n}$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^{n}$ to $\{\, 0,1 \,\}^{n}$.

We know that for any PPT adversary $A$, if for all $n$, $$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$ then $\mathcal{F}$ is a family of PRFs. And if $\mathcal{F}$ is a family of PRFs, then $\mathcal{H}$ is also a family of PRFs.

How about $A$ can only can query the oracle of a function sampled only one time? In other words, if $$\left\vert \Pr\left[ A\left( F_{n} \right) = 1 \right] - \Pr\left[ A\left( R_{n} \right) = 1 \right] \right\vert \leq \epsilon (n)$$ holds true, can we get that $$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$

PS: The title may not clear enough, but I don't know how to make it better :(. Thanks for anyone helping me to make it better :).

$\endgroup$
  • $\begingroup$ There's something wrong with your question setup. A PRF takes two inputs: a value in $\{0,1\}^n$, and a key. Your function $f_n$ takes only one input. So, syntactically, it can't be a PRF. It's also not clear to me what you mean by "the distribution of functions $f_n$". You might want to check your understanding of the definitions. Once you fix that up, you'll find that a simple counterexample is $f(k,x) = k \oplus x$. $\endgroup$ – D.W. Feb 27 '18 at 16:33
  • $\begingroup$ @D.W. You are right, I wrote the correct definition at the first time, and I decided to simplify it. And I did not realize that it is wrong. $\endgroup$ – TeamBright Mar 3 '18 at 7:33
2
$\begingroup$

Let $F_n$ be a random involution induced by a random perfect matching on $\{0,1\}^n$. For any input $x$, the distributions of $F_n(x)$ and $R_n(x)$ are almost identical (in fact, $F_n(x)$ has the same distribution as $R_n(x)$ conditioned on the event $R_n(x) \neq x$, which occurs with probability $1-2^{-n}$), so they are statistically indistinguishable. However, $H_n$ is the identity function, so it is easy to distinguish from a random function.

With some more work, it might be possible to extend this from one query to any fixed polynomial number of queries.

$\endgroup$
  • $\begingroup$ There is a one more question about the definition, can you help me? The definition of PRFs in wiki says that $F_{n}$ is the distribution of functions $f_{s}$, where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$. But as I know, $F_{n}$ is the distribution of functions $f_{s}$, where $s$ if fixed at first, right? Does the definition correct? $\endgroup$ – TeamBright Mar 4 '18 at 7:45
  • $\begingroup$ If $s$ is fixed then the distribution is concentrated on a single function! What would $s$ be fixed to? Rather, you should think of $s$ as a key or randomness which is used to generate the function. If this confuses you, I suggest reading $f$ instead of $f_s$. $\endgroup$ – Yuval Filmus Mar 4 '18 at 10:41
  • $\begingroup$ If you're still confused, you can ask a new question about this matter. $\endgroup$ – Yuval Filmus Mar 4 '18 at 10:42
  • $\begingroup$ Let $D_{1}$ and $D_{2}$ be two distributions. I notice even though they are statistically indistinguishable, maybe there still exists an oracle algorithm $D$ which can distinguish them. Why? I think that two distributions are statistically indistinguishable means that they cannot be distinguished even if $D$ has infinite power. $\endgroup$ – TeamBright Mar 6 '18 at 7:31
  • $\begingroup$ Two distributions are statistically indistinguishable if their statistical distance is negligible (smaller than inverse polynomial). The statistical distance is the advantage of the best algorithm which tries to separate the two distributions (i.e., the maximum of $|\Pr[D(D_1)=1] - \Pr[D(D_2)=1]|$ over all oracle algorithms $D$). $\endgroup$ – Yuval Filmus Mar 6 '18 at 12:33

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.