Cryptography

Cryptography is the mathematics of secure communication — the study of how information can be transformed so that only its intended recipients can read it, even in the presence of adversaries who intercept every transmission. What began as a craft of substituting letters and scrambling words has become, over the past half-century, one of the deepest applications of abstract algebra, number theory, and computational complexity. Today’s cryptographic systems protect banking, elections, private messages, and the entire infrastructure of the internet, all resting on the hardness of a handful of mathematical problems that humanity does not yet know how to solve efficiently.

Classical Cryptography and Symmetric Encryption

The oldest cryptographic systems belong to a tradition stretching back thousands of years, relying on the secrecy of a shared key known to both sender and receiver. The Caesar cipher, named for Julius Caesar’s documented use of it, shifts each letter of the plaintext forward by a fixed number of positions in the alphabet. With a shift of three, the word MATH becomes PDWK. The key is simply that number. Such a scheme is trivially broken by frequency analysis — the observation, developed into a systematic technique by the ninth-century Arab polymath al-Kindi, that different letters appear with characteristic frequencies in any natural language. In English, the letter E accounts for roughly 13% of all characters; if the most frequent ciphertext symbol occurs at that rate, it almost certainly encodes E.

The Vigenère cipher attempted to defeat frequency analysis by using a repeating keyword rather than a single shift. Each letter of the keyword specifies a different shift for the corresponding plaintext letter, producing a polyalphabetic substitution that flattens the frequency distribution. For centuries it was considered unbreakable — the polymath Blaise de Vigenère published it in 1586 and it earned the nickname “le chiffre indéchiffrable.” Charles Babbage (and independently Friedrich Kasiski in 1863) broke it by detecting the period of the keyword through repeated trigrams, reducing the problem to multiple single-shift ciphers.

The mathematical capstone of classical cryptography is perfect secrecy, defined precisely by Claude Shannon in his landmark 1949 paper “Communication Theory of Secrecy Systems.” Shannon showed that a cipher provides perfect secrecy if and only if observing the ciphertext conveys zero information about the plaintext — formally, if the plaintext and ciphertext are statistically independent. The one-time pad achieves perfect secrecy: the key is a truly random string of the same length as the plaintext, and encryption is performed by XOR-ing plaintext with key. Decryption reverses the XOR. Because every key is equally likely and each key produces a different plaintext, a ciphertext is consistent with every possible plaintext of the correct length. Shannon proved that any perfectly secure cipher must use a key at least as long as the message, which makes the one-time pad impractical for most uses — but the theoretical benchmark it sets is the standard against which all other schemes are measured.

Modern symmetric cryptography achieves practical security through block ciphers, which process fixed-size blocks of plaintext (typically 128 bits) using a secret key. The Advanced Encryption Standard (AES), selected by the US National Institute of Standards and Technology (NIST) in 2001 after an open international competition, operates over a $4 \times 4$ array of bytes and applies a sequence of round functions, each consisting of byte-level substitution (SubBytes), row rotation (ShiftRows), column mixing (MixColumns), and key addition (AddRoundKey). The mathematical foundation is the field $\mathbb{F}_{2^8}$, the field of 256 elements used to represent bytes, where multiplication follows the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$ over $\mathbb{F}_2$. AES with a 128-bit key runs 10 rounds; with 256 bits, 14 rounds. No attack significantly better than brute force is known against the full cipher.

A block cipher alone specifies only how to encrypt a single block; modes of operation determine how to handle messages of arbitrary length. The naive Electronic Codebook (ECB) mode, which encrypts each block independently, is notoriously insecure: identical plaintext blocks produce identical ciphertext blocks, revealing pattern information. Cipher Block Chaining (CBC) XORs each plaintext block with the previous ciphertext block before encryption, breaking up patterns at the cost of sequential processing. Counter (CTR) mode turns the block cipher into a stream cipher by encrypting successive values of a counter and XOR-ing the output with plaintext, enabling parallel encryption. Galois/Counter Mode (GCM) adds authentication, producing both ciphertext and a message authentication code (MAC) that detects any tampering.

Cryptographic Hash Functions

