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 :).

Improve this question
$\endgroup$
2
  • $\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. ♦
    Commented Feb 27, 2018 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$
    – Blanco
    Commented Mar 3, 2018 at 7:33

1 Answer 1

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

Improve this answer
$\endgroup$
5
  • $\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$
    – Blanco
    Commented Mar 4, 2018 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
    Commented Mar 4, 2018 at 10:41
  • $\begingroup$ If you're still confused, you can ask a new question about this matter. $\endgroup$
    – Yuval Filmus
    Commented Mar 4, 2018 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$
    – Blanco
    Commented Mar 6, 2018 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
    Commented Mar 6, 2018 at 12:33

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.