Cryptography

Cryptography is the art and science of communicating securely in the presence of an adversary.

12 frameworks, from 1467 to today · Theory Of Computation · Computer Science

still a working view ended · each leads to its entry below

Overview

Cryptography is the art and science of communicating securely in the presence of an adversary1. For most of its history it meant one thing above all: keeping a message secret from someone who might intercept it1. In the twentieth century, and especially after the 1970s, the field widened dramatically. Cryptographers now build systems for secrecy, but also for authentication, for proving statements without revealing why they are true, for computing on data without seeing it, and for coordinating distrustful parties1. What unites these goals is a particular style of reasoning that cryptography shares with the theory of computation: a security claim is a mathematical statement about what no efficient adversary can do, and it is proved, or at least argued, against a precise model of computation.

That style is what makes cryptography a subfield of theoretical computer science and not merely a branch of engineering. The history below follows the problems practitioners faced and the ideas they invented to solve them, from hand ciphers to the present.

Classical hand ciphers and the birth of cryptanalysis

For most of recorded history, cryptography was a craft of substitution and transposition1. A substitution cipher replaces each letter by another according to a fixed rule; a transposition cipher rearranges the letters123. The Caesar cipher, shifting each letter by a fixed amount, is the textbook example of the first1. These methods were used by generals, diplomats, and conspirators for centuries, and their weakness was understood early: a fixed substitution preserves the statistical fingerprint of the underlying language1. In English, e is the most common letter, so in a monoalphabetic cipher the most common ciphertext letter is probably e4. Frequency analysis, described in the ninth century by the Arab scholar al-Kindi in a work on deciphering cryptographic messages, turns this into a systematic attack124.

The response, from the fifteenth and sixteenth centuries onward, was the polyalphabetic cipher: use several substitution alphabets in rotation, so that the same plaintext letter encrypts differently at different positions. The Vigenère cipher, popularized in the sixteenth century, is the classic case. Its weakness is subtler. If the key is shorter than the message and repeats, the ciphertext splits into interleaved monoalphabetic ciphers, one per key position, and the key length can be recovered by statistical tests. The nineteenth-century attacks of Charles Babbage and Friedrich Kasiski exploited exactly this15. The lesson that emerged, though it took centuries to state precisely, is that a cipher is only as strong as the difficulty of the best attack, and that difficulty is a computational claim.

The mechanical era and information-theoretic security

The First World War and the decades after it pushed cryptography into machines1. Rotor machines such as the German Enigma enciphered each letter through a series of rotating wheels, producing a polyalphabetic cipher with an enormous period and a key that changed daily. Breaking Enigma at Bletchley Park in the Second World War was a landmark of cryptanalysis, combining mathematics, engineering, and the first large-scale electronic computation16. The work of Alan Turing and others on the bombe and on statistical attacks against the rotor settings showed that even a very complex mechanical cipher could fall to a well-designed computational attack6. Much of this work remained secret for decades, which shaped how the public history of the field unfolded.

In parallel, a theoretical foundation appeared. Claude Shannon's 1949 paper "Communication Theory of Secrecy Systems" recast cryptography in information-theoretic terms17. Shannon defined perfect secrecy: a cipher has it when the ciphertext gives no information about the plaintext, formally when the plaintext and ciphertext are statistically independent8. He proved that the one-time pad — a key as long as the message, used once, uniformly random — achieves perfect secrecy, and that any perfectly secret cipher needs a key at least as long as the message. This was a genuine theorem, not a heuristic, and it drew a sharp line: unconditional security is possible, but expensive1. Practical cryptography would have to settle for computational security, where the adversary is assumed to be limited in time or computing power19. Shannon also introduced the ideas of confusion and diffusion that later guided the design of block ciphers.

The public-key revolution

Until the 1970s, secure communication required the parties to share a secret key in advance110. That is a severe logistical constraint: to talk securely to n people, you need n pairwise secrets, and you need a secure channel to establish each one1. The breakthrough was public-key cryptography, in which each user has a public key that anyone can use to encrypt to them, and a private key kept secret110. The idea is usually credited to Whitfield Diffie and Martin Hellman, whose 1976 paper introduced the Diffie–Hellman key exchange: two parties who have never met can agree on a shared secret over a public channel, relying on the presumed difficulty of the discrete logarithm problem. (It later emerged that James Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ had developed similar ideas in the early 1970s, but their work was classified111.)