A cryptographic hash function is a deterministic function $H$ that maps an input of arbitrary length to a fixed-length output called the digest or hash, typically 256 or 512 bits, satisfying three security properties that make it behave like a one-way function. Preimage resistance means that given a hash value $h$, it is computationally infeasible to find any input $x$ with $H(x) = h$. Second preimage resistance means that given a specific input $x$ and its hash $H(x)$, it is infeasible to find a different input $x' \neq x$ with $H(x') = H(x)$. Collision resistance is the strongest condition: it must be infeasible to find any pair $x \neq x'$ with $H(x) = H(x')$, even when the attacker has complete freedom to choose both inputs.

The birthday paradox governs collision resistance quantitatively. Because hash outputs are uniformly distributed across $2^n$ values, a random collision will be found with probability around one-half after approximately $2^{n/2}$ evaluations — not $2^n$ as naive intuition might suggest. This means a 256-bit hash provides roughly $2^{128}$ security against collision attacks, and a 512-bit hash provides $2^{256}$.

The workhorse construction underlying the SHA-2 family (SHA-256 and SHA-512) is the Merkle-Damgård construction: the input is padded, divided into fixed-size blocks, and processed sequentially by a compression function $f$ that takes the current state and the next block and produces a new state. The final state is the hash. If $f$ is collision-resistant, the construction is collision-resistant for inputs of the same padded length. SHA-3, standardized in 2015, uses an entirely different design: the sponge construction built on a fixed permutation of a large state (the Keccak-f permutation), absorbing input blocks and squeezing out output bits. The sponge provides a clean security proof and avoids the length-extension vulnerability inherent to Merkle-Damgård.

Hash functions serve as the backbone of message authentication codes. The HMAC construction

$\text{HMAC}(K, m) = H\bigl((K \oplus \textit{opad}) \;\|\; H((K \oplus \textit{ipad}) \;\|\; m)\bigr)$

takes a secret key $K$, applies two padded variants of it as outer and inner keys, and produces a tag that can only be verified by someone who knows $K$. HMAC is provably secure as long as the underlying hash function is a pseudorandom function. Password hashing functions like Argon2 and bcrypt are deliberately expensive to compute, using large amounts of memory and CPU time to resist brute-force and GPU-accelerated attacks on stolen password databases.

Public-Key Cryptography and RSA

The conceptual breakthrough of the 1970s was public-key cryptography, independently conceived by Whitfield Diffie and Martin Hellman (1976) and, earlier but secretly, by James Ellis and Clifford Cocks at GCHQ. The idea is revolutionary: a user generates two mathematically related keys, a public key that can be freely distributed and a private key that is kept secret, such that anything encrypted with the public key can only be decrypted with the private key and vice versa. Two strangers who have never met can establish a shared secret over a completely public channel.

The first practical realization of this idea was the RSA cryptosystem, introduced by Rivest, Shamir, and Adleman in 1977. Key generation proceeds as follows: choose two large distinct primes $p$ and $q$, compute the modulus $n = pq$, and compute Euler’s totient $\phi(n) = (p-1)(q-1)$. Choose a public exponent $e$ with $\gcd(e, \phi(n)) = 1$ and compute the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$. The public key is $(n, e)$ and the private key is $d$ (together with $p$ and $q$). To encrypt a message $m$ (represented as an integer with $0 \leq m < n$):

$c \equiv m^e \pmod{n}$

To decrypt:

$m \equiv c^d \pmod{n}$

Correctness follows from Euler’s theorem: since $ed \equiv 1 \pmod{\phi(n)}$, we have

$c^d \equiv (m^e)^d = m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \pmod{n}$

for any integer $k$, provided $\gcd(m, n) = 1$ (which holds with overwhelming probability for a random message). The security of RSA rests on the integer factorization problem: factoring the public modulus $n$ into $p$ and $q$ is believed to be computationally hard when $p$ and $q$ are large primes (2048 bits or more in current practice). No polynomial-time classical algorithm for factoring is known, and the best algorithms — the General Number Field Sieve — run in sub-exponential time $\exp\!\bigl(O((\log n)^{1/3}(\log \log n)^{2/3})\bigr)$.

Textbook RSA as described above is insecure in practice because it is deterministic and malleable. Padding schemes fix this: OAEP (Optimal Asymmetric Encryption Padding) introduces randomness before encryption and is provably secure in the random oracle model against chosen ciphertext attacks. Real deployments always use OAEP or similar schemes rather than raw modular exponentiation.

