Prove a function G is not a pseudo random generator

archie09

1/16/23, 9:53 AM

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 ?

0 + 0

pseudo-random-generator

Maarten Bodewes

1/16/23, 10:00 AM

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

1/16/23, 10:43 AM

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

1/16/23, 6:42 PM

Thank you for letting me know. I have edited the question. Would really appreciate some help with the concept.

fgrieu

1/16/23, 7:02 PM

@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

1/16/23, 7:09 PM

@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

1/16/23, 8:56 PM

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.

Elon Musk

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

EN: Prove a function G is not a pseudo random generator

TH: พิสูจน์ว่าฟังก์ชัน G ไม่ใช่ตัวสร้างสุ่มหลอก

RO: Demonstrați că o funcție G nu este un generator pseudoaleator

RU: Докажите, что функция G не является псевдослучайным генератором.

VI: Chứng minh hàm G không phải là bộ tạo giả ngẫu nhiên

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.