- Atlas
- Computer Science
- Cryptography
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
- Polyalphabetic ciphers 1467-1900
- Classical cipher 1500-1940
- Electromechanical rotor cryptanalysis 1920-1960
- Information-Theoretic Cryptography 1949-Present
- Public-Key Cryptography 1976-Present
- Secure Multi-Party Computation 1982-Present
- Provable Security 1984-Present
- Elliptic-Curve Cryptography 1985-Present
- Zero-Knowledge and Interactive Proofs 1985-Present
- Post-Quantum Cryptography 1994-Present
- Lattice-Based Cryptography 1996-Present
- Fully Homomorphic Encryption 2009-Present
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
- Cryptography (introduction, Terminology, History, Classic cryptography, Early computer-era cryptography, Modern cryptography, Symmetric-key cryptography, Public-key cryptography), Wikipedia
- Substitution cipher, Wikipedia
- Transposition cipher, Wikipedia
- Frequency analysis (introduction, History and usage), Wikipedia
- Kasiski examination, Wikipedia
- Cryptanalysis of the Enigma, Wikipedia
- Block cipher (History), Wikipedia
- Semantic security, Wikipedia
- Computational hardness assumption, Wikipedia
- Public-key cryptography (History, introduction), Wikipedia
- Diffie–Hellman key exchange, Wikipedia
- Provable security, Wikipedia
- Zero-knowledge proof (History, introduction), Wikipedia
- Elliptic-curve cryptography (History), Wikipedia
- Homomorphic encryption, Wikipedia
- 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.
- 1467-1900
Polyalphabetic ciphers
How can a message be encrypted so that letter frequencies do not reveal it?
- 1500-1940
Classical cipher
How can messages be scrambled so that only the intended reader can read them?
- 1920-1960
Electromechanical rotor cryptanalysis
How can a complex mechanical cipher be broken by systematic analysis?
- 1949-Present
- 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
- 1982-Present
Secure Multi-Party Computation
How can distrustful parties compute a function together without revealing their inputs?
- 1984-Present
Provable Security
How can we prove that a cryptographic scheme is secure against all efficient adversaries?
- 1985-Present
Elliptic-Curve Cryptography
Can we get more security per bit of key using different mathematical groups?
- 1985-Present
Zero-Knowledge and Interactive Proofs
How can one prove a statement is true without revealing why it is true?
- 1994-Present
Post-Quantum Cryptography
How can we build cryptography that survives attacks by quantum computers?
- 1996-Present
Lattice-Based Cryptography
Can hard lattice problems provide secure encryption against quantum adversaries?
- 2009-Present
Fully Homomorphic Encryption
Can we compute on encrypted data without ever decrypting it?
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.
Provable Security influenced by Public-Key Cryptography
Goldwasser and Micali's definition of semantic security was formulated for public-key encryption, and their proof that it is achievable under hardness assumptions set the template for provable security. The reduction style grew directly out of the public-key setting.
Carried by Shafi Goldwasser; Silvio Micali; Probabilistic Encryption (1984).
Fully Homomorphic Encryption influenced by Lattice-Based Cryptography
Gentry's first fully homomorphic encryption scheme was built on lattice-based cryptography, using ideal lattices and bootstrapping. The construction relied directly on lattice hardness assumptions.
Carried by Craig Gentry.
Electromechanical rotor cryptanalysis influenced by Polyalphabetic ciphers
Rotor machines such as Enigma were built as polyalphabetic ciphers with a very long period, and their cryptanalysis at Bletchley Park exploited the resulting periodic structure. The statistical attacks on repeating-key polyalphabetic ciphers carried over into attacks on rotor settings.
Carried by Marian Rejewski; Alan Turing.
Information-Theoretic Cryptography influenced by Classical cipher
Shannon's 1949 paper recast classical cipher concepts in information-theoretic terms, defining perfect secrecy and proving the one-time pad optimal. He drew directly on the classical distinction between secrecy of the method and secrecy of the key.
Carried by Claude Shannon; Communication Theory of Secrecy Systems (1949).
Public-Key Cryptography influenced by Information-Theoretic Cryptography
Diffie and Hellman framed public-key cryptography against Shannon's distinction between unconditional and computational security, explicitly seeking schemes secure under computational assumptions rather than information-theoretic ones.
Carried by Whitfield Diffie; Martin Hellman; New Directions in Cryptography (1976).
Elliptic-Curve Cryptography influenced by Public-Key Cryptography
Elliptic-curve cryptography was proposed as an alternative group for implementing Diffie–Hellman key exchange and related public-key schemes, using the same discrete-logarithm hardness assumption in a different algebraic setting.
Carried by Neal Koblitz; Victor Miller.
Zero-Knowledge and Interactive Proofs influenced by Public-Key Cryptography
Zero-knowledge proofs were introduced in the context of public-key cryptography, with the canonical example being proving knowledge of a factorization or discrete logarithm without revealing it. The interactive proof framework was motivated by public-key identification and encryption.
Carried by Shafi Goldwasser; Silvio Micali; Charles Rackoff.
Post-Quantum Cryptography influenced by Public-Key Cryptography
Post-quantum cryptography arose as a response to Shor's quantum algorithm for factoring and discrete logarithms, which breaks RSA and Diffie–Hellman. The field seeks public-key schemes based on other hardness assumptions.
Carried by Peter Shor.
Zero-Knowledge and Interactive Proofs influenced by Provable Security
Zero-knowledge proofs were defined with completeness, soundness, and zero-knowledge properties quantified over efficient adversaries, directly extending the complexity-theoretic style of provable security. The definitions and reductions follow the same pattern.
Carried by Shafi Goldwasser; Silvio Micali; Charles Rackoff.
Information-Theoretic Cryptography influenced by Electromechanical rotor cryptanalysis
Shannon's wartime cryptanalysis of rotor machines informed his later theoretical treatment of secrecy systems, where he formalized the notion of a cipher and its statistical properties.
Carried by Claude Shannon.
Secure Multi-Party Computation influenced by Public-Key Cryptography
Secure multi-party computation extended the public-key setting to multiple parties, using public-key encryption and oblivious transfer as building blocks. The problem of coordinating distrustful parties arose from the public-key model of separate keys.
Carried by Andrew Yao.
Fully Homomorphic Encryption influenced by Secure Multi-Party Computation
Fully homomorphic encryption was motivated in part by secure multi-party computation and the goal of computing on encrypted data without decrypting it. The problem setting extends the multi-party computation goal to a single evaluator.
Carried by Craig Gentry.
Beyond the field
Where Cryptography's ideas came from in other fields, and what they led to there: the strongest 12 of 46 links.
Information-Theoretic Cryptography grew out of Information theory in Electrical Engineering
Information-theoretic cryptography derives its core quantities from Shannon's information theory as developed in electrical engineering. Shannon's 1949 secrecy paper carried the entropy framework directly into cryptanalysis.
Carried by Claude Shannon.
Information-Theoretic Cryptography grew out of Shannon Theory of Communication in Information Theory
Shannon's theory of communication supplied the entropy, redundancy and equivocation measures that information-theoretic cryptography uses to define perfect secrecy. The cryptographic framework is a direct application and branch of that theory.
Carried by Claude Shannon.
Information-Theoretic Cryptography grew out of Shannon information theory in Coding Theory
Information-theoretic cryptography is built directly on Shannon's mathematical theory of communication, using its entropy and channel concepts to define secrecy. Shannon himself made the transfer in his 1949 secrecy paper.
Carried by Claude Shannon; Communication Theory of Secrecy Systems (1949).
Information-Theoretic Cryptography grew out of Information Theory in Communication
Shannon's 1949 paper on secrecy systems applied his own information theory, defining perfect secrecy through entropy and equivocation. Information-theoretic cryptography is a direct branch grown from Shannon's communication theory.
Carried by Claude Shannon; Communication Theory of Secrecy Systems (1949).
Information-Theoretic Cryptography grew out of Information Theory in Communication Systems
Information-theoretic cryptography is a branch of Shannon's information theory as taught in communication systems engineering, using its entropy and channel-capacity concepts. Shannon's secrecy paper made the transfer explicit.
Carried by Claude Shannon.
Public-Key Cryptography influenced End-to-End Encryption in Digital Privacy
Public-key cryptography, introduced by Diffie and Hellman in 1976, lets parties establish shared secrets over an insecure channel. End-to-end encrypted messaging depends on this for key exchange and identity, using it to keep keys out of the server's hands.
Carried by Whitfield Diffie; Martin Hellman; New Directions in Cryptography (1976).
Public-Key Cryptography influenced Cryptographic Privacy Engineering in Digital Privacy
Public-key cryptography, introduced by Diffie and Hellman in 1976 and realized by RSA in 1977, supplied the mathematical tools that cryptographic privacy engineering built on for key exchange and secure channels. Privacy-engineering schemes from the 1980s onward were constructed from public-key primitives.
Carried by Whitfield Diffie; Martin Hellman; Rivest, Shamir and Adleman.
Public-Key Cryptography influenced Public-Key Infrastructure in Applied Cryptography
Public-key cryptography is the underlying primitive that public-key infrastructure organizes into certificates and trust hierarchies. PKI grew directly out of the need to bind public keys to identities.
Carried by Whitfield Diffie; Martin Hellman; Rivest, Shamir, Adleman.
Public-Key Cryptography influenced Cryptographic protocol in Applied Cryptography
Public-key cryptography is the primitive basis of cryptographic protocols; key exchange and digital signatures from the 1976-77 work were the building blocks of later protocol design.
Carried by Whitfield Diffie; Martin Hellman.
Provable Security influenced by Public-key cryptography in Cybersecurity
Public-key cryptography supplied the concrete schemes and hardness assumptions (factoring, discrete log) that provable security was built to analyze; Goldwasser and Micali's semantic-security definition was framed for public-key encryption.
Carried by Shafi Goldwasser; Silvio Micali.
Elliptic-Curve Cryptography grew out of Public-Key Cryptography in Applied Cryptography
Public-key cryptography provided the template of trapdoor and discrete-log systems that elliptic-curve cryptography reimplemented over elliptic curves.
Carried by Neal Koblitz; Victor S. Miller.
Elliptic-Curve Cryptography grew out of Public-key cryptography in Cybersecurity
Elliptic-curve cryptography is a branch of public-key cryptography: Koblitz and Miller took the Diffie–Hellman–Merkle group-based key exchange and instantiated it in elliptic-curve groups.
Carried by Neal Koblitz; Victor S. Miller.

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 CryptographyRelated fields
Fields its ideas are linked to
- Applied Cryptography 12 links
- Cybersecurity 5 links
- Digital Privacy 5 links
- Quantum Computation 5 links
- Computational Number Theory 4 links
- Quantum Information 3 links
- Complexity Theory 3 links
- Field And Galois Theory 1 link
- Epigraphy And Papyrology 1 link
- Coding Theory 1 link
- Communication 1 link
- Communication Systems 1 link