Score:0

When does a proof by reduction do not hold?

mu flag

I was doing the following exercise from the Introduction of Modern Cryptography from Katz and Lindell:

Let $F$ be a length preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$, state whether $F'$ is a pseudorandom function. If yes, prove it; if not, show an attack.

(d) $F'_k(x) \stackrel{def}{=} F_k(0||x) || F_k(x||1)$

I understand that in this case $F'_k$ is not a pseudorandom function since we could, efficiently and with non-negligible probability, distinguish $F'$ from a random function by querying $x = 0^{n-2}||1$ and $x = 0^{n-1}$, and checking if the leftmost $n$ bits of the first query equals the rightmost $n$ bits of the second query.

However, I could also assume an adversary $A$ that distinguishes $F'$ from a random function, and use it as a subroutine to attack $F$. For any query $x$ from $A$, I query for $0||x$ and $x||1$, concatenate the results and give them back to $A$. Whatever $A$ answers, that would be my answer.

Unfortunately, I can't justify why the proof is wrong. Maybe because there is a low probability that I can use the result from $A$ to break $F$? But how do I formalise that if I don't know know anything about $A$?

fgrieu avatar
ng flag
Hint: what about the $A$ defined above "However" being a working counterexample to what follows (which comes without any argument that it gives an advantage, BTW)?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.