The following year, Ron Rivest, Adi Shamir, and Leonard Adleman introduced RSA, the first practical public-key encryption and signature scheme, based on the difficulty of factoring large integers. The conceptual shift was profound. Security no longer rested on the secrecy of the method, as in classical ciphers, but on the computational hardness of a well-studied mathematical problem1. Kerckhoffs's principle — that a system should remain secure even if everything except the key is public — became the working assumption of the field1. Public-key cryptography also made digital signatures possible, giving a computational analogue of a handwritten signature that could be verified by anyone1.

Provable security and the complexity-theoretic turn

The 1980s brought a second shift: cryptography began to prove its claims. The motivating question was what "secure" even means. The answer, developed by Shafi Goldwasser and Silvio Micali in their 1984 work on probabilistic encryption, was semantic security: a cipher is secure if no efficient adversary can learn anything about the plaintext beyond its length, even given the ciphertext. This is a definition in the language of computational complexity, quantifying over all polynomial-time adversaries8. Goldwasser and Micali showed that such security is achievable under standard hardness assumptions, and that randomness in encryption is essential — deterministic encryption leaks information by definition.

This inaugurated provable security, the practice of defining a security goal precisely, stating a hardness assumption, and reducing the one to the other: if an adversary could break the scheme, it could solve the hard problem12. The reduction is the cryptographic analogue of a complexity-theoretic lower bound. The framework was extended by many hands: chosen-ciphertext security, formal models for signatures and key exchange, and the random oracle model, in which a hash function is idealized as a truly random function to make proofs tractable. The field also learned to be careful: a proof in an idealized model does not automatically transfer to real implementations, a lesson reinforced by later attacks on schemes that were "proved" secure under such idealizations.

Zero-knowledge and interactive proofs

A striking outgrowth of the complexity-theoretic view was zero-knowledge proofs, introduced by Goldwasser, Micali, and Charles Rackoff in 198513. The idea: a prover can convince a verifier that a statement is true without revealing anything beyond its truth13. The canonical example is proving knowledge of a secret without revealing the secret, such as showing you know the factorization of a number by answering challenges that only a knower could answer13. Zero-knowledge proofs are defined by three properties — completeness, soundness, and zero-knowledge — each stated against efficient adversaries. They connect cryptography to interactive proof systems and complexity classes, and they became a practical tool decades later in privacy-preserving protocols and blockchains.

Elliptic curves and the broadening of hardness assumptions

Through the 1980s and 1990s, cryptographers looked for hardness assumptions that gave more security per bit of key. Elliptic-curve cryptography, proposed independently by Neal Koblitz and Victor Miller in 1985, uses the group of points on an elliptic curve over a finite field14. The discrete logarithm problem on these groups appears to be harder than in the multiplicative groups used by Diffie–Hellman and RSA, so shorter keys give comparable security. Elliptic curves became standard in constrained environments and in modern protocols. The episode also illustrates a recurring theme: the security of a scheme rests on the best known attack, and when a new attack appears — as with pairing-based attacks on certain curves — the assumptions must be re-examined.

Fully homomorphic encryption and computing on secrets

For decades, a central limitation was that to compute on encrypted data you had to decrypt it first15. Fully homomorphic encryption (FHE) promised the opposite: perform arbitrary computations on ciphertexts so that decrypting the result gives the answer to the computation on the plaintexts15. The problem was open for years, with partial solutions for addition or multiplication alone. In 2009, Craig Gentry gave the first construction of a fully homomorphic scheme, using lattice-based cryptography and a technique called bootstrapping to control noise growth. The early schemes were wildly impractical, but the idea opened a research program that has produced steadily more efficient constructions. FHE is now a major direction in both theory and practice, and it exemplifies the field's willingness to pursue goals that seem impossible until a construction is found.

Post-quantum cryptography and the present

The arrival of quantum computing changed the threat model116. In 1994, Peter Shor showed that a quantum computer could factor integers and compute discrete logarithms efficiently, which would break RSA, Diffie–Hellman, and elliptic-curve schemes. This made post-quantum cryptography — schemes secure against quantum adversaries — a priority1. The leading families are lattice-based, code-based, hash-based, and multivariate schemes, each resting on problems believed hard even for quantum computers. In 2022 the U.S. National Institute of Standards and Technology selected its first post-quantum standards, and the migration is underway.

