# Pseudorandom generator designs

When designing pseudorandom generators what should one consider? Here is an example pseudorandom generator $$F^t : \{0,1\}^n \rightarrow \{0,1\}^{4n}$$. I have no idea what it means, so what does it kindly mean? It is one proposal written in a book for the truly random compression function $$t : \{0,1\}^{2n} \rightarrow \{0,1\}^n$$

Like how would I design one for truly random compression function such as $$t : \{0,1\}^{2n} \rightarrow \{0,1\}^n$$?

It just defines a function that expands the input size with the output size four times, where the output depends on configuration value $$t$$ as well. The hash function compresses the input to an output that is half the size (which is not common, usually a hash function outputs a constant size hash).
Here ^ is not a power function. It simply shows how many elements there are sequentially taken from the input set $$\{0, 1\}$$ - properly formatted it reads $$\{0, 1\}^{4 \cdot n}$$. So the $$x$$ in $$\{0, 1\}^x$$ simply defines an input or output consisting of $$x$$ bits - with value $$0$$ or $$1$$ of course.
• Thanks for your answer Sir! So basically, what you are saying is that with a PRG, it takes a fixed size n and then outputs 4 times n? Also, how would I design a PRG for the random compression function listed in my question? – jezd0rman70rzz Dec 3 '18 at 0:28
• Not a fixed size, no. If the size were fixed, even for a single call, then you would add $n$ to the configuration parameters. It simply expands any input to two times the size, the way I read it (context is important though, maybe $n$ is set to a value elsewhere). I don't think you should use a PRG such as this to create a hash function - was that actually a question? – Maarten Bodewes Dec 3 '18 at 0:32
• I'm trying to come up with a PRG based on the random compression function t : {0,1}^2n -> {0,1}^n. The thing is, I didn't know anything about PRGs but just to get things started a PRG always start like F^t : {0,1}^n? The last bit -> {0,1}^xn where x is a number is how it ends right? I just wanna design a PRG for the random compression function. Just out of interest, why is the mentioned random compression function not a block cipher either? – jezd0rman70rzz Dec 3 '18 at 0:37
• You seem to make two different requests now, creating a PRG based on a compression function and the other way around. A block cipher is a PRP, which is always $F_k: \{0, 1\}^n \to \{0, 1\}^n$ because there has to be a $F^{-1}_k$: encryption and decryption. – Maarten Bodewes Dec 3 '18 at 0:46