# 「Cryptography-MIT6875」: Lecture 17

**Topics Covered: **

- Definition of IND-CCA Security
- Application of NIZK: Construction of CCA-secure encryption scheme

In last post, we saw a NIZK for 3SAT, and then we can __get a NIZK for all of NP in the CRS model.__

Moreover, we mentioned that __if we weaken the notion of proofs into arguments__, then we can __construct perfect zk for all of NP.__

Today, we will discuss the **application of NIZK**, non-malleable and chosen ciphertext secure encryption scheme.

# Active Attacks against CPA-secure Encryption

Recall the public encryption schemes.

- Bob generate a pair of keys, a public key $pk$, and a private (or secret) key $sk$.
- Bob “publishes” $pk$ and keeps $sk$ to himself.
- Alice encrypts $m$ to Bob using $pk$.
- Bob decrypts using $sk$.

In Lecture 8, we gave the definition of **IND-CPA security** for public encryption scheme and mentioned the __IND-CPA-secure is achievable with randomness.__

But there are two active attacks against the public encryption scheme above.

## Malleability

The first active attack is **malleability**.

Consider the **scenario for bidding.**

Alice wants to bid ¥100 and she encrypts her bid with public key.

There is a malicious attacker that wants to win the bidding and he __can modify the encryption of ¥100 into an encryption of ¥101 as his bidding.__

The attack can always modify the encryption, which is always one more dollar than Alice’s although the attack __dose not know what Alice’s bid is.__

So the adversary could **modify (“maul”) an encryption** of $m$ __into an encryption of a related message__ $m’$.

## Chosen-Ciphertext Attack

Another active attack is **chosen-ciphertext attack.**

If the first bit of the message is 0, we define it’s the encryption of a valid message.

If the first bit of the message is 1, we define it’s the encryption of an invalid message.

Then the adversary may **have access to a decryption “oracle”** and can __use it to break security of a “target” ciphertext $c^*$ or even extract the secret key!__

In fact, **Bleichenbacher** showed __how to extract the entire secret key__ **given only a “ciphertext verification” oracle.**

# IND-CCA Security

After defining the stronger active attackers, we can define the Indistinguishable Chosen-Ciphertext Attack Security, or **IND-CCA.**

Recall the game in IND-CPA secure definition.

** Game in IND-CPA (one-message): **

- The
**Challenger**generates a pair of key $(pk, sk)$ and publishes the $pk$. **Eve**sends two**single messages**, $m_0$ and $m_1$s.t. $|m_0|=|m_1|$.- The challenger samples $b$ from ${0,1}$ and encrypts the message $m_b$ using $pk$.

And send the ciphertext to Eve. - Eve
__guesses which message is encrypted__and output $b’$. - Eve wins if $b’=b$.

Let’s move to the game in IND-CCA.

As has been said, the adversary has the __power of accessing to a decryption “oracle”.__

The adversary can **query for the decryption in polynomial many times.**

It can __happen both before and after the challenge.__

**Note** that the adversary can query for the decryption, **before the challenge**, of any ciphertext.

But **after the challenge**, he __cannot query for the decryption of the challenge.__

Otherwise, the challenge is meaningless.

So there are additional two phases in the game of IND-CCA.

** Game in IND-CCA: **

- The
**Challenger**generates a pair of key $(pk, sk)$ and publishes the $pk$. - Eve
**asks for the decryption of any ciphertext**in poly. many times. **Eve**sends two**single messages**, $m_0$ and $m_1$s.t. $|m_0|=|m_1|$.- The challenger samples $b$ from ${0,1}$ and encrypts the message $m_b$ using $pk$.

And send the ciphertext to Eve. - Eve
**asks for the decryption**of any ciphertext (**except the challenge**$c^\star$) in poly. many times. - Eve guesses
__which message is encrypted__and output $b’$. - Eve wins if $b’=b$.

# Constructing CCA-Secure Encryption

In the light of the CCA-secure definition, we can construct the CCA-secure encryption scheme.

**Our goal** is that the __adversary is hard to modify an encryption__ of $m$ into an encryption of a related message, say $m+1$.

Intuitionally, the **proof of knowledge** and the **signatures** should help __against the malleability for CAP-secure encryption.__

With **NIZK proofs of knowledge**, the idea is that the __encryption party attaches an NIZK proof of knowledge of the underlying message to the ciphertext.__

Therefore, the encryption consists of CPA-encryption and the NIZK proof of knowledge of the message.

