]> Cryptography - Probability

## Discrete Problems

Cryptography requires problems that are hard in the average case.

For our purposes, a probability space is a finite set $\Omega =\left\{0,1{\right\}}^{n}$, and a function $\mathrm{Pr}:{2}^{\Omega }\to \left[0,1\right].$ such that $\mathrm{Pr}\left[F\right]={\Sigma }_{x\in F}\mathrm{Pr}\left[x\right]$ for all $F\subseteq \Omega$.

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

## Type 1 Random Variables

A Type 1 RV is a function $X:\Omega \to S$, for some finite set $S$.

A predicate is a function $Q\left(x\right):S\to \left\{0,1\right\}$, i.e. it maps the set to a boolean. Define $\mathrm{Pr}\left[Q\left(x\right)\right]={\Sigma }_{y\in \Omega ,Q\left(X\left(y\right)\right)}\mathrm{Pr}\left[y\right]$.

Some more notation:

• $X←\Omega$ defines a uniform random variable on $\Omega$ ($X←\left\{0,1{\right\}}^{n}$). Formally, $\mathrm{Pr}\left[A\right]=\mid A\mid /\mid \Omega \mid$ for any $A\subseteq \Omega$, $X$ is the identity function, thus $\mathrm{Pr}\left[X=a\right]=1/\mid \Omega \mid$ for all $a\in \Omega$.

• $A\left(x,r\right)$ denotes a randomized algorithm: $x$ is the input, and $r\in \left\{0,1{\right\}}^{m}=\Omega$ is the randomness.

• $X←A\left(y\right)$ 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 $\mathrm{Pr}\left[Q\left(x\right)\mid x←A\left(y\right)\right]$ as the probability that $Q\left(x\right)$ holds for output of $A$ on input $y$.

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

$\mathrm{Pr}\left[\left(\frac{X}{p}\right)=1\mid p←A\left(n\right),X←{𝔽}_{p}^{*}\right]=1/2$

## Type 2 Random Variables

A Type 2 RV is a function $X:\Omega \to ℝ$.

We shall always use a uniform distribution on $\Omega$, which means that for all $r\in ℝ$,

$\mathrm{Pr}\left[X=r\right]=\mid \left\{y\mid X\left(y\right)=r\right\}\mid /\mid \Omega \mid$

Define

$E\left[X\right]={\Sigma }_{y\in \Omega }\mathrm{Pr}\left[y\right]X\left(y\right)$

and

${\sigma }^{2}\left(x\right)=E\left[{X}^{2}\right]-\left(E\left[X\right]{\right)}^{2}=E\left[\left(X-E\left[X\right]{\right)}^{2}\right].$

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

$\mathrm{Pr}\left[X=a\wedge Y=b\right]=\mathrm{Pr}\left[X=a\right]\mathrm{Pr}\left[Y=b\right].$

## Large Deviation Bounds

Markoff's Inequality:

$\mathrm{Pr}\left[X>\lambda \right]\le E\left[\mid x\mid \right]/\lambda .$

Chebyshev's Inequality:

$\mathrm{Pr}\left[\mid X-E\left[X\right]\mid \ge \lambda \sigma \left(X\right)\right]\le 1/{\lambda }^{2}.$

Example: Suppose ${X}_{1},...,{X}_{n}$ are pairwise independent random variables such that $\mathrm{Pr}\left[{X}_{i}=1\right]=p$, $\mathrm{Pr}\left[{X}_{i}=0\right]=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={\Sigma }_{i=1}^{n}{x}_{i}.$ Then

$\mathrm{Pr}\left[\mid X-E\left[X\right]\mid \ge \sqrt{n}\lambda \right]\le 2{e}^{-2{\lambda }^{2}}.$