Join Log in
Score:0
cryptonoob avatar Crypto

Determine if a function is a PRG when PRG concatenated with Seed?

bd flag
cryptonoob

I am a newbie in Cryptography and have trouble to solve the following question.

Let $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ be a PRG and $x \epsilon \{0,1 \}^n$. Determine if the function $Z: \{0,1 \}^n \rightarrow \{0,1 \}^{(l(n)+n)}$ s.t. $Z(x) := G(x)||x$ is also a PRG.

My first assumption was that it is a PRG, because the concatenation of the PRG Output G(x) as pseudorandomstring with a uniformly distributed random String x is also a random string. Hence, it can also not be distinguished by an adversary. Furthermore l(n)+n > n, so Expansion is also ok.

How can i prove that? My idea is a Reduction that if there is a distinguisher D who breaks Z(x) would break also G(x) with non-negl probability, which contradicts the initial assumption that G(x) is a PRG.

Am i on the right track or completely lost?

223
0 + 6
Maarten Bodewes avatar
in flag
Maarten Bodewes
So your function Z is outputting the seed together with the random values derived from it? The algorithm is known as well.
1
Reply
cryptonoob avatar
bd flag
cryptonoob
@MaartenBodewes Yes, exactly. But what do you mean with "algorithm is known as well"? G ist not specified any further. Therefore, if I need to give a counterexample for the case that Z is not a PRG, I can design G however I want.
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
No, this is not usually correct. We generally assume Kerckhoff's principle: any security is not in the algorithm but in the key or - in this case - seed. You can design $G$ however you want, but you should assume that any adversary knows the algorithm. In other words: you cannot assume $G$ to generate any secrecy besides the seed $x$. Now what would happen if you first generate a key and then an IV using $Z$?
0
Reply
SEJPM avatar
us flag
SEJPM
Hint: Is there perhaps some kind of test / distinguisher that can check whether a given random-looking string is coming from $Z$ or just plain random? Assume the adversary can compute $G$ as well.
2
Reply
cryptonoob avatar
bd flag
cryptonoob
@MaartenBodewes The only idea that i have is that an adversary can get the key/seed from the output of Z by performing a cut (because adversary knows the algorithm and knows that the key has a length of n). Then he can input this "key" into the function and check whether it is the same output or not. As far as I know, a PRG is deterministic. And in this case he even knows the key. Right track?
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
Yeah, that's the right track. Generally it should not be possible to derive the state of the RNG as it would leak information about all the other bytes in the stream.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.