Today the field is organized around a few large programs: standardizing post-quantum schemes, making FHE and secure multi-party computation practical, building zero-knowledge systems efficient enough for real deployment, and tightening the foundations of provable security. The open questions are the ones the history has been circling: which hardness assumptions are truly safe, how to prove security without idealized models, and how to build systems whose guarantees hold against adversaries we have not yet imagined.

References

  1. Cryptography (introduction, Terminology, History, Classic cryptography, Early computer-era cryptography, Modern cryptography, Symmetric-key cryptography, Public-key cryptography), Wikipedia
  2. Substitution cipher, Wikipedia
  3. Transposition cipher, Wikipedia
  4. Frequency analysis (introduction, History and usage), Wikipedia
  5. Kasiski examination, Wikipedia
  6. Cryptanalysis of the Enigma, Wikipedia
  7. Block cipher (History), Wikipedia
  8. Semantic security, Wikipedia
  9. Computational hardness assumption, Wikipedia
  10. Public-key cryptography (History, introduction), Wikipedia
  11. Diffie–Hellman key exchange, Wikipedia
  12. Provable security, Wikipedia
  13. Zero-knowledge proof (History, introduction), Wikipedia
  14. Elliptic-curve cryptography (History), Wikipedia
  15. Homomorphic encryption, Wikipedia
  16. Post-quantum cryptography, Wikipedia

