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.