Intro to Cryptography

Knowledge Map Atlas
What Cryptography Secures Kerckhoffs's Principle Breaking a Scheme What the Adversary Can Do Computational vs Unconditional Security The Shifting Ground

What Cryptography Secures

A message travels across a channel that someone else can read, alter, or forge. The sender wants the content hidden from everyone but the intended receiver. The receiver wants assurance that the message arrived unchanged, that it truly came from the claimed sender, and that the sender cannot later deny having sent it. Cryptography is the study of mathematical techniques that secure information against an adversary who controls the channel. It is one set of tools for information security, not the whole of it. Physical, procedural, and legal mechanisms address the rest.

What distinguishes the cryptographic viewpoint from ordinary engineering is the adversary. We design not against noise, accident, or average behavior but against an intelligent opponent who knows the system, chooses the worst case, and is bounded only by the resources available to that adversary. Every guarantee below is a guarantee made in the presence of such an opponent.

Definition: The Four Goals

Cryptography addresses four information-security goals, from which others are derived.

  1. Confidentiality keeps the content of information from all but those authorized to see it. (Secrecy and privacy are used synonymously with it.)
  2. Data integrity ensures that unauthorized alteration of data can be detected, where alteration includes insertion, deletion, and substitution.
  3. Authentication establishes identity. It splits into entity authentication (who one is communicating with) and data-origin authentication (the source of a message). Data-origin authentication implicitly provides data integrity, since a modified message has a changed source.
  4. Non-repudiation prevents an entity from later denying a previous commitment or action. Resolving such a dispute generally requires a trusted third party.

These goals are about the prevention and detection of cheating. The remainder of this page asks the question that any such guarantee must answer: when we say a scheme is secure, secure against what, and how is that claim made precise?

Kerckhoffs's Principle

To reason about confidentiality we first fix what an encryption scheme is. We work with a message space \(\mathcal{M}\) of plaintexts, a ciphertext space \(\mathcal{C}\), and a key space \(\mathcal{K}\). Each key selects a transformation that turns plaintext into ciphertext, and a matching transformation that reverses it.

Definition: Encryption Scheme (Cipher)

An encryption scheme, or cipher, consists of a family of encryption transformations \(\{E_e : e \in \mathcal{K}\}\), each an injective map \(E_e \colon \mathcal{M} \to \mathcal{C}\), together with a family of decryption transformations \(\{D_d : d \in \mathcal{K}\}\), with the property that for each encryption key \(e\) there is a unique decryption key \(d\) such that \[ D_d(E_e(m)) = m \quad \text{for every } m \in \mathcal{M}. \] This injectivity is essential, for otherwise a ciphertext would not determine its plaintext and decryption would be ambiguous. The pair \((e, d)\) is the key pair. The two keys may coincide.

We treat \(E_e\) here as a fixed map, so a given plaintext under a given key always produces the same ciphertext. Such a deterministic scheme is the natural starting point, but it carries a weakness. Identical plaintexts yield identical ciphertexts, so an observer learns when a message repeats. Removing this leak requires randomized encryption, where the same plaintext can map to many ciphertexts. We set that refinement aside here and return to it when security is made precise.

Two parties who wish to communicate confidentially agree on a key pair \((e, d)\). The sender transmits \(c = E_e(m)\), and the receiver recovers \(m = D_d(c)\). The question is what they must keep secret. One might try to hide the entire mechanism, including the spaces, the transformations, and the way the scheme is built. The principle that organizes modern cryptography rejects this.

Definition: Kerckhoffs's Principle

The security of an encryption scheme must rest entirely on the secrecy of the key, never on the secrecy of the algorithm. The spaces \(\mathcal{M}, \mathcal{C}, \mathcal{K}\) and the families \(\{E_e\}, \{D_d\}\) are assumed to be public knowledge. The only secret is the particular key pair \((e, d)\) in use.

A physical combination lock is the standard analogy. Its mechanism is mass-produced and available to anyone, yet the lock is secure because the combination is chosen and held by its owner. If the owner suspects the combination is known, they reset it without replacing the lock.

Keeping the mechanism secret as well can add a layer of difficulty for an attacker, but a scheme must not depend on it. Secret mechanisms are leaked, reverse-engineered, and reconstructed, and a design whose safety relies on concealment has no defense once concealment fails. Reducing all secrecy to a short, replaceable key is what makes a scheme analyzable, auditable, and recoverable after exposure.

The same reduction turns security into a mathematical question. Once the adversary is granted full knowledge of the scheme and is missing only the key, "secure" means precisely that such an adversary still cannot recover the plaintext. The next section makes cannot precise.

Breaking a Scheme

Under Kerckhoffs's principle the adversary knows the scheme and lacks only the key. What does it mean for such an adversary to succeed?

Definition: Breakable

An encryption scheme is breakable if a third party, without prior knowledge of the key pair \((e, d)\), can recover plaintext from the corresponding ciphertext within some appropriate time frame, by a procedure that succeeds with non-negligible probability.