The Diffie-Hellman key exchange solves a related problem: how can two parties who share only public information agree on a secret key? Fix a large prime $p$ and a generator $g$ of the multiplicative group $\mathbb{Z}_p^*$. Alice chooses a private integer $a$ and sends $g^a \bmod p$; Bob chooses $b$ and sends $g^b \bmod p$. Both compute the shared secret $g^{ab} \bmod p$. An eavesdropper sees $g^a$ and $g^b$ but must solve the discrete logarithm problem — recovering $a$ from $g^a \bmod p$ — to recover the secret. The hardness of this problem underlies Diffie-Hellman and its many descendants.

Elliptic Curve Cryptography

The same discrete logarithm problem can be posed in a far more compact algebraic setting: the group of points on an elliptic curve over a finite field. An elliptic curve over $\mathbb{F}_p$ (for a prime $p > 3$) is the set of solutions to

$y^2 \equiv x^3 + ax + b \pmod{p}$

together with a special point at infinity $\mathcal{O}$, subject to the non-singularity condition $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$. The set of points on the curve forms an abelian group under a geometric law: to add two points $P$ and $Q$, draw the line through them, find the third intersection with the curve, and reflect over the $x$-axis. The point at infinity serves as the group identity. Algebraically, if $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ with $P \neq -Q$, the sum $P + Q = (x_3, y_3)$ is given by

$\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1$

where all arithmetic is performed modulo $p$. Point doubling uses the tangent slope $\lambda = (3x_1^2 + a)/(2y_1)$.

Scalar multiplication — computing $kP = P + P + \cdots + P$ ($k$ times) for a positive integer $k$ — can be done efficiently in $O(\log k)$ group operations using the double-and-add algorithm, analogous to fast modular exponentiation. The elliptic curve discrete logarithm problem (ECDLP) asks: given points $P$ and $Q = kP$ on the curve, find $k$. Unlike the integer factorization and classical discrete logarithm problems, no sub-exponential algorithm is known for ECDLP on properly chosen curves, which means elliptic curve cryptography provides equivalent security to RSA with dramatically smaller key sizes. A 256-bit elliptic curve key offers roughly the same security as a 3072-bit RSA key, with correspondingly faster computation and lower bandwidth.

The Elliptic Curve Diffie-Hellman (ECDH) protocol is the direct analog of Diffie-Hellman: both parties agree on a curve and a base point $G$ of large prime order $n$. Alice chooses a private scalar $a$ and publishes $aG$; Bob chooses $b$ and publishes $bG$; the shared secret is $abG$. The Elliptic Curve Digital Signature Algorithm (ECDSA) allows signing messages: to sign a message hash $e$ with private key $d$, choose a random nonce $k$, compute the point $(x_1, y_1) = kG$, set $r = x_1 \bmod n$, and compute $s = k^{-1}(e + rd) \bmod n$. The signature is $(r, s)$, verifiable by anyone who knows the public key $Q = dG$.

The security of ECDSA depends critically on the nonce $k$ being truly random and never reused. A repeated nonce immediately exposes the private key — this vulnerability was famously exploited in 2010 to recover private keys from Sony’s PlayStation 3, which used a constant nonce in its firmware signing. EdDSA (the Edwards-curve Digital Signature Algorithm, including Ed25519) addresses this by deriving the nonce deterministically from the message and private key, eliminating the source of failure while preserving all security guarantees.

Digital Signatures and Zero-Knowledge Proofs

A digital signature scheme allows a signer to produce a short tag on a message that any recipient can verify was produced by the signer and no one else, and that the signer cannot later repudiate. Formally, a signature scheme consists of three algorithms: key generation (producing a public-private key pair), signing (producing a signature $\sigma$ on message $m$ using the private key), and verification (checking whether $\sigma$ is a valid signature on $m$ under the public key). Security means that without the private key, it is computationally infeasible to produce a valid signature on any new message, even after observing signatures on polynomially many messages of the adversary’s choice — the notion is called existential unforgeability under chosen message attack (EUF-CMA).

RSA signatures work by inverting encryption: signing a message means applying the private-key operation $\sigma = m^d \bmod n$, and verification means checking that $\sigma^e \equiv m \pmod{n}$. With appropriate padding (the PSS scheme), RSA signatures are provably secure. ECDSA and EdDSA, described above, provide shorter signatures with equivalent security.

