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.

Perfect Security

Definition A cipher (E, D) defined over (K, M, C) has perfect secrecy if for every two messages m1 and m2 (of the same size) belonging to M and for every c belonging to C, there is an equality:
P[E(k, m1)=c] = P[E(k, m2)=c]
where:
  • 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.

Semantic Security

Definition A cipher is semantically secure if knowledge of the ciphertext and the length of the original message, does not reveal any additional information on the original message that can be feasibly extracted.

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.

Date: 2020-03-09