Two phrases carry the weight. Within some appropriate time frame ties security to the lifespan of the data. An instruction to buy a stock may need to stay secret for minutes, a state secret for decades. A scheme is secure only relative to how long the protected information must outlast the attacker's effort.

Non-negligible probability rules out luck from the other side. A one-off lucky guess of the key is always possible, but its chance shrinks faster than the inverse of any polynomial in the key length, so it is little-o of every such inverse and does not count as breaking the scheme. An attack breaks a scheme only if it succeeds often enough to matter, not merely sometimes by chance.

Since the scheme is public, there is always one attack available, namely trying every key. Enumerate \(\mathcal{K}\), decrypt the ciphertext under each candidate, and recognize the correct plaintext when it appears. This exhaustive search always works in principle, so its cost sets a baseline every scheme must clear. If \(|\mathcal{K}|\) is small the scheme is broken outright. The key space must therefore be large enough that running through it is infeasible. The designer aims for more than a large key space, though. Exhaustive search should be the best available attack, so that no shortcut beats brute force.

The distinction matters because a large key space is necessary but not sufficient. A simple substitution cipher over the English alphabet has \(26! \approx 4 \times 10^{26}\) keys, and a polyalphabetic variant can reach \((26!)^3 \approx 7 \times 10^{79}\). Both counts are far beyond any exhaustive search. Yet both ciphers are weak. Frequency analysis recovers the plaintext without touching more than a negligible fraction of the key space, because the structure of the language leaks through the ciphertext. The right measure of security is therefore not the number of keys but the cost of the best attack, which may be vastly cheaper than brute force.

The word "infeasible" must now be pinned down, and this is where complexity theory enters. We already have two tools. The running time of an algorithm, analyzed asymptotically, measures how its cost grows with the size \(n\) of its input. The class \(P\) of problems decidable in polynomial time captures which problems count as efficiently solvable. "Computationally infeasible" means, at first approximation, that no attack runs in polynomial time in the key length. The work to break the scheme then outpaces any feasible adversary as the key length grows. The security of a cipher is thus a claim about the complexity of the problem an attacker must solve.

Phrasing security through complexity also reveals its fragility. The claim "no efficient attack exists" is a statement about what algorithms are possible, and the boundary of the efficiently solvable is not fully mapped. The relationship between efficient solution and efficient verification is itself one of the deepest open questions in the subject. A scheme rests on the belief that a particular problem is hard, and that belief can be revised. But the cost of an attack also depends on something we have not yet fixed: what the attacker is allowed to see and do.

What the Adversary Can Do

The question from the first section, "secure against what?", has a second half. Beyond how much computation the adversary commands, security depends on what access they have to the channel and to the scheme in operation. A scheme that resists an eavesdropper may fall to an attacker who can also inject messages. A scheme safe against an attacker who only sees ciphertext may leak under one who can choose the plaintexts that get encrypted. Stating a security claim means stating which adversary it holds against.

The coarsest split concerns what the adversary does to the channel. A passive adversary only monitors it, and thus threatens confidentiality alone. An active adversary may also alter, insert, or delete transmissions, and so threatens data integrity and authentication as well as confidentiality. Three of the four goals from the first section map onto this split, and non-repudiation, the fourth, concerns a dispute after the fact rather than the channel. Confidentiality must hold even against a passive listener, while integrity and authentication are precisely the goals an active adversary attacks.

Definition: Attack Models on Encryption

Attacks on an encryption scheme are classified by what the adversary has access to, in increasing order of power:

  1. Ciphertext-only. The adversary sees only ciphertexts. A scheme that falls to this is considered completely insecure.
  2. Known-plaintext. The adversary holds some plaintext-ciphertext pairs and uses them to attack other ciphertexts.
  3. Chosen-plaintext. The adversary obtains ciphertexts for plaintexts of their own choosing, then attacks previously unseen ciphertexts.
  4. Adaptive chosen-plaintext. The adversary mounts a chosen-plaintext attack in which each chosen plaintext may depend on ciphertexts seen so far.
  5. Chosen-ciphertext. The adversary obtains plaintexts for ciphertexts of their choosing. Such access might come, for instance, from temporary use of decryption equipment whose embedded key stays hidden. In the strongest form the adversary may keep querying the decryption of any ciphertext other than the target, even after receiving the target, and still must be unable to recover its plaintext.

The list grows in adversary power. Anything broken under a ciphertext-only attack is broken under all the others, and resistance to chosen-ciphertext attack is a far stronger claim than resistance to ciphertext-only attack. A scheme is expected to remain secure even when the adversary may choose what gets encrypted and decrypted. The demand looks paranoid until one realizes that real systems routinely encrypt attacker-influenced data and decrypt attacker-supplied ciphertexts. The same hierarchy carries over, with the goal of forgery rather than decryption, to digital signatures and message authentication codes.

With the adversary's computational power and access both fixed, we can finally separate the two fundamentally different grades of security a scheme might offer.

Computational vs Unconditional Security

Definition: Unconditional Security

