# How to implement a Cryptographic Pseudo Random Function

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?

• Short answer? No. For (2) take look at hardcore bits (wiki) – rath Apr 29 '14 at 14:57
• 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 – Cryptographeur Apr 29 '14 at 15:57
• 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. – 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)
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$