Perfectly secret one-time encryption

From CRYPTUTOR

Jump to: navigation, search

Perfect secrecy is a security definition for one-time private-key encryption schemes. Unlike most definitions in modern cryptography, it is an information-theoretic definition which does not rely on any computational assumptions. As such, it is the highest level of security one can wish to achieve for a simple encryption scheme. However, it has several drawbacks, addressed below.

[edit]

Definition

A (one-time, private-key) encryption scheme has perfect secrecy if the following two probability distributions are equal for all messages m_1\, and m_2\,:

\{\mathsf{Enc}_k(m_1)\}_{k \gets \mathsf{KeyGen}} \equiv \{\mathsf{Enc}_k(m_2)\}_{k \gets \mathsf{KeyGen}}

In words, the distribution of ciphertexts of m_1\, (induced by the choice of key) is the same as the distribution of ciphertexts of m_2\,. An eavesdropping adversary sees only a sample from one such distribution, and perfect secrecy implies that this distribution is independent of the plaintext message.

Two other equivalent definitions of perfect secrecy are:

  1. SIM-onetime security and
  2. IND-onetime security.
[edit]

Drawbacks

  • Perfect secrecy is only for one-time encryption schemes. It does not consider what happens when an adversary sees encryptions of multiple messages using the same key.
  • It is possible to show that (essentially) the keyspace must be at least as large as the message space to achieve perfect secrecy. Thus, two parties must somehow be able to securely share a key which is as long as the message they intend to encrypt, giving a chicken-and-egg problem.
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Perfectly_secret_one-time_encryption"
Personal tools