A scheme is unconditionally secure if it withstands an adversary with unlimited computational resources. For an encryption scheme this is called perfect secrecy. Observing the ciphertext gives the adversary no information about the plaintext, so the uncertainty about the plaintext after seeing the ciphertext equals the uncertainty before.

Perfect secrecy is the strongest guarantee imaginable, since it holds against an opponent with no bound on computation at all. It is also achievable. The one-time pad, which combines each plaintext symbol with a fresh, uniformly random key symbol used only once, is unconditionally secure.

The catch is structural. A necessary condition for an encryption scheme to be unconditionally secure is that the key be at least as long as the message. Perfect secrecy demands as much fresh secret key as there is data to protect, which defeats the usual purpose of cryptography, namely protecting a great deal of communication with a small, manageable secret. Unconditional security is real, but for most purposes it is a luxury one cannot afford.

Worse, the guarantee is unavailable for public-key cryptography altogether. If the encryption transformation is public, an adversary with unlimited resources can simply encrypt every candidate plaintext until the observed ciphertext appears. The plaintext is thus determined in principle. No public-key scheme can be unconditionally secure. The security on which practical communication rests therefore cannot be the unconditional kind. It must be computational.

Definition: Computational Security

A scheme is computationally secure if the computational effort required to defeat it, using the best known method, exceeds by a comfortable margin the resources of the anticipated adversary. The work factor \(W_d\) is the minimum amount of work, measured in elementary operations, needed to recover the secret key. A scheme is regarded as secure for practical purposes when \(W_d\) is large enough that the effort is out of reach within the data's useful lifespan.

Every public-key scheme has security of this kind, and so does any scheme whose key is shorter than its data. Such security does not promise that no attack exists, only that no feasible attack exists. A careful statement of the definition must therefore distinguish two quantities. The true work factor \(W_d\) is the cost of the best attack that could ever exist. It is generally unknown and unprovable, and no one has shown a large lower bound on it for any public-key scheme. What is actually measured is the historical work factor \(\overline{W}_d\), the cost of the best attack known at a given time. Computational security is in practice a claim about \(\overline{W}_d\). It asserts that, with the best algorithms known at the time, breaking the scheme is infeasible.

The gap between \(\overline{W}_d\) and \(W_d\) is the whole exposure of modern cryptography. The historical work factor \(\overline{W}_d\) is an upper bound on \(W_d\) that moves downward with every algorithmic advance. When a faster attack is discovered, \(\overline{W}_d\) drops, and a scheme believed secure yesterday may be broken today, with no change to the scheme itself. Security under this definition is provisional by construction. It is the best estimate available, not a theorem.

Where a scheme's hardness can be tied to a well-studied problem widely believed to be intractable, such as integer factorization or the discrete logarithm, confidence is higher. The tie, however, is to a conjectured hardness, not a proven one. The substance of everything that follows is the mathematics that makes those problems hard, together with the question of whether they truly are. Their hardness is also exactly what a sufficiently different model of computation could overturn.

The Shifting Ground

A historical work factor is measured against a model of computation, which fixes what counts as an elementary operation and what an algorithm is allowed to do. Change the model, and the cost changes. For public-key cryptography the change is not hypothetical.

A quantum computer is a different model of computation, and for two of the problems on which public-key cryptography is built it is dramatically faster. Shor gave a quantum algorithm that solves both integer factorization and the discrete logarithm in time polynomial in the input size [1]. No efficient classical algorithm is known for either problem, and RSA, Diffie-Hellman, and elliptic-curve schemes depend on their presumed hardness. Against a large-scale quantum computer, the historical work factor for these schemes collapses from infeasible to polynomial. The schemes are not merely weakened but broken.

Two clarifications keep this honest. First, the threat is conditional on hardware. Shor's algorithm breaks these schemes only once a quantum computer large and stable enough to run it on cryptographically relevant key sizes exists, and as of 2026 no such machine had been built. The condition has teeth even before it is met. An adversary can record encrypted traffic and decrypt it once such a machine arrives. Under this harvest-now-decrypt-later strategy, data that must stay secret for a decade is exposed as soon as such a machine is expected within that decade.

Second, the quantum threat is not universal. It targets the specific algebraic structure that Shor's algorithm exploits. The generic quantum speedup against symmetric-key ciphers and hash functions is the quadratic one from quantum search, and doubling key and output lengths answers it.

Math \(\leftrightarrow\) CS: What Survives

The response to Shor was standardized in 2024, when three algorithms were issued as post-quantum standards: a key-encapsulation mechanism and a digital-signature scheme built on the hardness of structured-lattice problems ([2], [3]), and a signature scheme resting on the preimage and second-preimage resistance of hash functions ([4]).

The split is the lesson of this page made concrete. The schemes that Shor's algorithm breaks are exactly those whose security is tied to factoring and the discrete logarithm. The schemes that survive are tied either to different conjectured-hard problems, namely lattice problems, or to the basic one-wayness of a hash, which a model change does not obviously help. What is replaced is the assumption about which problem is hard. What endures is the framework of Kerckhoffs's principle, the definition of breaking, and security as the complexity of an attacker's problem.

References