]> Cryptography - Probability

Discrete Problems

Cryptography requires problems that are hard in the average case.

For our purposes, a probability space is a finite set Ω={0,1 } n, and a function Pr:2 Ω[0,1 ]. such that Pr[F]=Σ xFPr[x] for all FΩ.

(See the Wikipedia for the general definition of a probability space. Briefly, a probability space is a set S, a σ-algebra X on S, and a measure P on X such that P(S)=1 .)

Type 1 Random Variables

A Type 1 RV is a function X:ΩS, for some finite set S.

A predicate is a function Q(x):S{0,1 }, i.e. it maps the set to a boolean. Define Pr[Q(x)]=Σ yΩ,Q(X(y))Pr[y].

Some more notation:

  • XΩ defines a uniform random variable on Ω (X{0,1 } n). Formally, Pr[A]=A/Ω for any AΩ, X is the identity function, thus Pr[X=a]=1 /Ω for all aΩ.

  • A(x,r) denotes a randomized algorithm: x is the input, and r{0,1 } m=Ω is the randomness.

  • XA(y) denotes a random variable X as the output of the algorithm A on input y. Output of algorithm is a probability distribution.

  • For a predicate Q, define Pr[Q(x)xA(y)] as the probability that Q(x) holds for output of A on input y.

Example: Let A(n) be a randomized algorithm that outputs an odd prime less than or equal to n. Then

Pr[(Xp)=1 pA(n),X𝔽 p *]=1 /2

Type 2 Random Variables

A Type 2 RV is a function X:Ω.

We shall always use a uniform distribution on Ω, which means that for all r,

Pr[X=r]={yX(y)=r}/Ω

Define

E[X]=Σ yΩPr[y]X(y)

and

σ 2 (x)=E[X 2 ](E[X]) 2 =E[(XE[X]) 2 ].

X,Y are independent if for all a,b we have

Pr[X=aY=b]=Pr[X=a]Pr[Y=b].

Large Deviation Bounds

Markoff's Inequality:

Pr[X>λ]E[x]/λ.

Chebyshev's Inequality:

Pr[XE[X]λσ(X)]1 /λ 2 .

Example: Suppose X 1 ,...,X n are pairwise independent random variables such that Pr[X i=1 ]=p, Pr[X i=0 ]=1 p.

Chernoff Bound: For i=1 ,...,n, let x i=0 with probability p and x i=1 otherwise. Suppose the x i are independent (stronger than pairwise independent), and define X=Σ i=1 nx i. Then

Pr[XE[X]nλ]2 e 2 λ 2 .