Cryptography

Cryptography is the science of transforming information so that only authorized parties can access it, and of providing mathematical guarantees of authenticity, integrity, and privacy. It sits at the intersection of number theory, algebra, complexity theory, and information theory, drawing on deep mathematical structure to build systems that billions of people rely on every day without awareness.

Classical Cryptography and the Foundations of Secrecy

The practice of hiding messages is ancient. Julius Caesar reportedly shifted each letter of his military dispatches by a fixed number of positions in the alphabet, producing one of the earliest documented substitution ciphers. For centuries, ciphers grew more elaborate — polyalphabetic systems like the Vigenere cipher, introduced in the sixteenth century, defeated simple frequency analysis by cycling through multiple substitution alphabets keyed by a repeating word. Transposition ciphers rearranged the positions of characters rather than replacing them, and real-world systems often combined both techniques. Yet all classical ciphers shared a fundamental weakness: their security rested on the secrecy of the method itself, and a sufficiently clever analyst armed with enough ciphertext could almost always recover the plaintext.

The watershed came in 1949, when Claude Shannon published Communication Theory of Secrecy Systems, recasting cryptography in the language of information theory. Shannon proved that the one-time pad — a cipher in which the key is a truly random string at least as long as the message, used exactly once — achieves perfect secrecy: the ciphertext reveals absolutely no information about the plaintext, regardless of the adversary’s computational power. Formally, for a plaintext $M$, ciphertext $C$, and key $K$ drawn uniformly at random, perfect secrecy means $P(M = m \mid C = c) = P(M = m)$ for all $m$ and $c$. Shannon also proved the converse: perfect secrecy requires a key at least as long as the message, making the one-time pad impractical for most applications. This impossibility result motivated the shift from information-theoretic security to computational security, where we accept that an adversary with bounded computational resources cannot break the system, even though an all-powerful adversary could in principle.

The mechanization of cryptography reached its dramatic climax during the Second World War. The German Enigma machine — an electromechanical rotor cipher with an astronomical number of possible settings — was famously broken by a team at Bletchley Park led by Alan Turing, who designed the Bombe, an electromechanical device that exploited known-plaintext patterns to eliminate impossible rotor configurations. The Enigma effort demonstrated a principle that remains central to modern cryptanalysis: the security of a system depends not on the obscurity of the algorithm but on the secrecy and quality of the key, a dictum later formalized as Kerckhoffs’s principle.

Symmetric Encryption: Block and Stream Ciphers

In symmetric-key encryption, the same secret key is used for both encryption and decryption. The two main families are block ciphers, which process fixed-size blocks of plaintext, and stream ciphers, which encrypt one bit or byte at a time using a pseudorandom keystream.

The modern era of block cipher design began with the Data Encryption Standard (DES), published in 1977 by the U.S. National Bureau of Standards based on a design by Horst Feistel at IBM. DES encrypts 64-bit blocks using a 56-bit key through 16 rounds of a Feistel network — a structure in which half the block is passed through a round function $f$ and XORed with the other half, then the halves are swapped. Each round applies Shannon’s principles of confusion (making the relationship between key and ciphertext complex) and diffusion (spreading plaintext statistics across the ciphertext). DES served well for two decades, but its 56-bit key proved too short: in 1998 a dedicated hardware machine cracked DES in under three days by brute-force search over the $2^{56}$ key space.

The replacement, the Advanced Encryption Standard (AES), was selected in 2001 after a public competition won by the Rijndael algorithm of Joan Daemen and Vincent Rijmen. AES operates on 128-bit blocks with key sizes of 128, 192, or 256 bits. Its design is not a Feistel network but a substitution-permutation network: each round applies a byte substitution (SubBytes) using an S-box derived from inversion in $\text{GF}(2^8)$, a row shift (ShiftRows), a column mixing (MixColumns) based on multiplication in $\text{GF}(2^8)$, and a key addition (AddRoundKey). AES remains the dominant symmetric cipher, with no practical attack significantly better than brute force against the full cipher.

