# Homework 0

CSE 208: Advanced Cryptography (Winter 2017)

Instructor: Daniele Micciancio

Due: Tuesday January 17, at the beginning of class.

## Multimessage-security

Consider the following definition of multi-message security for public key encryption.

Let `(KeyGen,Enc,Dec)` be a public key encryption (PKE) scheme as defined in lecture and satisfying the usual correctness requirement `Dec(sk,Enc(pk,m)) = m` for all `(pk,sk) <- KeyGen(t)`.

A left-right encryption oracle is a randomized algorithm LRpkb(m0, m1)=Enc(pk, mb) parametrized by a bit b ∈ {0, 1} and public key pk that on input two messages m0, m1, outputs the encryption (under pk) of one of them, selected according to the bit b.

An adversary in the multi-message IND-CPA definition of security for PKE is an algorithm ALR(pk) that takes a public key pk as input, and it is given oracle access to an left-right encryption oracle LR. For any bit b ∈ {0, 1}, define the output of the adversary in the multi-message IND-CPA game as

Outb[A]={ALRpkb(pk)∣(pk, sk)←KeyGen(t)}

Definition: A PKE scheme is n-IND-CPA secure if for any PPT adversary A making at most n queries to its LR-oracle, the probability |Pr{Outb[A]=b ∣ b ← {0, 1}}| is negligible in the security parameter t.

A scheme is multi-message IND-CPA secure if it is n-IND-CPA secure for any n polynomial in the security parameter t.

Notice that the IND-CPA security definition given in class corresponds to 1-IND-CPA, i.e., the special case where A is allowed to make exactly one query to the LR-oracle. So, clearly, any PKE scheme that satisfies the n-IND-CPA security definition is also IND-CPA secure according to the definition given in class.

Problem 1: Show that the converse is also true, i.e., any 1-IND-CPA secure PKE scheme is also n-IND-CPA secure. Hint: show how any adversary attacking n-IND-CPA security with advantage ε can be converted into an adversary attacking 1-IND-CPA security with advantage ϵ/n.

## Secret Key Encryption

Now consider the case of private key encryption. A private key encryption scheme is defined just like a PKE, with the only difference that pk=sk, i.e., the same key is used both to encrypt and decrypt. n-IND-CPA security is defined similarly, with the only difference that the adversary is not given the key pk = sk as input. In other words, sk ← KeyGen(t) outputs just one key, and the output of an adversary A in the security game is

Outb[A]={ALRskb() ∣ sk ← KeyGen(t)}

Definition:
A private key encryption scheme is n-IND-CPA secure if for any PPT adversary `A` making at most n queries to its LR-oracle, the probability |Pr{Outb[A]=b ∣ b ← {0, 1}}| is negligible in the security parameter t.

Problem 2: Prove that in the case of private-key encryption, 1-IND-CPA security does not imply n-IND-CPA security (even for n = 2). Specifically, give a private key encryption scheme that is 1-IND-CPA secure, but not 2-IND-CPA secure.