My question is related to:

  1. How to contruct a pseudorandom with a specific property

  2. Collision in pseudorandom function when two different keys are used

Question: When we use a pseudorandom function to pad a message do we need to worry about the pseudorandom function's output range and the probability of collision?

Assume we blind (read: “add padding to”) a message $m$ as $r_1=m\cdot PRF(k,1)$, and next time we blind it as $r_2=m\cdot PRF(k',1)$, where $k,k'$ are two independent random keys. We give $r_1,r_2$ to an adversary.

If our PRF is not collision resistant then when $PRF(k,1)=PRF(k',1)$ then the adversary can learn the message $m$.

  • $\begingroup$ If the condition $PRF(k,1) = PRF(k',1)$ happens no more often than would be expected for a random function, that is, if it happens with probability $2^{-n}$, where the length of the PRF output is $n$ bits, then this is a nonissue $\endgroup$ – poncho Feb 1 '17 at 14:03
  • $\begingroup$ @poncho thank you for the comment. My question is then, why do we have the notion of collision-resistant PRF in the literature. see : download.springer.com/static/pdf/866/…*~hmac=4157c370f0b835e6e790f60d3e997e76cc93fcf501a440639db62ccd7790132c $\endgroup$ – user153465 Feb 1 '17 at 14:07

Your Answer

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

Browse other questions tagged or ask your own question.