Check if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom

tonythestark

12/6/23, 7:43 AM

Let F be a pseudorandom function. Check if if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom( $\oplus$ is bitwise XOR).

I found this question in a book. I am not sure how to proceed :

$F_1(k,x) = F(k,x) \oplus x \implies F(k,x) \oplus F_1(k, x) = x$

Now do we assume that we know $F(k,x), F_1(k,x)$ ? Because if we do I found x, by xoring these. In general, is there a methodology for proving a function non pseudorandom ?
I have the definition of pseudorandomness of course, but it does not seem really practical.

127

0 + 7

pseudo-random-function

pseudo-random-generator

computational-complexity-theory

Marc Ilunga

12/6/23, 8:53 AM

In the question, you are interacting with $F_1$ thought you can assume you know the implementation of both. But you *don't know* both $F(k,x)$ and $F_1(k,x)$, you only get $F_1(k,x)$ for a $x$ you choose. A strategy to prove the negative is to exhibit an example of $F$ such that $F_1$ is distinguishable from a random function. To prove the positive, show that if one can break $F_1$, then it can also break $F$, which contradicts the starting assumption that F is secure.

tonythestark

12/6/23, 10:06 AM

@MarcIlunga If I know x then I can compute F(k, x) for all possible k and see which gives me F1(k,x) = F(k, x) xor x . That is $O(2^n)$ when I know that k has n bits.

tonythestark

12/6/23, 10:08 AM

@MarcIlunga As for what you said I am not sure I get it : when you say to prove the negative you mean to prove that F1 is not pseudorandom? How can I find an example F, where F1 is distinguishable from a random function?

Marc Ilunga

12/6/23, 10:18 AM

A brute force attack is always possible for most applied schemes, but for a reasonable key space (like 128 bits), this is practically impossible. A general trick to find a counter-example is to start with an $F$ that is secure and "sabotage" it carefully such that the sabotage version remains secure but when used inside $F_1$, $F_1$ becomes insecure.

kelalaka

12/9/23, 7:45 PM

@MarcIlunga Isn't knowing $x$ reveals both $F(k,x)$ and $F_1(k,x)$ if one can choose $x$. tonythestark it is easy with contrapositive. Assume that $F_1$ is not pseudo-random then conclude that $F$ is also not a pseudo-random.

Marc Ilunga

12/9/23, 8:45 PM

@kelalaka, that is correct, we can recover $F(k,x)$. For some reason, I had something else in mind while writing this (Sorry @tonythestark)... But yeah, I agree with the proof strategy that I also outlined in the first comment, but didn't want to spoil the result.

kelalaka

12/13/23, 6:15 PM

tonythestark, you can write your answer...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Check if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom

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.