I need three pseudo random functions which all take a seed S (t-bits long).

The functions should map from

  1. $d$ bits to $d$ bits
  2. $d$ bits to $1$ bit
  3. $d$ bits to $t$ bits

$d$ is $10$ bits
$t$ is $2048$ bits

Can you link me to some c++ implementation(or any language) or tell me how to implement it?

  • 1
    $\begingroup$ Short answer? No. For (2) take look at hardcore bits (wiki) $\endgroup$ – rath Apr 29 '14 at 14:57
  • $\begingroup$ With just 10 bits of input, an attacker simply precomputing all possible values of $d$ would render your values very predictable indeed - especially for 3 $\endgroup$ – Cryptographeur Apr 29 '14 at 15:57
  • 2
    $\begingroup$ I prefer a two phase function: 1) Extract - Hash the seed and the input to a fixed size (say 256 bits) 2) Expand - Use a stream cipher to expand that key to whatever size you want. | You can use HKDF for this. $\endgroup$ – CodesInChaos Apr 29 '14 at 16:58
  1. $f_s: d \rightarrow d$ bits is a Pseudorandom Permutation (see Luby-Rackoff Constructions)

  2. $f_s: d \rightarrow 1$ bit is a Hardcore bit (see Goldreich Levin Theorem)

  3. $f_s: d \rightarrow t$ bits is a Pseudorandom Generator. (assuming $t$ is a function of $d$) (see Goldreich Goldwasser Micali)

(All these topics are coved in the Katz-Lindell book.)

With these constructions known, you'll be writing provably secure constructions for the crypto primitives.

Also, please forgive my abuse of notation here, when i write $f_s: x \rightarrow y$, what I really mean is $f: x \times s \rightarrow y$


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.