Score:0

PRG implies OWF Proof

lk flag

enter image description here I got the idea of this proof, that since PRG expands from n to 2n, it cannot project to all {0,1}^{2n}, only to a neglible part which we can abuse to make a good distinguisher just by telling if A succeeds finding a preimage in X. A random string from U2n has very likely no preimage in X. Thus we can distinguish U2n from G(Un). But I think I do not understand the construction f well. What's the purpose of our y? Can we not just proof this using f(x) := G(x)? Also why is f variable? If we define f like that, shouldn't it be a projection from 2n to 2n? I miss something.

cn flag
The definition of a OWF being used there probably requires the function to be length preserving. Since G is expanding you need to pad the input.
killertoge avatar
lk flag
Ok that makes sense. I skipped back to page 40: "In the sequel, we shall deal only with one-way functions that are length-regular [...] mostly with length-preserving functions". I use Goldreichs book to read proofs that our lecture is not talking about, so I should be more careful. Thanks.
kodlu avatar
sa flag
Your question is a pain to read. Please use mathjax
killertoge avatar
lk flag
@kodlu I learn some Latex currently, I will definitely try to use it in my next question.
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.