Block ciphers are not used in isolation but through modes of operation that determine how multiple blocks are processed. Electronic Codebook (ECB) mode encrypts each block independently, which leaks patterns in the plaintext. Cipher Block Chaining (CBC) XORs each plaintext block with the previous ciphertext block before encryption, breaking patterns but requiring an initialization vector. Counter (CTR) mode turns a block cipher into a stream cipher by encrypting successive counter values and XORing the result with plaintext, enabling parallelization. Galois/Counter Mode (GCM) combines CTR encryption with a polynomial-based message authentication code, providing authenticated encryption — simultaneous confidentiality and integrity — which is now the standard for protocols like TLS 1.3.

Stream ciphers generate a pseudorandom keystream from a short key and a nonce, then XOR it with the plaintext. Early designs like RC4 were widely deployed in protocols such as WEP and early TLS but proved vulnerable to statistical biases in the keystream. The modern standard is ChaCha20, designed by Daniel J. Bernstein, which uses a sequence of add-rotate-XOR operations on a 256-bit key to produce a keystream with excellent statistical properties and resistance to known attacks. Paired with the Poly1305 authenticator, ChaCha20-Poly1305 provides authenticated encryption and is a preferred cipher suite in TLS 1.3, particularly on platforms without hardware AES acceleration.

Public-Key Cryptography and the RSA System

The conceptual revolution that transformed cryptography came in 1976, when Whitfield Diffie and Martin Hellman published New Directions in Cryptography, proposing that two parties could agree on a shared secret over a public channel without ever having met. Their insight was that certain mathematical functions are easy to compute but hard to invert — so-called one-way functions — and that a trapdoor one-way function allows inversion with knowledge of a secret. In a public-key system, each party publishes a public key derived from a trapdoor function; anyone can encrypt a message using the public key, but only the holder of the corresponding private key can decrypt it.

The first practical realization was the RSA cryptosystem, introduced in 1977 by Ronald Rivest, Adi Shamir, and Leonard Adleman. RSA relies on the presumed hardness of factoring the product of two large primes. Key generation selects two large primes $p$ and $q$, computes $n = pq$ and $\phi(n) = (p-1)(q-1)$, chooses a public exponent $e$ coprime to $\phi(n)$, and computes the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$. Encryption of a message $m$ produces $c \equiv m^e \pmod{n}$; decryption recovers $m \equiv c^d \pmod{n}$. The correctness follows from Euler’s theorem: $m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \pmod{n}$. The security of RSA rests on the RSA assumption — that computing $e$-th roots modulo $n$ is hard without the factorization — which is believed to be equivalent in difficulty to factoring $n$.

Raw “textbook RSA” is deterministic and therefore vulnerable to chosen-plaintext attacks. In practice, RSA is used with padding schemes such as OAEP (Optimal Asymmetric Encryption Padding), which introduces randomness and has been proven semantically secure under the RSA assumption in the random oracle model. RSA also provides digital signatures: signing a message $m$ produces $s \equiv m^d \pmod{n}$, and verification checks that $s^e \equiv m \pmod{n}$. The Probabilistic Signature Scheme (PSS) adds randomness to achieve tight security reductions.

Elliptic Curve Cryptography and Discrete Logarithms

An alternative family of public-key systems is based on the discrete logarithm problem (DLP): given a cyclic group $G$ of order $q$, a generator $g$, and an element $h = g^x$, find $x$. The Diffie-Hellman key exchange uses this in the multiplicative group of integers modulo a prime $p$: Alice sends $g^a \bmod p$, Bob sends $g^b \bmod p$, and both compute the shared secret $g^{ab} \bmod p$. The ElGamal encryption scheme and the Digital Signature Algorithm (DSA) extend this framework to encryption and signing.

In the 1980s, Neal Koblitz and Victor Miller independently proposed using the group of points on an elliptic curve over a finite field as the setting for discrete-logarithm-based cryptography. An elliptic curve over $\mathbb{F}_p$ is defined by an equation of the form $y^2 = x^3 + ax + b$ (with $4a^3 + 27b^2 \neq 0$ to ensure smoothness), and its points form an abelian group under a geometric addition law. The elliptic curve discrete logarithm problem (ECDLP) — given points $P$ and $Q = kP$, find $k$ — is believed to be substantially harder than the ordinary DLP in $\mathbb{F}_p^*$ for groups of the same size, because the index calculus attacks that accelerate factoring and conventional DLP do not transfer to generic elliptic curves. This hardness advantage means that a 256-bit elliptic curve key provides security comparable to a 3072-bit RSA key, making elliptic curve Diffie-Hellman (ECDH) and the Elliptic Curve Digital Signature Algorithm (ECDSA) far more efficient for constrained environments.

