1
$\begingroup$

It seems that the minimal size of Pseudorandom permutation (PRP) output is $128$ bits. In general, I'd like to see if there's any minimal size of the output of pseudorandom function (PRF) as well? for instance can we set the output size of PRF to 32 or 40 bits.

Below, I'm trying to explain the question with an example.


Let $k_i$ be secure random key. I've a message $m$ of 32-bit. I want to encrypt it in two different ways:

  1. Using output of a pseudorandom function (PRF) as a one time pad: I do the following:

    a) $PRF_{k_1}(0)=a$,

    b) $c_1=a \cdot m$.

  2. Using a Pseudorandom permutation (PRP):

    a) $c_2=PRP_{k_2}(m)$


Question 1: What is the minimal size of $c_1$? Can we set the output size of PRF to 32 bits, so the size of $c_1$ would be the same?

Question 2: what is the minimal size of $c_2$? Am I right it is at least 128 bits?

Question 3: If the answer to both questions is positive, then how can we compare the security and efficiency of the above two schemes with each other?


Please kindly let me know if my question is not clear, etc instead of down voting it; and I'll address your comments.

$\endgroup$
2
$\begingroup$

Answer 1: If you are going to use a "one time pad", then $c1$ must be exactly the same size as $m$, so $c1$ must be 32 bits. (Note: Using a PRF and evaluating with the input of 0 is not a one-time pad. It might be equivalent if you change $k_i$ every time, but then why bother with the PRF when you could use $k_i$ directly?)

Answer 2: Since you specific it as a PRP (pseudorandom permutation), $c2$ must be 32-bits. With a permutation, the size of the input matches the size of the output. A PRP pseudorandomly maps each element of the possible input set to a single item in the output set. So as with the first, $m$ and $c$ must be exactly the same size.

Answer 3: There isn't sufficient information about the rest of the system or usage to really comment on their security with the exception to say: trying to make a "one-time pad" from other function almost always fails and anything that has only a 32-bit input can probably be trivially brute forced.

$\endgroup$
  • $\begingroup$ thanks for the answer. My comments are as follows: 1- "anything that has only a 32-bit input can probably be trivially brute forced" --> but we are using a uniformly random and sufficiently long key for PRF. Do you think if there's still a problem? 2- "c_2 must be 32 bits" --> isn't the case that the minimal AES output is 16 bytes or 128 bits? if that's the case then $c_2$ size would be 128. Thanks! $\endgroup$ – Ay. Jan 22 at 9:51
  • 1
    $\begingroup$ @Ay. Your question does not mention AES, it only mentions PRPs generically. If you wanted information about AES specifically, then you should include that point in the body of your question. $\endgroup$ – Ella Rose Jan 22 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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