Cryptography

Cryptography requires problems that are hard in the average case.

For our purposes, a probability space is a finite set $\Omega =\{\mathrm{0,1}{\}}^n$, and a function $\mathrm{Pr}:2^{\Omega }\to [\mathrm{0,1}].$ such that $\mathrm{Pr}[F]={\Sigma }_{x\in F}\mathrm{Pr}[x]$ 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(S)=1$.)

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

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

Some more notation:

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

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

• $X\leftarrow A(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 $\mathrm{Pr}[Q(x)\mid x\leftarrow A(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

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

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}[X=r]=\mid \{y\mid X(y)=r\}\mid /\mid \Omega \mid$$

Define

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

and

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

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

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

Markoff's Inequality:

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

Chebyshev's Inequality:

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

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

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