Transcript CIS 5371 Cryptography

CIS 5371 Cryptography
2. Perfect Secret Encryption
1
Encryption
Encryption
encryption key
Plaintext
Ciphertext
decryption key
Decryption
2
Encryption schemes

3
Encryption schemes
Definition
An encryption scheme (Gen,Enc,Dec) over message space
M is perfectly secret if for every probability distribution
over M, every message mM, and every ciphertext cC
for which Pr[C = c]  0:
Pr[M = m | C = c] = Pr[M = m]
Convention:
We consider only probability distributions over M, C that
assign non-zero probabilities to all mM and cC.
4
Encryption schemes
Lemma 1
An encryption scheme (Gen,Enc,Dec) over message
space M is perfectly secret if and only if for every
probability distribution over M, every message
mM, and every ciphertext cC:
Pr[C = c | M = m] = Pr[C = c]
5
Encryption schemes

6
Encryption schemes
An equivalent definition for perfect secrecy
7
Encryption schemes

8
Shannon’s Theorem
Theorem
Let (Gen,Enc,Dec) be an encryption scheme over a
message space M for which |M|= |K|=|C|. The scheme
is perfectly secret if and only if:
1. Every key kK is chosen with equal probability 1/|K| by
algorithm Gen.
2. For every mM and every cC there is a unique key kK
such that Enck(m) outputs c
9
Encryption algorithms

10
Encryption schemes
Theorem
The one time pad encryption scheme is
perfectly secret.
11
Limitations to perfect secrecy
Theorem
Let (Gen,Enc,Dec) be a perfectly secret
encryption scheme over message space
M, and let K be the key space as
determined by Gen.
Then |K|  |M| .
12