The deeper innovation of the 1980s was the realization that signatures and authentication are instances of a broader cryptographic primitive: the interactive proof. In an interactive proof, a prover attempts to convince a verifier of some claim through a sequence of challenges and responses. What makes this remarkable is the possibility of zero-knowledge proofs — interactive proofs in which the verifier learns nothing from the interaction beyond the bare fact that the claim is true. The verifier gains no information that would allow it to prove the claim to a third party or to compute anything it could not already compute.

The Schnorr identification protocol illustrates the idea concretely. To prove knowledge of a discrete logarithm $x$ such that $y = g^x$ in a group of prime order $q$, without revealing $x$: the prover chooses a random commitment $r$, sends $R = g^r$ to the verifier; the verifier sends a random challenge $c$; the prover responds with $s = r + cx \bmod q$; the verifier checks that $g^s = R \cdot y^c$. If the prover knows $x$, this always passes. Crucially, the transcript $(R, c, s)$ can be simulated without knowing $x$ (by choosing $s$ first and computing $R = g^s y^{-c}$), which proves the protocol is zero-knowledge: transcripts generated by an honest prover are computationally indistinguishable from simulated ones.

The Fiat-Shamir transform converts any such interactive protocol into a non-interactive signature scheme by replacing the verifier’s random challenge with a hash of the commitment: $c = H(R \| m)$. The hash function acts as a random oracle that neither party can control, making the proof non-interactive and binding it to a specific message. Schnorr signatures, EdDSA, and many modern constructions are built exactly this way.

Modern zk-SNARKs (zero-knowledge Succinct Non-interactive ARguments of Knowledge) push this further: they allow a prover to convince a verifier that it knows a secret input satisfying an arbitrary polynomial-time computation, with a proof that is tiny (a few hundred bytes) and verifiable in milliseconds regardless of the computation’s complexity. The underlying mathematics involves polynomial commitment schemes, quadratic arithmetic programs, and pairings on elliptic curves. zk-SNARKs have found dramatic applications in privacy-preserving cryptocurrencies (Zcash) and in scaling blockchains by moving computation off-chain.

Lattice-Based and Post-Quantum Cryptography

Every public-key cryptosystem described so far — RSA, Diffie-Hellman, elliptic curve cryptography — relies on a mathematical problem that a sufficiently powerful quantum computer can solve efficiently. In 1994, Peter Shor discovered quantum algorithms that factor integers and compute discrete logarithms in polynomial time, running on a quantum computer. If such a machine is ever built at sufficient scale, RSA, ECDSA, and Diffie-Hellman would all be broken simultaneously. The field of post-quantum cryptography seeks replacements whose security does not depend on these problems.

The leading candidate family is lattice-based cryptography. A lattice $\Lambda$ in $\mathbb{R}^n$ is the set of all integer linear combinations of $n$ linearly independent basis vectors $\mathbf{b}_1, \ldots, \mathbf{b}_n$:

$\Lambda = \left\{ \sum_{i=1}^n z_i \mathbf{b}_i \;\middle|\; z_i \in \mathbb{Z} \right\}$

Lattices support several problems believed to be hard even for quantum computers. The Shortest Vector Problem (SVP) asks for the shortest nonzero vector in $\Lambda$. The Closest Vector Problem (CVP) asks for the lattice point closest to a given target vector. The key hard problem for cryptographic construction is Learning with Errors (LWE), introduced by Oded Regev in 2005. In LWE, one is given many pairs $(\mathbf{a}_i, b_i)$ where $\mathbf{a}_i \in \mathbb{Z}_q^n$ is random and $b_i = \mathbf{a}_i \cdot \mathbf{s} + e_i \bmod q$ for a fixed secret vector $\mathbf{s}$ and small error terms $e_i$ drawn from a Gaussian distribution. The task is to recover $\mathbf{s}$. Regev proved that solving LWE is at least as hard as solving worst-case lattice problems, giving a security reduction with a firm mathematical foundation.

Ring-LWE is a more efficient variant in which vectors are replaced by polynomials in a ring $R_q = \mathbb{Z}_q[x]/(f(x))$ for a suitable irreducible polynomial $f$. The algebraic structure of the ring allows much more compact key representations and faster operations via the Number Theoretic Transform (NTT), analogous to the Fast Fourier Transform. NIST standardized several lattice-based schemes in 2024: CRYSTALS-Kyber (now ML-KEM) for key encapsulation, and CRYSTALS-Dilithium (now ML-DSA) and FALCON for digital signatures. These form the backbone of the post-quantum transition now underway across the internet.

