0
$\begingroup$

I've read Intro to Modern Cryptography PRF section (and example 3.26) and on stackexchange(1, 2), but I still don't fully know how to prove it (with probabilities)

To prove it's a PRF, I know you have to prove that no adversary can distinguish $F'_k(x)$ from a random function or I show a possible attack. So the question is (similar to 3.10 from book):

Let F be a length-preserving pseudorandom function. Prove $F'_k(x): \{0, 1\}^{n} → \{0,1\}^{2n}$ such that $F'_k(x) = F_k(0^{n})||F_k(x) $ is a $F'_k(x)$ keyed pseudorandom function or not. Where || denotes concatenation.

What I've done so far: No. Consider an adversary A that input $r \in \{0, 1\}^{n}$, it returns 1 if its first n bits are 0...0. On a truly random string it returns 1 with prob $2^{-n}$. On a pseduorandom string it returns 1 with probability 1. Then adversary has advantage $1 - 2^{-n}$ which violates the definition of psuedorandomness (as it's no longer < negligible?).

1. I believe this is correct, or what have I not understood correctly?
2. If it is the case, I am having trouble applying this to $F'_k(x) = F_k(x)||F_k(\bar x) $ on a paper I found here, example 3.7.2. It says No, but I'm having trouble connecting it with the method I learnt in class, but it looks random to me. I would say it returns 1 if its last bits?? I'm not entirely sure.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ You attack on $F'_k$ doesn't work, as the first $n$ bits $F_k(0^n)$ need not be all 0. Hint: what is $F'_k(0^n)$ ? $\endgroup$
    – poncho
    Commented Oct 31, 2016 at 17:02
  • $\begingroup$ Or even better, what's $F'_k(0^n)$? $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 31, 2016 at 18:43
  • $\begingroup$ Oh, I seem to have misunderstood, then it would work for $0^{n} $, not $F'_k(0^{n})$. As for $F'_k(0^{n})$, so I put in n-bit of 0s and get 2n bit of random bit output because all input of PRF outputs random? I don't see how Im supposed to know what that equals to. I feel like that's not what you're asking me to do though. $\endgroup$
    – user153882
    Commented Oct 31, 2016 at 20:32
  • $\begingroup$ I think I got it. Is it the fact that $F'_k(0^{n})$ will always give the same bits so the first n bit will be same of two messages. So instead, we consider two oracle queries of x1 and x2 and we can distinguish between them so its not PRF. If this is what you're leading me, how do I fit this in my probability argument? $\endgroup$
    – user153882
    Commented Oct 31, 2016 at 21:41
  • $\begingroup$ A true random function is highly unlikely to give the same first $n$ bits when invoked on two different inputs, as then the outputs are chosen uniformly and independently. $\endgroup$
    – fkraiem
    Commented Nov 1, 2016 at 3:27

1 Answer 1

Reset to default
1
$\begingroup$

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F_k'(0^n)$?

Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F_k'(0^n)$?

From your last comment, I guess this isn't clear yet: The distinguisher can query the function for any kind of $x$, as often as he wants - with the limitation of being a polynomial time algorithm. And he has to find out whether the results he gets back are from a truly random function or from $F_k'(.)$, with just $k$ being drawn randomly. So the distinguisher can only do one thing: Choose $x$ in a clever way, so that some structure appears within one result or over several results, if it is $F_k'$ - and the random function does not have that.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for the clarification, i think i wrapped my heads around it and my last comment to be true. Since PRF are deterministic $F_K(0^{n})$ output will be the same. So from my early construction, we consider an adversary... returns 1 if the first n bits are the same as the last n bits (e.g. when $F'_k(0^{n}) = F_k(0^{n})||F_k(0^{n}) $ else return 0... and the rest is same $\endgroup$
    – user153882
    Commented Nov 6, 2016 at 1:39

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.