Perfect Secrecy

What is a cryptosystem?

• Three finite sets:
  • $\mathcal {P}$ = the set of all possible plaintexts (e.g. of a certain length)
  • $\mathcal {C}$ = the set of all possible ciphertexts
  • $\mathcal {K}$ = the set of all possible keys

• Encryption and decryption functions such that for each k in $\mathcal {K}$:
  • e_k : $\mathcal {P}$$\to$$\mathcal {C}$
  • d_k : $\mathcal {C}$$\to$$\mathcal {P}$
  • d_k(e_k(P)) = P for all P in $\mathcal {P}$

Probability distributions

• Assume:
  • Pr$\nolimits_{{\mathcal{P}}}^{}$(P) probability distribution on plaintext space $\mathcal {P}$
  • Pr$\nolimits_{{\mathcal{K}}}^{}$(k) probability distribution on key space $\mathcal {K}$
  • Choosing the key and selecting the plaintext are independent
• These induce:
  • Pr$$\nolimits_{{\mathcal{C}}}^{}$$(C) = $$\sum_{{\substack{P \in \mathcal{P}, k \in \mathcal{K} e_{k}(P)=C}}}^{}$$Pr$$\nolimits_{{\mathcal{P}}}^{}$$(P)Pr$$\nolimits_{{\mathcal{K}}}^{}$$(k)
    probability distribution on ciphertext space $\mathcal {C}$
  • Pr$$\nolimits_{{\mathcal{P}}}^{}$$(P | C) = $${\frac{{\mathop{\rm Pr}\nolimits _{\mathcal{P} \times \mathcal{C}} (P \land C)}}{{\mathop{\rm Pr}\nolimits _{\mathcal{C}} (C)}}}$$ (by Bayes' Theorem)
    conditional distribution of plaintext given ciphertext
  • Pr$$\nolimits_{{\mathcal{P} \times \mathcal{C}}}^{}$$(P$$\land$$C) = $$\sum_{{\substack{k \in \mathcal{K} e_{k}(P)=C} }}^{}$$Pr$$\nolimits_{{\mathcal{P}}}^{}$$(P)Pr$$\nolimits_{{\mathcal{K}}}^{}$$(k)
    joint probability distribution of plaintext and ciphertext

Perfect Secrecy

Definition

A cryptosystem has perfect secrecy (or perfect security, or unconditional security) if for every P $\in$ $\mathcal {P}$ and C $\in$ $\mathcal {C}$,

Pr$$\nolimits_{{\mathcal{P}}}^{}$$(P | C) = Pr$$\nolimits_{{\mathcal{P}}}^{}$$(P).

Criterion 1

If a system has perfect secrecy, then for all P $\in$ $\mathcal {P}$, C $\in$ $\mathcal {C}$, there is a k $\in$ $\mathcal {K}$ such that e_k(P) = C.

Criterion 2

If a system has perfect secrecy, then

$$\left\vert\vphantom{\mathcal{K}}\right.$$$$\mathcal {K}$$$$\left.\vphantom{\mathcal{K}}\right\vert$$ $$\geq$$ $$\left\vert\vphantom{\mathcal{C}}\right.$$$$\mathcal {C}$$$$\left.\vphantom{\mathcal{C}}\right\vert$$ $$\geq$$ $$\left\vert\vphantom{\mathcal{P}}\right.$$$$\mathcal {P}$$$$\left.\vphantom{\mathcal{P}}\right\vert$$.

Criterion 3

Suppose $\left\vert\vphantom{\mathcal{K}}\right.$$\mathcal {K}$$\left.\vphantom{\mathcal{K}}\right\vert$ = $\left\vert\vphantom{\mathcal{C}}\right.$$\mathcal {C}$$\left.\vphantom{\mathcal{C}}\right\vert$ = $\left\vert\vphantom{\mathcal{P}}\right.$$\mathcal {P}$$\left.\vphantom{\mathcal{P}}\right\vert$. Then a system has perfect secrecy if and only if

(a)

every key is used with equal probability, and

(b)

for every P $\in$ $\mathcal {P}$ and C $\in$ $\mathcal {C}$, there is exactly one key k $\in$ $\mathcal {K}$ such that e_k(P) = C.

About this document ...

Perfect Secrecy

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.57)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -link 0 -split +0 -html_version 3.2,math perfect-secrecy.tex

The translation was initiated by Joshua R Holden on 2004-04-11