One-time pad Created 2026-09-24 Updated 2026-10-14
For messages in a finite additive group, a one-time pad encrypts as , where the key is uniform and independent of , as long as the message, and never reused. Then is uniform and independent of , giving perfect secrecy.
Let be the effective mask. For each position ,
Thus the mask is always a palindrome, even though itself is uniformly random. The exclusive or of the ciphertext bits in a mirror pair is
because the equal mask bits cancel. The observer learns the corresponding plaintext parity exactly. If is odd, the middle mask bit is also zero, so the middle plaintext bit is exposed directly.
An explicit failure of perfect secrecy works for every . Choose uniformly from and . For , the ciphertext is a palindrome with probability one. For and , toggling just the first bit breaks the mirror equality, so the ciphertext is a palindrome with probability zero. For , the effective mask is zero and . Observing therefore distinguishes these two messages perfectly.
There are only possible effective masks, each equally likely. Hence even a fresh -bit key supplies at most independent masking bits in this construction. Choosing a long, uniform, one-use key is insufficient if the encryption transformation collapses its randomness.
Figure 1.
Mirror-paired mask bits cancel, exposing the plaintext parity in each pair
. Details.
Perfect secrecy means that observing the ciphertext changes no probability concerning the plaintext. For every distribution of the message , and every with ,
Equivalently, for every pair the conditional probability distributions of the ciphertext are identical:
The randomness here comes from independent key generation and any encryption randomness. The claim is information theoretic: unlimited computation cannot extract information about from beyond what was known beforehand.
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.
Perform every addition in the finite field . From the two transmitted strings and one obtains
Choosing one candidate value of recursively determines , and hence determines the candidate plaintext . There are only two candidates: changing complements every recovered key bit and every plaintext bit. The information that the message makes sense normally selects the intended candidate.
Once this ambiguity is resolved, any other ciphertext positions encrypted with the recovered segment can be decrypted. Key bits outside that segment remain independent and uniformly distributed, so this mistake gives no information about messages using only those bits. This is the two-time pad attack: reusing related one-time-pad key material destroys perfect secrecy.
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
Perfect secrecy of Shamir's threshold scheme Created 2026-09-29 Updated 2026-11-05
In Shamir's secret sharing, observing any shares leaves the secret's prior distribution unchanged. In particular, the posterior distribution is uniform if the prior distribution was uniform; uniformity of the secret is not required for perfect secrecy.
To prove this, fix distinct nonzero evaluation points and a candidate secret . The evaluations impose independent linear equations on the random coefficients. The evaluation matrix has rank : its first columns form a Vandermonde matrix multiplied by a nonsingular diagonal matrix of nonzero evaluation points. Every observed share tuple therefore has exactly compatible coefficient tuples. Since the coefficients were independently uniform, its conditional probability is
independent of . Thus the shares and the secret are independent random variables, which proves perfect secrecy.[ref]