$C:(c=\text{CPAEnc}(m;r),\text{ proof }\pi \text{ that “I know }m\text{ and }r\text{ “})$.

This idea will turns out to be useful, but **NIZK proofs themselves can be malleable.**

So the **active attack** turns to create the CPA-encryption of $(m+1,r)$ and the NIZK proof of $(m+1,r)$.

## Start with Digital Signatures

Let’s start with digital signatures.

We construct the CCA-secure encryption, which contains the signature of the CPA-secure encryption.

$C:(c=\text{CPAEnc}(pk,m;r),\text{Sign}_{sgk}(c),vk)$

where the encryption produces a signing/verification key pair by running $(sgk,vk)\gets \text{Sign.Gen}(1^n)$.

It is actually **not CCA-secure.** (or it’s malleable)

If the adversary changes $vk$, all bets are off.

The picture below explains the reason vividly.

Consequently, the **lesson** is that __we need to “tie” the ciphertext $c$ to $vk$ in a “meaningful” way.__

## IND-CPA → “Different-Key Non-malleability”

One observation is we can **reduce IND-CPA to Different-Key Non-malleability(NM).**

The **Different-Key NM** predicates that __given (independent) $pk,pk’$ and the encryption $\text{CPAEnc}(pk,m;r)$,__ the adversary **cannot produce** $\text{CPAEnc}(pk’,m+1;r)$.

It’s a **reduction** that suppose the adversary could produce the different-key encryption, then she can break the IND-CPA security of $\text{CPAEnc}(pk,m;r)$.

**Proof:**

Suppose for contradiction that the **adversary** has the __power of producing the different-key encryption__, $\text{CPAEnc}(pk’,m+1;r)$.

The interaction with the Diff-Key NM adversary is as follows.

* Interaction with Diff-Key NM Adv.*

- Pick a random pair $(pk’, sk’)$ and
__give the two public keys $pk,pk’$ .__ - Give the CPA-secure encryption of $m$ using $pk$.
- The Diff-Key NM adv.
__promises to produce the CPA-secure encryption__of $m+1$ using the different key $pk’$. (w.r.t. contradiction)

Then we can **construct a CPA adversary** by using the Diff-Key NM adversary, as shown below.

* Break CPA-secure Encryption *

- The
**challenge**is to__decrypt the message given CPA-secure encryption.__

(as shown on the left of the picture)

- Given $pk$, then we
__pick a random pair__$(pk’,sk’)$ and send $pk,pk’$ to the adversary. - Give the CPA-secure encryption from CPA challenge.
- The adversary promises to
__produce an encryption using the different key__$pk’$. - Then we can decrypt it with $sk’$ and subtract 1 to get $m$.

Hence, if the adversary can **break the Different-Key NM game**, then she can **break CPA security.**

## CCA-Secure Encryption Scheme

We can get **non-malleable and CCA-secure encryption** putting *CPA-secure encryption*, *digital signature* and *NIZK proofs* together.

As has been said, we __need to tie the ciphertext $c$ to the verification key $vk$.__

### NM Encryption Scheme

** CCA Encryption (only non-malleable): **

We

__define $2n$ public keys of the CPA scheme__as the**CCA public key.****CCA Public Key:**$\left[\begin{array}{llll}p k_{1,0} & p k_{2,0} & \dots & p k_{n, 0} \ p k_{1,1} & p k_{2,1} & \dots & p k_{n, 1}\end{array}\right]$ where $n=|vk|$.

First, pick a signing/verification key pair $(sgk, vk)$.

Then

__use the CCA public key, based on the bits of__$vk$, to produce the ciphertext.$CT=[ct_{1,vk_1},ct_{2,vk_2},\dots,ct_{n,vk_n}]$ where $ct_{i,j}\gets \text{CPAEnc}(pk_{i,j},m)$.

This ties the ciphertext $CT$ to the verification key $vk$ in meaningful way that the

__encryption is under the public key indexed by the bits of $vk$.__For each ciphertext in slot $i$ of $CT$:

If the $i$-th bit of $vk$ is 0, then use $pk_{i,0}$ to produce the ciphertext.

If the $i$-th bit of $vk$ is 1, then use $pk_{i,1}$ to produce the ciphertext.

Output $(CT,vk,\sigma=\text{Sign}_{sgk}(CT))$

The encryption scheme above is **non-malleable.**

* Non-malleability rationale: *

- If the adversary
__keeps the $vk$ the same,__she needs to produce $(CT’,vk,\sigma_{sgk}(CT’))$ for the related message $m’$, which**has to break the signature scheme.**- $CT’$ is encrypted
__under the same public key__as $CT$.

