Cryptographic key 2026-11-05
A cryptographic key is a parameter selecting a particular transformation from a family of algorithms in cryptography. For an encryption family, correctness requires
for every allowed plaintext and appropriate encryption/decryption keys. In symmetric-key cryptography, the communicating parties share a secret key. In public-key cryptography, the public encryption or verification key is paired with a private decryption or signing key.
For a one-bit example, and recover the message because applying exclusive or twice with the same bit cancels it. The one-time pad extends this to a uniformly random independent key as long as the message. Its secrecy depends on the key distribution and use, not on hiding the XOR algorithm. The number of possible keys gives a brute-force search space, but key length alone does not establish the security of a cryptographic construction.
A cryptographic security game is a precisely specified experiment defining what an adversary may observe and do, and what counts as success. Its rules include key generation, random choices, permitted queries, resource limits and a winning condition. Security statements bound the winning probability or a specified cryptographic distinguishing advantage, often as a function of a cryptographic security parameter. A reduction proves a result about that defined experiment, not every informal meaning of the word secure.[ref]
For an original one-challenge confidentiality game, an adversary chooses two equal-length plaintexts . A challenger samples an independent uniform bit , encrypts , and gives the ciphertext to the adversary, which returns a guess . In this simplified game there are no additional encryption or decryption queries. Define
Random guessing has advantage zero. A success probability gives advantage . Another convention doubles this value; stating the normalization avoids a factor-of-two ambiguity when comparing bounds.
The one-time pad supplies a complete worked example. Let messages and the independently uniform key contain bits, and set . For any fixed -bit string and either challenge bit,
since exactly one key gives that ciphertext. The ciphertext distribution is identical for and , so no function of it and the chosen messages can outperform guessing. The advantage is zero in this game.
Changing the rules can change the result. Reusing the pad for another message supplies the relation . A chosen-plaintext attack game grants access to encryptions selected by the adversary; a chosen-ciphertext attack game grants additional decryption access with carefully stated restrictions. The proof for the one-challenge experiment does not establish security under those extra observations.
A forgery game for a message authentication code instead asks for an accepted message/tag pair meeting its freshness condition. That is a different winning event from guessing an encrypted message. The cryptographic security game makes these distinctions inspectable and provides the exact target for a security reduction.
Cryptographic simulator 2026-11-05
A cryptographic simulator is an algorithm in a security proof that reproduces an adversary's externally observable behavior using the interfaces and cryptographic leakage allowed by an ideal cryptographic functionality. In universal composability, substituting it for the real adversary should leave every allowed cryptographic environment unable to distinguish real and ideal executions efficiently.[ref]
The central question is what information the simulator receives. An original elementary example uses a one-time pad. For a fixed -bit message , let its fresh secret key be uniform on . Its ciphertext is , where is bitwise exclusive or. For every -bit value ,
A simulator told only can therefore reproduce this one ciphertext's distribution by generating independent uniform bits, without knowing . With , each of the 32 possible ciphertexts has probability in both constructions. This is a direct distribution calculation, not a complete universal composability proof for a messaging system: other visible inputs, outputs and correlations would also need to match.
Now modify the toy system so its visible packet includes a secret input bit in the clear. Suppose the cryptographic environment selected uniformly and the ideal service reveals neither nor any correlated information before the simulator must report its guessed packet bit . In the real system the environment's test succeeds with probability one. Any simulator whose information is independent of succeeds with probability , even without a computation bound. The cryptographic distinguishing advantage is therefore .
Allowing the ideal service to reveal would remove that particular simulation obstacle, but would specify a different disclosure policy. A valid simulator must use the actual permitted cryptographic leakage, rather than assume access to an honest party's private data.
More generally, reproducing a cryptographic transcript requires its correlations with the cryptographic environment's state to be correct. Sampling plausible-looking individual messages is insufficient. Efficiency also matters: an unbounded reconstruction algorithm does not supply a polynomial time simulator when the security definition requires one.
Let and choose uniformly from the finite family . All bounds below must hold for every pair of distinct inputs .
A universal hash family, also called universal2, satisfies . A strongly universal hash family satisfies
Thus the two outputs are independent and uniform; summing over gives the collision condition. An almost strongly universal hash family permits a larger conditional guessing bound. In the -almost-strongly-universal convention used here,
equivalently . Necessarily , with giving strong universality. Stating this normalization matters because the name alone does not specify the allowed forgery probability.
Here is an explicit polynomial almost strongly universal hashing construction and a one-use message authentication protocol. Use a publicly specified finite field , where . Encode a fixed-length -bit message as field elements , padding the final block in a fixed way. Both parties know the length, so this encoding is injective. They share independent uniform secret field elements , requiring shared secret bits. Define
For every message, the output is uniform because of . For distinct messages and prescribed tags , the condition determines exactly one value of for each . The remaining condition is
Its left-hand side has a nonzero coefficient of positive degree, so subtracting the specified constant gives a nonzero polynomial of degree at most . By the root bound for a polynomial, there are at most possible field elements . Consequently
and this is an -almost-strongly-universal family with , provided . The powers start at one deliberately: a message coefficient at power zero could give a known constant tag shift, allowing a deterministic substitution.
Alice sends the message and its tag over the public channel. Bob accepts only if his independently computed tag agrees. An attacker who has seen no tag guesses one with probability . After seeing a valid pair , an attacker substituting a different message and any chosen tag succeeds with conditional probability at most . This remains true when the choice of depends on the observed pair: the bound is uniform over all those choices. More explicitly, the observed tag leaves uniform because each possible has exactly one compatible secret mask .
For a desired forgery bound , choose . Since and , the substitution bound is at most . The secret requirement is
For a long message this is much shorter than its bits. This is Wegman–Carter authentication: a keyed hash plus a fresh secret one-time pad on the tag. It authenticates the message rather than concealing its contents. Use the key once for the guarantee just established; multiple authenticated messages require fresh masks and a reuse security analysis. Authenticate lengths and sequence identifiers too if variable lengths or replay protection are required.
Use the BB84 protocol to establish a secret random key, then encrypt the actual message with a one-time pad. Alice chooses independent random bits and independently chooses between the computational orthonormal basis and the diagonal basis , where . She sends one photon or other qubit in each corresponding state. Bob independently chooses one of the two bases for each measurement.
Over an authenticated public classical channel, they announce their bases but not their bit values. They retain only positions where their bases match; absent disturbance these sifted bits agree. They disclose and discard a randomly selected test sample to estimate the error rate. If it is too large they abort. Otherwise they perform information reconciliation and privacy amplification to produce a shared key about which an eavesdropper has negligible information. Authentication is essential: without it, an active attacker can impersonate the two parties. It may use a previously shared short authentication key, subsequently replenished from the new secret key.
The no-cloning theorem prevents an attacker from copying an unknown nonorthogonal state perfectly: preservation of inner products would require , impossible when its modulus is strictly between zero and one. In a simple intercept-and-resend attack, Eve chooses the wrong basis with probability , and then introduces a wrong sifted bit with probability . Thus the test error rate is , and the probability that independent tested bits show no error is . More general attacks are handled by bounding Eve's information from the observed statistics and shortening the reconciled key through privacy amplification.
Finally Alice sends , using a uniform independent key of the message's length exactly once. The one-time pad makes the ciphertext independent of the message. The security claim is secrecy with arbitrarily small failure probability after testing and privacy amplification, not that a finite quantum transmission can never be disturbed or intercepted. The scheme assumes trusted devices and an authenticated classical channel; it does not rely on a computational hardness assumption.
A cipher has perfect secrecy when the conditional probability of every plaintext given a ciphertext equals its prior probability: whenever . Equivalently, the plaintext and ciphertext are independent random variables.
Fix a ciphertext that can occur. Perfect secrecy requires every possible plaintext to remain possible after observing . For a deterministic decryption rule, two different plaintexts producing require two different keys, so the key space has cardinality at least that of the message space.
In a one-time pad, the message and key belong to the same finite additive group, the key is uniform and independent of the message, and encryption is . For every there is exactly one key , so
independent of . Bayes' theorem then gives , proving perfect secrecy.
Alice and Bob need a uniformly random secret key known only to them. Alice publicly sends the one-time pad ciphertext , and Bob recovers . For every observed and possible message there is exactly one equally likely key , so is independent of and Eve learns nothing.
A one-time pad over the finite additive group uses a key that is uniform on , independent of the plaintext , as long as the plaintext, and never reused. Encryption and decryption are
For independent random variables , conditioning reduces entropy and translation by a known element of the finite additive group preserves entropy, so
Interchanging and gives , hence
This is the entropy of a sum of independent finite-group variables.
The result explains why adding independent pad symbols cannot reduce uncertainty. For a uniform pad, is itself uniform and is independent of , which is the perfect-secrecy property. Independence is necessary: if is nonconstant and , then is constant, so
This is an entanglement-based quantum key distribution scheme of the type proposed by Artur K. Ekert.[ref] The measurements generate correlated random data; Alice does not choose a message by choosing their random outcomes.
After the measurements, Alice and Bob announce their basis choices over an authenticated public channel. They retain the pairs with equal axes, here and , and Bob flips his outcome signs to match Alice's bits. They sacrifice a random subset for error estimation and use the appropriate other setting combinations to estimate . In the ideal source the same-axis bits match after the flip and ; the specified intercept-resend attack cannot reproduce that value.
A practical protocol includes information reconciliation, an accounting of information leaked publicly, and privacy amplification. It must abort when its statistical security conditions fail. Authentication is essential: a completely unauthenticated public channel permits a man-in-the-middle attack. A Bell-violation observation alone, without sampling, device and adversary assumptions and a finite-key analysis, is not a proof that Eve knows no key bits.
With a sufficiently uniform secret shared key of the required length, Alice can send publicly using a one-time pad; Bob recovers . The pad must be secret, as long as the protected message, and never reused. A complete security proof makes the probability or distinguishing advantage of failure small under stated assumptions. The ideal exam correlations diagnose the stated attack; they do not provide an unconditional guarantee against every attack or implementation fault.
Security reduction 2026-11-05
A security reduction turns an adversary breaking one stated cryptographic property into an algorithm breaking another property or solving an assumed-hard problem. It specifies the simulation given to the adversary, the relation between success probabilities and the additional computation required. A primitive's hardness assumption can then imply a bound for the constructed scheme.[ref]
An original reduction illustrates this without a numerical loss. Let a pseudorandom generator expand a uniformly sampled -bit seed into an -bit string . Consider one-use encryption for -bit messages. Suppose adversary distinguishes which of was encrypted in the one-challenge cryptographic security game.
Construct a distinguisher given a string that is either a generator output or uniformly random. Run to obtain its message pair, select an independent uniform bit , and give it . Output one exactly when guesses correctly. If , this is the real encryption experiment. If is uniform, it is a one-time pad, and the success probability is . Therefore
Any nonzero advantage for that encryption game gives the same distinguishing advantage against the generator. The reduction adds the challenge-bit choice, an exclusive or and bookkeeping to the cost of running . It establishes this one-use confidentiality result, without claiming authenticity or safe pad reuse.
Other reductions lose probability or require more computation. For a separate stipulated bound,
an adversary with advantage , and implies primitive advantage at least . Conversely, a primitive bound at the reduction's actual running time gives only the scheme bound . The coefficient and additive term are original illustrative values, not a published bound for a named cipher.
The cryptographic security game and resource accounting remain part of the theorem. A proof cannot transfer a primitive bound stated for a small computation budget to a reduction that exceeds it, or replace the exact scheme's assumptions by a different informal hardness claim.
Symmetric-key cryptography uses shared secret key material for cryptographic operations, including encryption and authentication. In a symmetric encryption scheme, a recipient holding the secret key can recover the plaintext from a ciphertext. Keeping the algorithm public does not prevent security: the secret is the key, not the procedure.
For example, a one-time pad encrypts a bit string as and decrypts with . Perfect secrecy requires an independently uniform secret key as long as the message and never reused. Reusing it gives , exposing a relation between messages. Ordinary efficient symmetric ciphers instead offer computational guarantees under stated assumptions. Confidentiality alone does not ensure message integrity; authenticated encryption addresses both.[ref]