Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Do PRGs accept variable-length inputs?
I can’t really decide whether the definition of a PRG in the slides 04_PRG.pdf, p. 3 allows variable-length input. Is the n fixed in the definition or is it somehow bound by a \forall?
In other words, is a PRG of type
- [m]{0,1}^n → {0,1}^{l(n)}[/m] for some fixed n and polynomial l,
- or [m]Πn. {0,1}^n → {0,1}^{l(n)}[/m] for some polynomial l, where Π binds dependently?
If it’s the second, then the inequality [m]|Pr[…] - Pr[…]| <= negl(n)[/m] is all-quantified in n, right?
Without looking at the slides:
I’d expect $\bin^n$ and $negl(n)$ to have $n$ as security parameter.
For variable length input I’d expect $\bin^*$ instead
It’s still for all choices of security parameter $n$ though
Excluded from the “Textbook” (Introduction to Modern Cryptography, Katz & Lindell, I just copied that from the 2007 edition):
EDIT: I swapped the picture with a working link
https://www.dropbox.com/s/ji145xku81t1h46/pic.png?dl=0
[quote=tyr]EDIT: I swapped the picture with something better
[/quote]
It seems you swapped it with an HTTP 401 error
For archival reasons, here is a permanent link, which will never cease to exist: https://imgur.com/a/gXPymT8
Well, but then it doesn’t make sense to require a polynomial [m]l[/m] associated with the running time, or does it?
[quote=Marcel[Inf]]
[quote=tyr]EDIT: I swapped the picture with something better
[/quote]
It seems you swapped it with an HTTP 401 error
[/quote]
Fixed it, I guess?
The original question is rather … weird to me.
Once you defined one specific PRG G, it only takes seeds of length n and outputs pseudorandom strings of length l(n).
[quote=Marcel[Inf]]
Well, but then it doesn’t make sense to require a polynomial [m]l[/m] associated with the running time, or does it?
[/quote]
The PRG has to be polynomial bound, otherwise we could simply generate true randomness.
Ex:
Given the string “ab” and generating the true randomness “c” to get “abc” is easy if one simply takes a random table, that maps every input to one single ouput. But that requires exponential space. Here it would take 26^2 many entries, starting with
aa | e
ab | c
ac | h
… | …
But we are interested in an efficient algorithm, a PRG that does something similar, but polynomial indistinguishable from that.