Advanced elliptic curve techniques include pairing-based cryptography, which exploits bilinear maps $e: G_1 \times G_2 \to G_T$ to enable constructions such as identity-based encryption (where a user’s public key is their email address or name) and functional encryption. Pairings opened the door to a rich set of protocols that were previously impossible, though they also introduced new hardness assumptions and implementation subtleties.

Hash Functions, MACs, and Digital Signatures

A cryptographic hash function $H: \{0,1\}^* \to \{0,1\}^n$ maps arbitrary-length inputs to fixed-length outputs and must satisfy three properties: preimage resistance (given $y$, it is hard to find $x$ with $H(x) = y$), second preimage resistance (given $x$, it is hard to find $x' \neq x$ with $H(x') = H(x)$), and collision resistance (it is hard to find any pair $x \neq x'$ with $H(x) = H(x')$). The generic birthday attack finds collisions in $O(2^{n/2})$ evaluations, so a hash with $n$-bit output provides at most $n/2$ bits of collision resistance.

Early hash functions like MD5 (128-bit output, designed by Ronald Rivest in 1991) and SHA-1 (160-bit, published by NIST in 1995) followed the Merkle-Damgard construction, which processes the message in blocks through an iterated compression function. Both were eventually broken: practical collision attacks on MD5 appeared in 2004 (by Xiaoyun Wang and collaborators), and a collision for the full SHA-1 was demonstrated in 2017 by the SHAttered team. The SHA-2 family (SHA-256, SHA-512), also Merkle-Damgard based, remains secure. The SHA-3 standard, selected in 2012, is built on the Keccak sponge construction designed by Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles Van Assche — a fundamentally different architecture that absorbs input into a large internal state and squeezes out the hash, offering resilience against length-extension attacks that plague Merkle-Damgard designs.

Message Authentication Codes (MACs) provide integrity and authenticity using a shared key. HMAC, defined as $\text{HMAC}_K(m) = H((K \oplus \text{opad}) \| H((K \oplus \text{ipad}) \| m))$, is provably secure as a pseudorandom function assuming the underlying hash function’s compression function is a PRF. Password hashing uses deliberately slow functions — PBKDF2, bcrypt, and the memory-hard Argon2 — to resist brute-force attacks on weak passwords.

Digital signatures extend beyond RSA and ECDSA. EdDSA, based on twisted Edwards curves and deterministic nonce generation, eliminates the catastrophic nonce-reuse vulnerability that has plagued ECDSA implementations. Schnorr signatures, long blocked by patents, are now widely adopted and form the basis of multi-signature schemes. Hash-based signatures like XMSS and SPHINCS+ derive their security solely from the properties of hash functions, making them attractive candidates for post-quantum cryptography since hash function security is not threatened by quantum algorithms in the way that factoring and DLP assumptions are.

Zero-Knowledge Proofs and Secure Computation

A zero-knowledge proof allows a prover to convince a verifier that a statement is true without revealing any information beyond the validity of the statement itself. Formally, a zero-knowledge proof system for a language $L$ satisfies three properties: completeness (an honest prover convinces an honest verifier for any $x \in L$), soundness (no cheating prover can convince the verifier for $x \notin L$ except with negligible probability), and zero-knowledge (the verifier’s view can be simulated without the prover, so no information is leaked). The concept was introduced in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff.

Classical interactive zero-knowledge protocols include the Schnorr protocol for proving knowledge of a discrete logarithm and the Fiat-Shamir identification scheme. The Fiat-Shamir transform converts interactive protocols into non-interactive ones by replacing the verifier’s random challenge with the output of a hash function applied to the prover’s commitment, yielding a non-interactive zero-knowledge proof (NIZK) in the random oracle model. Modern constructions have taken this idea to extraordinary lengths. zk-SNARKs (zero-knowledge Succinct Non-interactive Arguments of Knowledge) produce constant-size proofs that can be verified in milliseconds regardless of the complexity of the underlying computation, though they require a trusted setup to generate common reference parameters. zk-STARKs (Scalable Transparent Arguments of Knowledge), introduced by Eli Ben-Sasson and collaborators, eliminate the trusted setup by relying on hash functions and algebraic coding theory, producing larger proofs but with transparent, post-quantum-secure assumptions.

