Information-theoretic security of ciphers
The quality of a cipher can be described by checking its resistance to strictly technical attacks (that is bypassing the human factor). The highest defined level of security is referred to as the perfect security. In fact, to describe the practical security of ciphers, the semantic security property is usually used.
P[E(k, m1)=c] = P[E(k, m2)=c]
- the key k belongs to a set K of all possible keys,
- M is a set of all possible messages,
- C is a set of all possible ciphertexts.
- Given a ciphertexts it is not possible to distinguish between two possible sent messages
- Given a ciphertexts it is not possible to find out anything about sent text
- It is not possible to break the cipher using ciphertext-only attacks
- |K| >= |M|
The one-time pad is the only cipher known to have perfect secrecy.
Any probabilistic, polynomial-time algorithm (PPTA) which receives the ciphertext created by a semantically secure cipher of any certain message and its length cannot determine any partial information on the message with probability non-negligibly higher than all other PPTAs that only have access to the message length and don't have access to the ciphertext.
One can prove that the OTP cipher is semantically secure if it uses a random encryption key. Similarly, each stream cipher can have the property, if a pseudorandom generator used in the cipher is secure.