Crypto 101: IND-CPA and IND-CCA

This post will cover the definitions of IND-CPA and IND-CCA.

All adversaries are polynomial time unless noted otherwise.

Note that these definitions work for both symmetric and public key encryption.

IND-CPA i.e chosen plaintext attack is what it sounds like, attacker chooses 2 plaintexts m0 and m1 and given a ciphertext has to guess whether the ciphertext is the encryption of m0 or m1.

IND-CPA:

  1. Adv generates 2 same-length messages m0 and m1.
  2. Encryption oracle encrypts a random message from (m0,m1).

Adv is given unrestricted encryption oracle access (can query anything anytime) and has to guess which message was encrypted. If Adv wins with probability <= 1/2 + negl then IND-CPA secure else not. Encryption oracle uses its own generated key Gen(1^n).

IND-CCA:

  1. Adv generates 2 same-length messages m0 and m1.
  2. Encryption oracle encrypts a random message from (m0,m1). [Call this the challenge ciphertext.]

Adv is given unrestricted encryption oracle access AND access to the decryption oracle WITH the restriction that Adv cannot query the oracle on the challenge ciphertext. A has to guess which message got encrypted. If A wins with probability <= 1/2 + negl then IND-CCA else not. Encryption oracle uses its own generated key Gen(1^n).

In public key encryption the encryption oracle is simply just the public key itself, which is public.

Deterministic encryption can never be IND-CPA because an adversary can simply encrypt m0 and check if the challenge ciphertext is the encryption of m0. This is why ECB mode and textbook RSA are not CPA-secure – because they are deterministic.

No randomized symmetric or public key encryption schemes can be information-theoretically secure (perfect secrecy) because any unbounded adversary can simply query the encryption oracle for Enc(m0, r) for all possible values of r and compare them to the challenge ciphertext. Of course this is not possible with polynomial-time adversaries.

Random oracle model is where all hash functions are replaced by a random oracle. A random oracle is a black box that responds with a random output for every unique input, and responds with the same output for the same input.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s