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$?


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Commented Dec 3, 2018 at 0:28
  • $\begingroup$ 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? $\endgroup$
    – Maarten Bodewes
    Commented Dec 3, 2018 at 0:32
  • $\begingroup$ 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? $\endgroup$ Commented Dec 3, 2018 at 0:37
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Dec 3, 2018 at 0:46
  • $\begingroup$ Sorry sir for confusion. So basically, you have mentioned a interesting fact about a block cipher being a PRP (I'm learning something new today! You made my day honestly!!) My question is why the truly random compression function Fk : {0,1} ^ 2n -> {0,1} ^ n isn't a block cipher?? I am so sorry if I sound really stupid (I am very stupid at crypto, maths in general) and so sorry for writing it like a noob. BTW what is a PRP?? So sorry I am new to crypto and IT advance as a whole $\endgroup$ Commented Dec 3, 2018 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.