Loading field map
Cryptography is the study of techniques for secure communication in the presence of adversaries. At its core, it concerns the design and analysis of protocols and algorithms that allow parties to exchange information or perform computations while ensuring properties such as confidentiality (only intended recipients can read a message), integrity (data has not been altered), authentication (the claimed sender is genuine), and non-repudiation (a sender cannot deny having sent a message). The field is a branch of the theory of computation because its central questions are about what can and cannot be computed under adversarial conditions, and its methods are fundamentally mathematical and computational.
The foundational problem of cryptography is the encryption of messages. Two parties, traditionally called Alice and Bob, wish to communicate over an insecure channel monitored by an eavesdropper, Eve. The goal is to transform a plaintext message into a ciphertext that reveals nothing useful to Eve, while allowing Bob, who possesses the appropriate key, to recover the plaintext. For most of history, this was the entire scope of the field. Classical ciphers—such as the Caesar cipher, the Vigenère cipher, or the Enigma machine—were based on secret algorithms or relatively short keys. Their security rested on the assumption that an adversary lacked the computational resources or the specific knowledge to break them. This approach was fundamentally heuristic: a cipher was considered secure until someone found an attack.
A decisive conceptual shift occurred in the mid-twentieth century with the work of Claude Shannon. Shannon formalized the notion of perfect secrecy: a cipher is perfectly secret if the ciphertext gives an eavesdropper no information whatsoever about the plaintext, regardless of her computational power. He proved that perfect secrecy requires a key at least as long as the message, used only once (the one-time pad). This result established an absolute limit on what information-theoretic security can achieve, but it also made perfect secrecy impractical for most applications because distributing and managing keys as long as the messages themselves is prohibitive.
The modern field of cryptography emerged when researchers asked a different question: what if we relax the requirement from information-theoretic security to computational security? Instead of demanding that an adversary learn nothing, we require only that breaking the scheme is computationally infeasible—that is, would require an amount of computation so large that it is effectively impossible. This reframing, developed in the 1970s and 1980s, transformed cryptography from an art of designing secret codes into a rigorous scientific discipline grounded in computational complexity theory.
The modern theory of cryptography rests on a single, crucial assumption: the existence of one-way functions. A one-way function is a function that is easy to compute in one direction but hard to invert on average. For example, multiplying two large prime numbers is easy, but given their product, finding the original primes is believed to be hard. The existence of one-way functions is not proven; it is a conjecture that is widely believed but depends on the unresolved question of whether P equals NP. If P equals NP, then one-way functions cannot exist, and most of modern cryptography would collapse. Conversely, the existence of one-way functions is known to be sufficient for many, though not all, cryptographic tasks.
This foundation explains why modern cryptography is a branch of the theory of computation. Its security proofs are conditional: they state that if a certain computational problem is hard (such as factoring large integers or computing discrete logarithms), then a given scheme is secure. These proofs are reductions, showing that any efficient algorithm that breaks the cryptographic scheme could be turned into an efficient algorithm that solves the underlying hard problem. This methodology, introduced in the 1980s, is what distinguishes modern cryptography from its historical predecessors. A scheme is not considered secure because no one has found an attack; it is considered secure because an attack would imply a breakthrough on a well-studied computational problem.
Within this computational framework, several distinct research programmes have developed, each addressing different aspects of the field's central questions.
Symmetric-key cryptography deals with schemes where Alice and Bob share the same secret key. The two fundamental tasks are encryption (confidentiality) and message authentication (integrity and authenticity). The design of block ciphers (such as the Advanced Encryption Standard, AES) and hash functions (such as SHA-256) is largely an engineering discipline, but it is guided by theoretical principles. The security of these constructions is typically argued through heuristic analysis and extensive cryptanalysis—the study of methods to break them—rather than through formal proofs from complexity assumptions. This is because the underlying structures are designed to be fast and practical, and proving their security would require assumptions that are not well understood.
A significant theoretical contribution to this area is the concept of provable security for modes of operation. A mode of operation specifies how to use a block cipher to encrypt messages of arbitrary length. Theoreticians have proven that certain modes are secure if the underlying block cipher is a pseudorandom permutation—a function that is indistinguishable from a truly random permutation by any efficient adversary. This shifts the burden of security from the mode to the block cipher, where it is addressed by cryptanalysis.
Public-key (or asymmetric) cryptography, introduced in the 1970s, solves the key distribution problem that plagues symmetric schemes. In a public-key system, each user has a pair of keys: a public key, which can be freely distributed, and a private key, which is kept secret. Messages encrypted with the public key can only be decrypted with the private key, and digital signatures work in the reverse direction. The security of these schemes relies on specific number-theoretic assumptions, most notably the hardness of factoring large integers (used in RSA) and the discrete logarithm problem in various groups (used in Diffie–Hellman key exchange and elliptic curve cryptography).
The theoretical framework for public-key cryptography was formalized in the 1980s with the concept of semantic security, which requires that an adversary who sees a ciphertext learns nothing about the plaintext beyond what she already knew. This definition, along with the notion of indistinguishability, became the standard for proving the security of encryption schemes. The field also developed the random oracle model, a heuristic in which a hash function is treated as a truly random function for the purpose of security proofs. Schemes proven secure in this model are not guaranteed to be secure in practice, but the model provides a useful sanity check.
A distinct research programme, sometimes called the "foundations of cryptography," seeks to understand the minimal assumptions and the general principles underlying all cryptographic tasks. This programme, initiated in the 1980s, established that many seemingly different tasks—encryption, signatures, zero-knowledge proofs, secure multiparty computation—are related through reductions. A central result is that the existence of one-way functions is necessary and sufficient for many basic tasks, such as pseudorandom generators (functions that expand a short random seed into a long string that looks random) and private-key encryption. For public-key encryption and digital signatures, stronger assumptions are needed, such as the existence of trapdoor functions (one-way functions that are easy to invert with additional secret information).
This programme also introduced the concept of hybrid arguments, a proof technique that shows a scheme is secure by considering a sequence of intermediate games, each indistinguishable from the previous one, until reaching a game where security is obvious. This technique is now ubiquitous in cryptographic proofs.
Secure multiparty computation (MPC) addresses a more general problem than encryption: how can a group of parties jointly compute a function of their private inputs without revealing those inputs to each other? For example, several companies might want to compute the total revenue of their industry without disclosing their individual revenues. The foundational result in this area, due to Andrew Yao and later generalized, is that any function can be securely computed, provided that a majority (or, in some settings, any number) of the parties are honest. This is a striking result because it shows that cryptography can enforce correct behavior even when parties do not trust each other.
The two main approaches to MPC are garbled circuits (where one party encodes the function as a circuit and sends it to another party in encrypted form) and secret sharing (where each input is split into shares distributed among the parties, and the computation is performed on the shares). These approaches have different efficiency characteristics and security models, and both remain active areas of research. The theoretical significance of MPC is that it demonstrates the power of cryptography to go beyond communication security and into the realm of distributed computation.
A zero-knowledge proof is a protocol in which one party (the prover) convinces another (the verifier) that a statement is true without revealing anything beyond the truth of the statement. For example, a prover might convince a verifier that she knows a solution to a Sudoku puzzle without revealing the solution itself. The concept, introduced in the 1980s, is a cornerstone of modern cryptography. It is used in authentication protocols, in constructing secure multiparty computation, and in blockchain systems for verifying transactions without revealing their contents.
The theory of zero-knowledge proofs is notable for its subtle definitions. A proof is zero-knowledge if the verifier's view of the protocol can be simulated without access to the prover's secret, meaning that the verifier learns nothing she could not have learned on her own. There are several variants—perfect, statistical, and computational zero-knowledge—depending on how close the simulation is to the real interaction. The existence of zero-knowledge proofs for all NP statements (a class of computational problems) is a deep result that connects cryptography to computational complexity theory.
A more recent but now central concern is the threat posed by quantum computers. In the 1990s, Peter Shor showed that a sufficiently large quantum computer could efficiently solve the factoring and discrete logarithm problems, which would break RSA, Diffie–Hellman, and elliptic curve cryptography. This has motivated the search for cryptographic schemes based on problems believed to be hard even for quantum computers, such as learning with errors (a problem from lattice theory) and certain problems on error-correcting codes.
Post-quantum cryptography is not a single approach but a collection of proposals, each with its own assumptions and trade-offs. The field is currently in a standardization phase, with the National Institute of Standards and Technology (NIST) having selected several lattice-based schemes for standardization. It is important to note that post-quantum schemes are not proven secure against quantum attacks; they are based on the presumed hardness of specific mathematical problems, just as classical schemes are based on the presumed hardness of factoring and discrete logarithms.
These approaches are not rival schools that compete for dominance; they are complementary research programmes that address different aspects of the field. Symmetric and public-key cryptography solve different problems (key distribution versus efficiency), and modern protocols typically use both: public-key cryptography to establish a shared secret, and symmetric cryptography to encrypt the actual data. Provable security provides the theoretical framework for all of them, while cryptanalysis serves as the empirical check on whether the assumptions hold in practice.
There are, however, genuine tensions. The provable security programme sometimes produces schemes that are too inefficient for practical use, while practical schemes often rely on assumptions that have not been rigorously analyzed. The random oracle model is a point of contention: some researchers argue that proofs in this model provide meaningful assurance, while others point out that there exist schemes that are secure in the model but insecure when the random oracle is instantiated with any concrete hash function. Similarly, the relationship between the existence of one-way functions and the P versus NP question is a deep open problem that underlies the entire field.
The current landscape of cryptography is characterized by several durable features. First, the field is firmly grounded in computational complexity theory: security is always relative to an adversary with bounded computational resources, and proofs are conditional on the hardness of specific problems. Second, the field has expanded far beyond encryption to encompass a rich set of tasks—digital signatures, authentication, key exchange, secure computation, zero-knowledge proofs, and more—each with its own definitions and constructions. Third, the field is increasingly concerned with practical deployment, including issues of side-channel attacks (where an adversary exploits physical characteristics of a device, such as timing or power consumption), implementation errors, and the transition to post-quantum algorithms.
A defining feature of modern cryptography is its insistence on formal definitions. A cryptographic scheme is not considered secure until its security goal has been precisely stated and a proof has been provided that the scheme meets that goal under explicit assumptions. This emphasis on rigor, which distinguishes modern cryptography from its historical predecessors, is also what makes it a branch of the theory of computation. The field's central questions—What can be computed securely? Under what assumptions? At what cost?—are computational questions, and its methods are the methods of complexity theory and probability theory.
The open problems that define the field's frontier are equally computational. Whether one-way functions exist is the most fundamental, but there are many others: Can we build public-key encryption from symmetric primitives alone? Can we achieve fully homomorphic encryption (computing on encrypted data without decrypting it) with practical efficiency? Can we prove the security of standardized schemes without relying on idealized models? These questions ensure that cryptography remains an active and evolving field, one whose answers will shape the security of digital communication for the foreseeable future.