Editing One-time pad (section)

== Perfect secrecy ==
One-time pads are "[[Information-theoretic security|information-theoretically secure]]" in that the encrypted message (i.e., the [[ciphertext]]) provides no information about the original message to a [[cryptanalyst]] (except the maximum possible length<ref group="note">The actual length of a plaintext message can hidden by the addition of extraneous parts, called [[Padding (cryptography)|padding]]. For instance, a 21-character ciphertext could conceal a 5-character message with some padding convention (e.g. "-PADDING- HELLO -XYZ-") as much as an actual 21-character message: an observer can thus only deduce the maximum possible length of the significant text, not its exact length.</ref> of the message). This is a very strong notion of security first developed during WWII by [[Claude Shannon]] and proved, mathematically, to be true for the one-time pad by Shannon at about the same time. His result was published in the ''Bell System  Technical Journal'' in 1949.<ref name="Shannon">{{cite journal
 |last        = Shannon
 |first       = Claude E.
 |title       = Communication Theory of Secrecy Systems
 |journal     = Bell System Technical Journal
 |volume      = 28
 |issue       = 4
 |pages       = 656–715
 |date        = October 1949
 |url         = http://www3.alcatel-lucent.com/bstj/vol28-1949/articles/bstj28-4-656.pdf
 |doi         = 10.1002/j.1538-7305.1949.tb00928.x
 |access-date  = 2011-12-21
 |url-status = dead|archive-url  = https://web.archive.org/web/20120120001953/http://www.alcatel-lucent.com/bstj/vol28-1949/articles/bstj28-4-656.pdf
 |archive-date = 2012-01-20
|hdl = 10338.dmlcz/119717
 }}</ref> If properly used, one-time pads are secure in this sense even against adversaries with infinite computational power.

Shannon proved, using [[information theory|information theoretic]] considerations, that the one-time pad has a property he termed ''perfect secrecy''; that is, the ciphertext ''C'' gives absolutely no additional [[information]] about the [[plaintext]].<ref group="note">That is to say, the "'''information gain'''" or [[Kullback–Leibler divergence]] of the plaintext message from the ciphertext message is zero.</ref> This is because (intuitively), given a truly uniformly random key that is used only once, a ciphertext can be translated into ''any'' plaintext of the same length, and all are equally likely. Thus, the ''[[a priori (philosophy)|a priori]]'' probability of a plaintext message ''M'' is the same as the ''[[empirical knowledge|a posteriori]]'' probability of a plaintext message ''M'' given the corresponding ciphertext.

Conventional [[Symmetric encryption|symmetric encryption algorithms]] use complex patterns of [[Substitution cipher|substitution]] and [[Transposition cipher|transpositions]]. For the best of these currently in use, it is not known whether there can be a cryptanalytic procedure that can  efficiently reverse (or even [[Partial inverse|partially reverse]]) these transformations without knowing the key used during encryption. Asymmetric encryption algorithms depend on mathematical problems that are [[Super-polynomial time|thought to be difficult]] to solve, such as [[integer factorization]] or the [[discrete logarithm]]. However, there is no proof that these problems are hard, and a mathematical breakthrough could make existing systems vulnerable to attack.<ref group="note">Most asymmetric encryption algorithms rely on the facts that the best known algorithms for prime factorization and computing discrete logarithms are superpolynomial time. There is a strong belief that these problems are not solvable by a Turing machine in time that scales polynomially with input length, rendering them difficult (hopefully, prohibitively so) to be broken via cryptographic attacks. However, this has not been proven.</ref>

Given perfect secrecy, in contrast to conventional symmetric encryption, the one-time pad is immune even to brute-force attacks. Trying all keys simply yields all plaintexts, all equally likely to be the actual plaintext. Even with a partially known plaintext, brute-force attacks cannot be used, since an attacker is unable to gain any information about the parts of the key needed to decrypt the rest of the message. The parts of the plaintext that are known will reveal ''only'' the parts of the key corresponding to them, and they correspond on a [[Bijection|strictly one-to-one basis]]; a uniformly random key's bits will be [[Independence (probability theory)|independent]].

[[Quantum cryptography]] and [[post-quantum cryptography]] involve studying the impact of quantum computers on [[information security]].
[[Quantum computing|Quantum computers]] have been shown by [[Shor's algorithm|Peter Shor]] and others to be much faster at solving some problems that the security of traditional asymmetric encryption algorithms depends on. The cryptographic algorithms that depend on these problems' difficulty would be rendered obsolete with a powerful enough quantum computer.
One-time pads, however, would remain secure, as perfect secrecy does not depend on assumptions about the computational resources of an attacker.