Secure multiparty computation (MPC) generalizes zero-knowledge to settings where multiple parties wish to compute a joint function of their private inputs without revealing those inputs to each other. The theoretical foundations were laid by Andrew Yao in 1982 with his garbled circuits protocol for two-party computation, and by Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson in 1988 with the BGW protocol for the multiparty case. Shamir’s secret sharing — which splits a secret $s$ into $n$ shares such that any $t$ shares suffice to reconstruct $s$ but fewer than $t$ reveal nothing — is a key building block. Practical MPC systems now handle tasks like secure auctions, private set intersection, and privacy-preserving machine learning, with performance that was unimaginable a decade ago.

Homomorphic Encryption and Lattice-Based Cryptography

Homomorphic encryption allows computation on encrypted data without decryption. A scheme is additively homomorphic if $\text{Enc}(m_1) \cdot \text{Enc}(m_2) = \text{Enc}(m_1 + m_2)$, and multiplicatively homomorphic if a similar relation holds for multiplication. For decades, constructing a fully homomorphic encryption (FHE) scheme supporting both operations — and therefore arbitrary computation — remained an open problem. In 2009, Craig Gentry achieved the breakthrough by constructing an FHE scheme from ideal lattices, using a technique called bootstrapping: a somewhat-homomorphic scheme that can evaluate its own decryption circuit can refresh ciphertexts and thus support unlimited computation. Subsequent schemes like BFV, BGV, and CKKS (which supports approximate arithmetic on real numbers) have brought FHE closer to practicality, though significant performance overhead remains.

The security of Gentry’s construction and most modern FHE schemes rests on the hardness of lattice problems, particularly the Learning With Errors (LWE) problem introduced by Oded Regev in 2005. Given a matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$, a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$, and a noise vector $\mathbf{e}$ with small entries, the LWE problem asks to recover $\mathbf{s}$ from $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} \pmod{q}$. Regev showed a quantum reduction from worst-case lattice problems (like the Shortest Vector Problem) to average-case LWE, providing strong theoretical evidence for its hardness. The Ring-LWE and Module-LWE variants operate over polynomial rings and offer improved efficiency, forming the basis of the most important post-quantum cryptographic schemes.

Lattice-based cryptography now dominates the post-quantum landscape. The NIST Post-Quantum Cryptography standardization process, which began in 2016 and announced its first selections in 2022, chose the lattice-based CRYSTALS-Kyber key encapsulation mechanism and CRYSTALS-Dilithium signature scheme as primary standards. The hash-based SPHINCS+ was selected as an alternative signature scheme. These algorithms are designed to resist attacks by quantum computers running Shor’s algorithm, which efficiently solves factoring and discrete logarithm problems and would break RSA, Diffie-Hellman, and elliptic curve cryptography. Grover’s algorithm provides only a quadratic speedup for symmetric key search, so doubling key lengths (e.g., from AES-128 to AES-256) suffices for symmetric schemes.

Post-Quantum Cryptography and Emerging Frontiers

The threat posed by quantum computation to classical public-key cryptography has driven an urgent migration effort. Organizations worldwide are inventorying their cryptographic dependencies and planning transitions to post-quantum algorithms, a process complicated by the need for crypto-agility — the ability to swap cryptographic primitives without redesigning entire systems. Hybrid schemes that combine a classical algorithm (like ECDH) with a post-quantum one (like Kyber) in a single key exchange are being deployed as a transitional measure, ensuring security even if one component is later broken.

Beyond post-quantum migration, several frontier areas are reshaping the field. Indistinguishability obfuscation (iO), if achievable efficiently, would be a “master tool” from which almost any cryptographic primitive can be constructed, but current constructions remain far from practical. Differential privacy is being integrated with cryptographic protocols to provide formal guarantees about statistical queries over sensitive data. Formal verification of cryptographic implementations — using tools that mathematically prove that code correctly implements a specification and is free of side-channel leaks — is becoming essential as the gap between theoretical security and real-world vulnerability (timing attacks, power analysis, and fault injection) has proven repeatedly exploitable. The convergence of these threads — provable security, post-quantum resilience, privacy-preserving computation, and verified implementation — defines the trajectory of cryptography as it enters its next era.