Score:0

Prove a function G is not a pseudo random generator

de flag

A function G(x) = x || x (where “||” denotes string concatenation). It is given that G is not s pseudo random generator. Can someone describe how can we prove this. I am getting a bit confused in the concept of pseudo random generator.

What I have understood till now - The formal definition of pseudo random generator is given as $\Pr[PRG_{A,G(n)} = 1] ≤ 1/2 + negl(n)$. Here we can observe that for this function G the output will have equal first and second halves. How to use this with the formal defination to prove that G is insecure ?

Maarten Bodewes avatar
in flag
As it is stated it is still a assignment without clear indication of effort. Please [edit] the question to include your reasoning; it doesn't have to be correct, it just needs to be *there*.
Marc Ilunga avatar
tr flag
Welcome to Crypto.SE! A useful approach here would be to write down the definition of a PRG and the security guarantees of such an object. From there, maybe you can see why this particular instance does not work? This may also help with editing the comment in a conformant way (see the first comment)
archie09 avatar
de flag
Thank you for letting me know. I have edited the question. Would really appreciate some help with the concept.
fgrieu avatar
ng flag
@archie09: you have skipped a lot of the formal definition of PRG. Like it's input and output domains, perhaps it's expansion property (some sources skip that), and for sure the context for the formula: something on the tune of "for any Probabilistic Polynomial-Time algorithm $\mathcal A$, there is a negligible function $\mathrm{negl}$ such that..." As a relatively minor aside I don't recognize the formula as the one in the defintion of a PRG I studied, but it may be that I used a different reference.
archie09 avatar
de flag
@fgrieu Could you tell me a good source I can refer for this definition. I tried searching but not able to understand this concept properly.
Maarten Bodewes avatar
in flag
In the end you should be able to prove somehow that a bit in the output doesn't have a 0.5 + $e$ chance of being 0 or 1, while including previous output. That should be easy, right? However, I don't see how to do that given just the probability in the definition, so I'll leave you to do that formally.
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.