Reference
Notation and Glossary
The eight chapters share a vocabulary. This page collects the notation, security notions and abbreviations in one place for quick reference.
Section 1General Conventions
$\lambda$ denotes the security parameter throughout, and all algorithms are implicitly given $1^\lambda$. An algorithm is efficient if it runs in probabilistic polynomial time in $\lambda$, abbreviated PPT.
A function $\nu$ is negligible if it shrinks faster than any inverse polynomial: for every $c > 0$ there is $\lambda_0$ such that $\nu(\lambda) < \lambda^{-c}$ for all $\lambda > \lambda_0$. This is written $\nu(\lambda) \le \negl(\lambda)$. Computational security rests on this notion: a scheme is secure when every efficient adversary's advantage is negligible; the advantage need not be zero.
Security is stated as a game between an adversary and a challenger. The adversary wins by distinguishing two worlds, or by producing a forgery. A scheme is secure when no efficient adversary wins with probability non-negligibly better than guessing.
| Symbol | Meaning | First used |
|---|---|---|
| $\lambda$ | Security parameter; key lengths and running times are measured against it | Chapter 1 |
| $\negl(\lambda)$ | Some negligible function of $\lambda$ | Chapter 1 |
| $\poly(\lambda)$ | Some polynomially bounded function of $\lambda$ | Chapter 1 |
| $\bits^n$ | The set of bit strings of length exactly $n$ | Chapter 1 |
| $\bits^*$ | Bit strings of any finite length | Chapter 1 |
| $x \getsr S$ | $x$ drawn uniformly at random from the finite set $S$ | Chapter 1 |
| $x \leftarrow \mathcal{A}(y)$ | $x$ is the output of running algorithm $\mathcal{A}$ on input $y$ | Chapter 1 |
| $\oplus$ | Bitwise exclusive or | Chapter 1 |
| $x \| y$ | Concatenation of strings $x$ and $y$ | Chapter 1 |
| $|x|$ | Length of a string, or cardinality of a set | Chapter 1 |
| $[n]$ | The set $\{1, 2, \dots, n\}$ | Chapter 1 |
| $\approx_c$ | Computational indistinguishability | Chapter 1 |
| $\Pr[\,E\,]$ | Probability of event $E$ | Chapter 1 |
Colors are consistent across every page. Alice, the sender, is blue. Bob, the receiver, is cyan. Eve, the adversary, is red. Keys and secrets are yellow. Randomness and noise are purple. Trusted third parties and oracles are magenta. Something proved secure is green.
Section 2Primitives and Schemes
| Symbol | Meaning |
|---|---|
| $\Enc(k, m)$ | Encryption of message $m$ under key $k$ |
| $\Dec(k, c)$ | Decryption of ciphertext $c$ under key $k$ |
| $\Tag(k, m)$ | Message authentication code (MAC) tag on message $m$ under key $k$ |
| $\Hash(x)$ | A cryptographic hash function applied to $x$ |
| $\PRF(k, x)$ | A pseudorandom function keyed by $k$ |
| $\mathbf{G}(s)$ | A pseudorandom generator on seed $s$ |
| $\mathcal{M}, \mathcal{C}, \mathcal{K}$ | Message, ciphertext and key spaces |
| $(pk, sk)$ | A public-key / secret-key pair |
| $\mathrm{IV}$ | Initialization vector, for a mode of operation |
| $\tau$ | An authentication tag |
| $\mathbf{cmps}$ | A fixed-input-length compression function |
Security Notions
| Abbreviation | Notion | What the adversary may do |
|---|---|---|
| OT / one-time | One-time security | See one ciphertext; no queries |
| CPA | Chosen-plaintext attack | Request encryptions of chosen messages |
| CCA | Chosen-ciphertext attack | Also request decryptions, except of the challenge |
| UF-CMA | Unforgeability under chosen-message attack | Request tags, then forge on a fresh message |
| AE | Authenticated encryption | Confidentiality and integrity together |
| CR | Collision resistance | Find $x \ne x'$ with $\Hash(x) = \Hash(x')$ |
Weak collision resistance fixes $x$ and asks for a colliding $x'$; it costs roughly $L$ queries for an output space of size $L$. Strong collision resistance lets the adversary choose both inputs, so the birthday bound brings the cost down to about $\sqrt{L}$. This factor is why a 128-bit digest gives only 64-bit collision security.
Section 3Algebra and Number Theory
| Symbol | Meaning |
|---|---|
| $\Z, \R$ | The integers; the reals |
| $\Z_N$ | Integers modulo $N$ |
| $\Z_N^*$ | The multiplicative group of units modulo $N$ |
| $\varphi(N)$ | Euler's totient: the size of $\Z_N^*$ |
| $\gcd(a,b)$ | Greatest common divisor; $a, b$ are coprime when it is $1$ |
| $\GF(2^8)$ | The finite field with $256$ elements, used by AES (Advanced Encryption Standard) |
| $h(X)$ | Rijndael's irreducible polynomial $X^8 + X^4 + X^3 + X + 1$ |
| $\mathbb{G}, g$ | A cyclic group and a generator of it |
| $e(\cdot,\cdot)$ | A bilinear pairing: $e(g^a, g^b) = e(g,g)^{ab}$ |
| $\Zq^{n \times m}$ | Matrices over $\Zq$, used throughout lattice cryptography |
| $\Lambda$ | A lattice: all integer combinations of a basis |
| $\|v\|$ | Euclidean norm of a vector |
| $\lambda_1(\Lambda)$ | Length of a shortest nonzero lattice vector |
$\lambda$ is the security parameter, but $\lambda_1(\Lambda)$ is the first successive minimum of a lattice. They are unrelated. The subscript and the lattice argument distinguish them; Chapter 4 is the only place both appear together.
Hardness Assumptions
| Name | Problem | Chapter |
|---|---|---|
| Factoring | Given $N = pq$, recover $p$ and $q$ | 2 |
| RSA | Given $(N, e, y)$, find $x$ with $x^e \equiv y \bmod N$ | 2 |
| DLog | Discrete logarithm: given $g^x$, recover $x$ | 2 |
| CDH | Computational Diffie-Hellman: given $g^a, g^b$, compute $g^{ab}$ | 2 |
| DDH | Decisional Diffie-Hellman: distinguish $(g^a, g^b, g^{ab})$ from $(g^a, g^b, g^c)$ | 2 |
| LPN | Learning parity with noise | 3 |
| SIS | Short integer solution: find a short nonzero $z$ with $Az \equiv 0 \bmod q$ | 4 |
| LWE | Learning with errors: distinguish $(A, As + e)$ from uniform, for small error $e$ | 4 |
| SVP / CVP | Shortest and closest vector problems in a lattice | 4 |
Section 4Differential Privacy
| Symbol | Meaning |
|---|---|
| $\eps$ | Privacy parameter; smaller means more private and less accurate |
| $\delta$ | Failure probability in approximate $(\eps,\delta)$-DP |
| $D \sim D'$ | Neighboring databases, differing in one individual's record |
| $\Delta f$ | Global sensitivity: $\max_{D \sim D'} |f(D) - f(D')|$ |
| $\Lap(b)$ | The Laplace distribution with scale $b$ |
| $\mathcal{M}(D)$ | A randomized mechanism applied to database $D$ |
| $q$ | One query or a query count, depending on context |
A randomized mechanism $\mathcal{M}$ is $(\eps, \delta)$-differentially private if for all neighboring databases $D \sim D'$ and all measurable sets $S$ of outputs,
$$\Pr[\mathcal{M}(D) \in S] \;\le\; e^{\eps}\,\Pr[\mathcal{M}(D') \in S] + \delta.$$When $\delta = 0$ this is pure $\eps$-differential privacy. The guarantee is about the mechanism, and holds for every pair of neighboring databases and every adversary, regardless of auxiliary information.
Section 5Blockchain and Multiparty Computation
| Term | Meaning | Chapter |
|---|---|---|
| UTXO | Unspent transaction output; Bitcoin's unit of value | 6 |
| Proof of work | Finding a nonce (a one-use number chosen by the miner) whose block hash falls below a target | 6 |
| Difficulty | Inverse of the target; retargeted to hold block time steady | 6 |
| Fork | Competing valid branches; Bitcoin nodes choose the branch with the most cumulative proof of work | 6 |
| Orphan / stale block | A valid block excluded from the branch with the most cumulative proof of work | 6 |
| Selfish mining | Withholding blocks to orphan honest work | 6 |
| Proof of stake | Leader election weighted by held stake in place of work | 7 |
| Sortition | Cryptographic sampling of a committee | 7 |
| Nullifier | A value published to spend a shielded note exactly once | 7 |
| MPC | Secure multiparty computation | 8 |
| OT | Oblivious transfer; complete for MPC | 8 |
| Semi-honest | Adversary follows the protocol but tries to learn more | 8 |
| Malicious | Adversary may deviate arbitrarily from the protocol | 8 |
| Simulator | Algorithm producing an indistinguishable view in the ideal world | 8 |
| $(t, n)$-threshold | Any $t+1$ of $n$ shares reconstruct; any $t$ reveal nothing | 8 |
Many definitions in this course compare two worlds: real ciphertext versus random, real protocol versus ideal functionality, database $D$ versus its neighbor $D'$ and a pseudorandom function versus a truly random function. Recognizing this pattern helps reconstruct the definitions during an exam.