Security of the encryptions, using a PRG for the keyGen

Question

I recently got doubtful about the usefulness of pseudorandom generators (PRG) in cryptography.

Based on Kerckhoffs's principle, we always assume that the used algorithms are made public. So, when we use a PRG to generate a long key from a short key, we are broadcasting the PRG algorithm too.

When we use the output of a PRG as the key for a symmetric key encryption, doesn't it mean that the adversary still only needs to check exhaustively the space of the seed? If so, what's the merit of using a PRG? (I know that the output of a PRG must be indistinguishable from a truly random sequence, but based on what I explained, I think it is not important since I think the space of their input plays the main role in the security of encryptions not the space of their output.)

One more question is whether the length of the seed is important.

The encryption method that made me sceptical is an encryption scheme which works only by different rounds of permutations sequentially (i.e., it divides the message into blocks, permutes the blocks, and then permutes the bits within each block). Both keys are completely pseudorandom.

Answer 1

Doesn't it mean that the adversary still only needs to check exhaustively the space of the seed?

Yes, any adversary could do this. But the seed is the "smaller" private key. And this private key is the secret regarding the principles of Kerkhoff. Today's cryptography assumes that a secret key with length 128 or even 256 is big enough so that no adversary can exhaustively check the values in a reasonable amount of time. I mean he would have to look at $2^{128}$ or $2^{256}$ values.

That also answers your second question. Yes the length of the original key is very important, because it sets the security. If the key is to small, say 16 bit, it is very easy to look at every values.

But why are PRG important anyway? First of all it is very interesting for theoretical cryptography, to understand this better I recommend Katz & Lindell's textbook (2nd edition). For practical applications one benefit is, that a shorter key can be stored. An example is the One-Time-Pad, which normally has a key as long as the message. With a PRG you can use a much smaller key and still use the principle of OTP.

Note: PRG are normally not used for the creation of the needed entropy for a secure secret key. This is can be done by secure random number generators and the PRG may be built on top of it, but not as the source of good entropy.