Code-based cryptography offers another quantum-resistant approach. The McEliece cryptosystem (1978) is based on the hardness of decoding a random linear error-correcting code — a problem that has resisted quantum attack for decades. The system is fast but uses very large public keys (hundreds of kilobytes), which limits its practical deployment. Multivariate cryptography, based on the difficulty of solving systems of quadratic equations over finite fields, and hash-based signatures like SPHINCS+ (also NIST-standardized) round out the post-quantum portfolio. The “harvest now, decrypt later” threat — adversaries recording encrypted traffic today intending to decrypt it once quantum computers arrive — makes migration to post-quantum standards an urgent priority even before cryptographically relevant quantum computers exist.

Secure Computation and Homomorphic Encryption

The frontiers of modern cryptography extend well beyond confidentiality. Secure multiparty computation (MPC) addresses the following question: can a group of parties, each holding a private input, jointly compute a function of all their inputs without any party learning anything beyond the function’s output? Consider three executives who want to determine the average of their salaries without revealing individual values. MPC makes this possible through cryptographic protocols, even if some of the participants behave maliciously.

The foundational tool for MPC is secret sharing. In Shamir’s secret sharing scheme, a secret $s$ is divided into $n$ shares such that any $t$ shares are sufficient to reconstruct $s$, but any $t-1$ shares reveal nothing about it. The construction is elegant: choose a random polynomial $f$ of degree $t-1$ over $\mathbb{F}_p$ with $f(0) = s$, and give participant $i$ the share $f(i)$. Reconstruction uses Lagrange interpolation:

$s = f(0) = \sum_{i=1}^t s_i \prod_{j \neq i} \frac{-j}{i - j} \pmod{p}$

Any $t$ points determine the polynomial uniquely (by Lagrange interpolation), but $t-1$ points are consistent with every possible value of $s$ (since a polynomial of degree $t-1$ can pass through $t-1$ points while taking any value at 0). Shamir secret sharing is information-theoretically secure: even an adversary with unlimited computational power cannot extract the secret from fewer than $t$ shares.

Garbled circuits, introduced by Yao (1982) in his two-party computation protocol, provide a different technique: the circuit computing the desired function is “garbled” — each wire is assigned two random cryptographic keys representing 0 and 1, and each gate is encoded as an encrypted truth table with entries permuted and encrypted using the appropriate key pairs. The evaluating party can compute through the garbled circuit learning only the output, never the intermediate wire values. Modern optimizations like the “free XOR” technique and half-gates construction have made garbled circuits practical for large circuits.

Homomorphic encryption takes the most direct approach to private computation: it allows arithmetic to be performed directly on encrypted data, so that a cloud server can compute on data it cannot read. A scheme is additively homomorphic if $\text{Enc}(a) + \text{Enc}(b) = \text{Enc}(a + b)$ (the Paillier cryptosystem, built on RSA-like assumptions, is the classical example). A scheme is multiplicatively homomorphic if $\text{Enc}(a) \cdot \text{Enc}(b) = \text{Enc}(a \cdot b)$ (textbook RSA happens to have this property). A scheme supporting both operations is fully homomorphic encryption (FHE).

The existence of FHE was an open question for decades until Craig Gentry constructed the first scheme in 2009, using ideal lattices. The key challenge is that every homomorphic operation introduces noise into the ciphertext, and noise that grows too large causes decryption to fail. Gentry’s solution was bootstrapping: decrypting a noisy ciphertext homomorphically (using an encryption of the secret key) to produce a fresh encryption of the same message with reduced noise. While bootstrapping is computationally intensive, subsequent schemes — BGV, BFV, CKKS — have dramatically improved performance. The CKKS scheme, which supports approximate arithmetic on real and complex numbers, has found particular application in privacy-preserving machine learning, where it can evaluate neural network inference on encrypted patient data, allowing a hospital to use an AI diagnostic tool without exposing any individual’s records to the service provider. What once seemed a purely theoretical curiosity now sits at the edge of practical deployment, promising a future in which computation and privacy are no longer in conflict.