Cryptography

These come in three flavours:

• $A$ is a deterministic polynomial-time algorithm if there exists a polynomial $P_A(\lambda )$ such that for all inputs $X$ of length $\lambda$, ${\mathrm{TIME}}_A(X)\le P_A(\lambda )$.

• A probabilistic strict polynomial-time algorithm $A$ has the same definition as above except that $A$ may flip coins.

• A probabilistic expected polynomial-time algorithm $A$ has the same definition as above except $E[{\mathrm{TIME}}_A(X)]\le P_A(\lambda )$.

As above, but running bounds should hold for all inputs and all input communication messages.

A function $f:{\mathbb{Z}}_{\ge 0}\to {ℝ}_{\ge 0}$ is negligible if for all $c>0$, there exists a ${\lambda }_0>0$ such that for all $\lambda \ge {\lambda }_0$, $f(\lambda )<1/{\lambda }^c$.

Example: $2^{-\lambda },{\lambda }^{-\log \lambda }$ are negligible, ${\lambda }^{-1000000}\mathrm{is}\mathrm{nonnegligible}$

[cf. Dan's definition: A function $g(t):{\mathbb{Z}}^{+}\to {ℝ}^{+}$ is negligible if for all polynomials $h\in {\mathbb{Z}}^{+}[x]$ we have that $g(t)<1/h(t)$ for sufficiently large $t$. ]