1
$\begingroup$

Suppose $F_s$ be a family of keyed pseudorandom functions. Define $F'_s(x)=F_x(s)$. Is $F'_s$ a family of pseudorandom functions? It seems false but I am able to give a proof assuming $F$ is constructed from a length doubling PRG. It is essentially the same proof as construction of PRF from PRG. I don't know if this proof is correct. Can someone tell me if the statement is true or false?

$\endgroup$
5
  • 4
    $\begingroup$ Note that the statement you are trying to prove or disprove is an implication. I.e., you are trying to prove/disprove the statement "If $F$ is a family of PRFs, then $F'$ is also a family of PRFs." Having a single positive example, i.e., a single instance of $F$ where $F'$ is also a PRF, tells you nothing about the validity of the statement. On the other hand, having a single counterexample, i.e., a single PRF-family $F$ such that $F'$ is not a family of PRFs, disproves the statement. $\endgroup$
    – Maeher
    Commented Oct 19, 2023 at 7:28
  • $\begingroup$ So in general is the statement false? $\endgroup$
    – Suraj
    Commented Oct 19, 2023 at 8:42
  • $\begingroup$ Can you come up with a counter example? $\endgroup$
    – Maeher
    Commented Oct 19, 2023 at 10:26
  • $\begingroup$ Is this a homework? Could you indicate of the origin of this question? $\endgroup$
    – kelalaka
    Commented Oct 22, 2023 at 10:38
  • $\begingroup$ it is not a homework question. i conjectured this to help solve some other problem. $\endgroup$
    – Suraj
    Commented Oct 23, 2023 at 8:48

2 Answers 2

2
$\begingroup$

No. If $F$ is a PRF family with a weak key, i.e., a key that forces it to behave insecurely, then $F'$ is not a PRF.

Weak-key PRF: Let $G$ be a secure PRF. We construct another secure PRF, $F$ with a weak key $\hat k$. Define $F_k(x) = G_k(x)$ for all $k \neq \hat k$. Then define $F_{\hat k}(x) = x$ for all $x$. $F$ is still a PRF, because the likelihood of selecting $\hat k$ from the space of keys is negligible.

However, $F'$ is not a secure PRF with this definition of $F$. An adversary may simply query for $\hat k$ and recieve the full key $F'_x(\hat k) = F_{\hat k}(x) = x$.

$\endgroup$
1
  • $\begingroup$ By the way, this might be a HW $\endgroup$
    – kelalaka
    Commented Oct 22, 2023 at 10:38
0
$\begingroup$

$F'$ need not be a secure PRF. Consider: $F$ be a (keyed) Pseudo-Random Permutation defined over: $\mathcal{X} \times \mathcal{X} \to \mathcal{X}$. By the PRF-PRP switching lemma, then $F_s$ is a secure PRF (up to a certain number of queries). Note that $F'_s$ is well defined since the key and message output spaces are the same.

Claim: A two-queries adversary distinguishes $F'$ from a truly random function with overwhelming probability.

As an aside, PRFs that are secure when keyed by the input are called swap PRFs. When the PRF is secure, when keyed either way, then the PRF is a dual-PRF. Some PRFs have this nice property; an example is HMAC. Backendal et al. show that HMAC is a dual PRF when the inputs satisfy certain properties, as is usually the case in protocols that rely on the dual PRF security of HMAC.

$\endgroup$
5
  • $\begingroup$ By the way, this might be a HW $\endgroup$
    – kelalaka
    Commented Oct 22, 2023 at 10:38
  • $\begingroup$ @kelalaka, that was my guess as well. Hence, I kept the explanation a bit incomplete. $\endgroup$ Commented Oct 22, 2023 at 10:51
  • $\begingroup$ I've asked the OP for clarification.. $\endgroup$
    – kelalaka
    Commented Oct 22, 2023 at 10:53
  • $\begingroup$ thanks for the answer this is very interesting. $\endgroup$
    – Suraj
    Commented Oct 23, 2023 at 8:50
  • $\begingroup$ @Suraj, if you've got the details, feel free to post an answer expanding on that. $\endgroup$ Commented Oct 23, 2023 at 11:09

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.