The frameworks of Cryptography

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1467-1900

    Polyalphabetic ciphers

    How can a message be encrypted so that letter frequencies do not reveal it?

    Fly to its tower in Nousfarer

  2. 1500-1940

    Classical cipher

    How can messages be scrambled so that only the intended reader can read them?

    Fly to its tower in Nousfarer

  3. 1920-1960

    Electromechanical rotor cryptanalysis

    How can a complex mechanical cipher be broken by systematic analysis?

    Fly to its tower in Nousfarer

  4. 1949-Present
  5. 1976-Present

    Public-Key Cryptography

    How can two parties communicate securely without sharing a secret key in advance?

    About Public-Key Cryptography
    Public-Key Cryptography, introduced in the landmark 1976 paper "New Directions in Cryptography" by Whitfield Diffie and Martin Hellman, fundamentally altered the landscape of secure communication. Before this breakthrough, all cryptographic systems required parties to share a secret key in advance through a secure channel—a major practical limitation. Public-Key Cryptography solved this by using pairs of mathematically related keys: a public key, which can be freely distributed, and a private key, kept secret by its owner. This asymmetry enables two parties who have never met to establish secure communications, and it also makes possible digital signatures, which provide authentication and non-repudiation. The framework rests on the concept of trapdoor one-way functions—functions that are easy to compute in one direction but computationally infeasible to invert without a secret "trapdoor" (the private key). This paradigm shift turned cryptography from a tool limited to those who could manage secret key distribution into a foundational technology for global digital infrastructure, underpinning protocols like TLS, SSH, and PGP.
    The core curriculum for Public-Key Cryptography in a cryptography theory course begins with understanding the problem this framework solves: the key distribution problem. The first major concept is the notion of a one-way function, a function that is easy to compute but hard to invert without additional information. The next concept is a trapdoor one-way function, which adds a secret "trapdoor" that allows inversion. These lead directly to the two canonical applications: Public-Key Encryption, where anyone can encrypt a message using the public key, but only the private key holder can decrypt; and Digital Signatures, where the private key signs a message and anyone can verify the signature using the public key. A foundational protocol that demonstrates these ideas without full encryption is the Diffie–Hellman Key Exchange, which allows two parties to agree on a shared secret over an insecure channel. A second foundational system is the RSA Cryptosystem (Rivest–Shamir–Adleman, 1977), which provided the first full implementation of a public-key encryption and signature scheme based on the difficulty of factoring large integers. Key generation is an essential procedural concept: generating a secure key pair requires picking large primes (for RSA) or group elements (for Diffie–Hellman) with specific properties. Security for public-key systems is typically analyzed under the Computational Security model, meaning security holds against polynomial-time adversaries, assuming the underlying computational problem (like factoring or discrete logarithm) is hard. The concept of a hybrid cryptosystem is also central: because public-key operations are computationally expensive, practical systems use public-key cryptography only to establish a shared symmetric key, which then encrypts the bulk data. Finally, the framework introduces the public key infrastructure (PKI) as the practical mechanism for binding public keys to identities via certificates, ensuring that users can reliably obtain authentic copies of each other's public keys.
    The intellectual history of Public-Key Cryptography begins with its precursor, Information-Theoretic Cryptography, and its dominant figure, Claude Shannon. Shannon's 1949 paper "Communication Theory of Secrecy Systems" established the mathematical theory of secrecy but also proved that the only system achieving perfect secrecy—the one-time pad—required a key as long as the message, a severe practical limitation. This created an opening for a computational approach that could trade perfect secrecy for practical security based on hard problems. The key breakthrough came in 1976 with Whitfield Diffie and Martin Hellman's paper "New Directions in Cryptography," which introduced the concept of public-key cryptography and the Diffie–Hellman key exchange protocol, based on the discrete logarithm problem. Diffie and Hellman also proposed the idea of trapdoor one-way functions and outlined the need for public-key encryption and digital signatures, though they did not provide concrete implementations for the latter. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman published the RSA cryptosystem, which provided the first full public-key encryption and signature scheme, based on the difficulty of factoring the product of two large primes. This was followed by the ElGamal cryptosystem (Taher Elgamal, 1985), which adapted the Diffie–Hellman idea into a full encryption scheme. The field of Provable Security, which emerged around 1984 with the work of Shafi Goldwasser and Silvio Micali on semantic security, later provided rigorous definitions and reductions for public-key schemes, ensuring that breaking a scheme implies solving a underlying hard problem. Secure Multi-Party and Privacy-Preserving Cryptography, beginning around 1982 with Andrew Yao's work on garbled circuits, extended the public-key framework to allow multiple parties to jointly compute a function without revealing their private inputs. Public-Key Cryptography remains a dominant paradigm, although it now coexists with Post-Quantum Cryptography, which seeks schemes secure against quantum computers that could break RSA and Diffie–Hellman via Shor's algorithm.
    The 9 concepts its tower teaches
    • Computational Security
    • Diffie–Hellman Key Exchange
    • Digital Signatures
    • Hybrid Cryptosystem
    • Key Generation
    • One-Way Function
    • Public-Key Encryption
    • RSA Cryptosystem
    • Trapdoor One-Way Function

    Fly to its tower in Nousfarer

  6. 1982-Present

    Secure Multi-Party Computation

    How can distrustful parties compute a function together without revealing their inputs?

    Fly to its tower in Nousfarer

  7. 1984-Present

    Provable Security

    How can we prove that a cryptographic scheme is secure against all efficient adversaries?

    Fly to its tower in Nousfarer

  8. 1985-Present

    Elliptic-Curve Cryptography

    Can we get more security per bit of key using different mathematical groups?

    Fly to its tower in Nousfarer

  9. 1985-Present

    Zero-Knowledge and Interactive Proofs

    How can one prove a statement is true without revealing why it is true?

    Fly to its tower in Nousfarer

  10. 1994-Present

    Post-Quantum Cryptography

    How can we build cryptography that survives attacks by quantum computers?

    Fly to its tower in Nousfarer

  11. 1996-Present

    Lattice-Based Cryptography

    Can hard lattice problems provide secure encryption against quantum adversaries?

    Fly to its tower in Nousfarer

  12. 2009-Present

    Fully Homomorphic Encryption

    Can we compute on encrypted data without ever decrypting it?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Polyalphabetic ciphersClassical cipherElectromechanical rotor cryptanalysisInformation-Theoretic CryptographyPublic-Key CryptographySecure Multi-Party ComputationProvable SecurityElliptic-Curve CryptographyZero-Knowledge and Interactive ProofsPost-Quantum CryptographyLattice-Based CryptographyFully Homomorphic Encryption

Beyond the field

Where Cryptography's ideas came from in other fields, and what they led to there: the strongest 12 of 46 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Cryptography is a planet in Nousfarer

Its city has a tower for each of these 12 frameworks. Land, walk in, and climb one concept at a time.

Land on Cryptography

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Cryptography sits on the Map of Human Knowledge