How to implement a Cryptographic Pseudo Random Function

Question

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

The functions should map from

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

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

Subhayan · Accepted Answer · 2014-05-01 08:28:09Z

$f_s: d \rightarrow d$ bits is a Pseudorandom Permutation (see Luby-Rackoff Constructions)
$f_s: d \rightarrow 1$ bit is a Hardcore bit (see Goldreich Levin Theorem)
$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$

1 Answer 1