Score:0

PRGs from OW functions

jp flag

Given a OW function $f:\{0,1\}^n\to\{0,1\}^n$ with hardcore predicate $h(x)$, you can build a PRG $G$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$ The expansion condition for $G$ is trivially satisfied (the seed $s$ has length $n$, while the string $f(s)\Vert h(s)$ has length $n+1$). How can I show that $G$ is also pseudorandom, that is, for any probabilistic poly-time distinguisher $\mathcal D$ $$\mid\Pr[\mathcal D(G(s)=1]-\Pr[\mathcal D(r)=1]\mid\le\epsilon(n), \quad r\leftarrow \{0,1\}^{n+1} $$ where $\epsilon(n)$ is a negligible function of $n$?

jp flag
@kelalaka Sorry, is your comment about my deleted question (the necessity of the one-time requirement for the one-time pad)? If so I have found a satisfactory answer [here](https://crypto.stackexchange.com/questions/59/taking-advantage-of-one-time-pad-key-reuse?rq=1) already.
kelalaka avatar
in flag
Welcome to Cryptography.SE. Usually search first then ask. The usual approach for this type of questions assume that there is a distinguisher for $G$ then there is one for $f$, too.
jp flag
@kelalaka Could you elaborate on that?
Chris Peikert avatar
in flag
It’s not enough for $f$ to be a one-way *function*, but it does suffice for it to be a one-way *permutation* (i.e, a bijection).
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.