Do PRGs accept variable-length inputs?

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 :wink:


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 :slight_smile:
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 :slight_smile:
[/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.