Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
Short answer? No. For (2) take look at hardcore bits (wiki) –  rath Apr 29 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 at 15:57
2  
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 at 16:58

1 Answer 1

  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

 
discard

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.