Difference between revisions of "Pseudorandom number generators"

From Simulace.info
Jump to: navigation, search
Line 12: Line 12:
  
  
−
where <math>{U_m}</math> denotes a uniformly random string in <math>{{\{0, 1\}^m}}</math>. Here the string <math>{{U_l}}</math> is called the 'seed'. If <math>{{C}}</math> is a class of tests, we say that G '<math>{{\epsilon}}</math>-fools <math>{{C}}</math>' or is an '<math>{{\epsilon}}</math>-PRG against <math>{{C}}</math>' if <math>{{G}}</math> <math>{{\epsilon}}</math>-fools <math>{{f}}</math> for every <math>{{f \in C}}</math>.
+
where <math>{U_m}</math> denotes a uniformly random string in <math>{{\{0, 1\}^m}}</math>. Here the string <math>{{U_l}}</math> is called the 'seed'. If <math>{{C}}</math> is a class of tests, we say that G '<math>{{\epsilon}}</math>-fools <math>{{C}}</math>' or is an '<math>{{\epsilon}}</math>-PRG against <math>{{C}}</math>' if <math>{{G}}</math> <math>{{\epsilon}}</math>-fools <math>{{f}}</math> for every <math>{{f \in C}}</math>.<ref name="cmu">[http://www.cs.cmu.edu/~odonnell/complexity/docs/lecture16.pdf Lecture 16: Nisan's PRG for small space, 15-855: Intensive Intro to Complexity Theory. Spring 2009, Carnegie Mellon University, USA.]: page 1</ref>
  
−
[[File:secure_prf.png]]
+
[[File:secure_prf.png|center|x125px]]
  
  

Revision as of 20:12, 1 December 2012

In cryptography, a pseudorandom generator (or PSG) is procedure that outputs a sequence computationally indistinguishable from truly random sequence with uniformly distributed random sequence. The prefix pseudo (from Greek ψευδής "lying, false") is used to mark something as false, fraudulent, or pretending to be something it is not. Pseudo random generators find application in many fields besides cryptography such as applied mathematics, physics and simulations. Simulations often require mechanisms producing sequences of random values. These procedures are certainly non-trivial and often require significant amounts of computational time.


Definition

A pseudorandom generator (or PRG) is a (deterministic) map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G:\{0, 1\}^l \rightarrow \{0, 1\}^n}}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n \geq l}}} . Here Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{l}}} is the 'seed length' and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n - l \geq 0}}} is the 'stretch'. We typically think that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n \gg l}}} and that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G}}} is effciently computable in some model. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f:\{0, 1\}^n \rightarrow \{0, 1\}}}} is any 'statistical test', we say that G 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools' Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f}}} is


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{|Pr[f({U_n} = 1)] - Pr[f(G({U_l})) = 1)]| \leq \epsilon}}}


where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {U_m}} denotes a uniformly random string in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\{0, 1\}^m}}} . Here the string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{U_l}}} is called the 'seed'. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} is a class of tests, we say that G 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} ' or is an 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -PRG against Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} ' if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G}}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f}}} for every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f \in C}}} .[1]

Secure prf.png


Example

First of all let’s start with pseudorandom functions. A pseudorandom function is any function defined over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal(K, X, Y)}}}  :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{F:K \times X \rightarrow Y}}}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{K}}} is key space
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{X}}} is input space
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{Y}}} is output space

such that exists efficient algorithm to evaluate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal F(k,x)}}} .[2]


On the other hand pseudorandom permutation is any function defined over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal(K, X)}}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{E:K \times X \rightarrow X}}}

such that[2]:

  1. Exists efficient deterministic algorithm to evaluate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal E(k,x)}}}
  2. The function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal F(k,\cdot)}}} is one-to-one
  3. Exists efficient inversion algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal D(k,y)}}}


Any pseudorandom permutation is also pseudorandom function given

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{X=Y}}}
  2. Function is efficiently invertible

References

  1. ↑ Lecture 16: Nisan's PRG for small space, 15-855: Intensive Intro to Complexity Theory. Spring 2009, Carnegie Mellon University, USA.: page 1
  2. ↑ 2.0 2.1 Boneh, D. (2012); Lecture 3 - Block ciphers, Introduction to Cryptography. Stanford, USA.
Retrieved from "http://www.simulace.info/index.php?title=Pseudorandom_number_generators&oldid=1602"