- $CT’$ is encrypted
- If the adversary
__changes the $vk$,__she has to break the Different-Key Non-malleability game, and therefore**CPA security.**- The adversary needs the produce $(CT’,vk’,\sigma_{sgk’}(CT’))$ for the related message $m’$.
- $CT’$ is encrypted
__under the different public key__, which is indexed by $vk’$. - Hence, for
**each different bit**of $vk’$:- The original $ct_{i,j}\gets \text{CPAEnc}(pk_{i,j},m)$.
- The adversary needs to produce $ct_{i,j}’\gets \text{CPAEnc}(pk_{i,1\oplus j},m’)$.
- Turns out the Different-Key NM, which can
**be reduced to CPA security.**

### CCA-Secure Encryption Scheme

We are not done!!

Adversary could **create ill-formed ciphertexts**, e.g. __different $ct$s encrypt different messages__, and uses it for Bleichenbacher-like attack.

Hence, it has to **prove that the ciphertext is well-formed.**

** CCA Encryption (non-malleable and CCA-secure): **

We

__define $2n$ public keys of the CPA scheme__as the**CCA public key.****CCA Keys:**PK = $\left[\begin{array}{llll}p k_{1,0} & p k_{2,0} & \dots & p k_{n, 0} \ p k_{1,1} & p k_{2,1} & \dots & p k_{n, 1}\end{array}\right]$,

**CRS**where $n=|vk|$.SK = $\left[\begin{array}{c}sk_{1,0} \ sk_{1,1}\end{array}\right]$

- To achieve NIZK proof, it has to have (public)
**CRS**. - The secret key contains
**only one pair**since it needs to be proven well-formed.

- To achieve NIZK proof, it has to have (public)

First, pick a signing/verification key pair $(sgk, vk)$.

Then

__use the CCA public key, based on the bits of__$vk$, to produce the ciphertext.$CT=[ct_{1,vk_1},ct_{2,vk_2},\dots,ct_{n,vk_n}]$ where $ct_{i,j}\gets \text{CPAEnc}(pk_{i,j},m)$.

Generate

**NIZK proof**$\pi$ = “CT is well-formed”.Output $(CT,{\color{blue}\pi},vk,\sigma=\text{Sign}_{sgk}({\color{blue}{CT,\pi}}))$

** CCA Decryption: **

- Check the signature
- Check the NIZK proof
- Decrypt with $sk_{1,vk_1}$

Now, this encryption scheme is CCA-secure and non-malleable.

** Proof of CCA-security: **

Proof Sketch

- Suppose for contradiction that there is an
**CCA adversary.** **Play the CCA game with the adversary.**

Note that we will__define several hybrid distributions to argument__and__play the CCA game in one Hybrid.__- Then we can use her to
**break either the NIZK soundness/ZK, the signature scheme or the CPA-secure scheme.**

- Suppose for contradiction that there is an
CCA game is as follows.

**Hybrid 0**: Play the CCA game as prescribed.**Hybrid 1**: Observe that $vk_i\ne vk^*$. (**Otherwise break signature.**)- Observe that this means
**each query ciphertext-tuple**__involves a different public-key from the challenge ciphertext.__ - Then we
__can use the “different private-key” to decrypt.__ **(If the adversary sees a difference, she broke NIZK soundness.)**

It means that the adversary__produces a ill-formed ciphertext__and she cheats successfuly.

- Observe that this means
Hybrid 2: Now change the CRS/$\pi$ into

**simulated**CRS/$\pi$.**(It’s OK by ZK)**If we want to use the adversary to break CPA security, it

__has to win the CPA game__as follows.We can plop $pk$, given in CPA game, into

__one slot__of $PK$.We plop ciphertext, given in CPA game, into $c^*$

__with the corresponding slot.__For

**other slots**in $c^*$, we can__generate the ciphertext for random message.__But we cannot generate NIZK proof $\pi$ since we don’t have the witness.

It says that the $c^*$ is ill-formed.But we

**cannot since we don’t have the witness**, that is $m^*$, the challenge of CPA game.Hence, in Hybrid 2, we change the CRS/$\pi$ into

**simulated**CRS/$\pi$.It’s zero-knowledge.

But more importantly, we

__can generate simulated proof.__Consequently,

__if the adversary wins in this hybrid__, she**breaks IND-CPA**as shown below.

「Cryptography-MIT6875」: Lecture 17