Week 2b: IND-EAV and Perfect Secrecy

Question 1

What functions does an encryption system algorithm contain?

Answer 1

• key-gen algorithm
• encryption algorithm
• decryption algorithm

Question 2

What inputs/outputs does a key-gen algorithm take?

Answer 2

Input: nothing
Output: key

Question 3

What inputs/outputs does an encryption algorithm take?

Answer 3

Input: key, plaintext
Output: ciphertext

Question 4

What inputs/outputs does a decryption algorithm take?

Answer 4

Input: key, ciphertext
Output: plaintext

Question 5

What are the steps for the IND-EAV game?

Answer 5

1. B generates random key
2. A sends m0 and m1 to B
3. B selects m0 or m1, encrypts the message and sends ciphertext to A
4. A guesses which message was encrypted

Question 6

What does IND-EAV stand for?

Answer 6

Indistinguishability under eaves dropping.

Question 7

Define “perfect secrecy”.

Answer 7

• given a ciphertext c of message m the probability of guessing m is unchanged
• Pr[ M=m | C=c ] = Pr[ M=m ]

Question 8

Explain Shannon’s Perfect Secrecy Theorem.

Answer 8

A crypto system has perfect secrecy if
keyspace == ciphertext space == message space
and every key is used with equal probability