Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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 – figlesquidge 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)

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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