Weel 3: Advantage and CPA, CCA1, CCA2

Question 1

Define “Advantage” in Information Security.

Answer 1

Adv(A) = |Pr(b’= b) - ½ |

Question 2

What are the Advantage cases?

Answer 2

1. A wins > 50% Adv(a) =| p - ½ | for p > ½ therefore Adv(A) > 0 BAD
2. A wins < 50% Adv(a) =| p - ½ | for p < ½ therefore Adv(A) > 0 BAD
3. A wins = 50% of time Adv(a) = 0 (no advantage) GOOD

Question 3

If key length is 3 bits what is key space?

Answer 3

2^3 = 8

Question 4

Given size of key k, what is the probability that the adversary guesses the key correctly?

Answer 4

1 / ( 2^k )

Question 5

What is a polynomially bounded adversary?

Answer 5

An adversary that can make n guesses where n is polynomially related to keyspace k.

Question 6

When is e(k) negligible?

Answer 6

When 1/e(k) < |1/poly(k)|

Question 7

Define a “IND-EAV secure” crypto system?

Answer 7

A cryptosystem is indistinguishable under eavesdropping (IND-EAV secure) if no PPT-bounded adversary has a real (non-negligible) advantage of winning the EAV game.

Question 8

What are the steps of a Chosen Plaintext Attack (CPA) Game?

Answer 8

• B generates key
• A sends polynomially many query messages q to B
• B encrypts q and sends back to A
• A sends challenge message m0 and m1 to B
• B randomly chooses message, encrypts and sends to A
• A guesses which message was encrypted

Question 9

What is the difference between Deterministic and Non-deterministic encryption?

Answer 9

Deterministic - two identical messages encrypted with same key result in identical ciphertexts

Non-deterministic - two identical messages encrypted with same key result in different ciphertexts

Question 10

How are Non-Deterministic encryption ciphertexts decrypted?

Answer 10

Random value used in encryption is made irrelevant.

Question 11

What are the steps for the Non-Adaptive Chosen Ciphertext Attack (CCA1) Game?

Answer 11

CPA game + Adversary can make decryption queries until the challenge ciphertext is issued

Rules

• B will not decrypt challenge messages m0 and m1
• B will only decrypt valid ciphertext

Question 12

What are the steps for the Adaptive Chosen Ciphertext Attack (CCA2) Game?

Answer 12

CPA game + adversary can make decryption queries before and after the challenge ciphertext is issued

Rules

• B will not decrypt challenge messages m0 and m1
• B will only decrypt valid ciphertext