An IND-CCA secure private-key encryption scheme

From CRYPTUTOR

By appending a MAC of the ciphertext, we can transform any IND-CPA-secure private-key encryption scheme into an IND-CCA-secure scheme.

[edit]

Construction

Suppose $(\mathsf{KeyGen_{Enc}},\mathsf{Enc},\mathsf{Dec})$ is an IND-CPA-secure private-key encryption scheme, and $(\mathsf{KeyGen_{MAC}},\mathsf{MAC},\mathsf{Ver})$ is a MAC scheme. Then we define the following private-key encryption scheme:

$\mathsf{KeyGen}^*$ : output $(k 1, k 2)$ , where $k_1 \gets \mathsf{KeyGen_{Enc}}, k_2 \gets \mathsf{KeyGen_{MAC}}$ ,
$\mathsf{Enc}_{k_1,k_2}^*(m)$ : output $(z, \mathsf{MAC}_{k_2}(z))$ , where $z \gets \mathsf{Enc}_{k_1}(m)$ .
:
- If $\mathsf{Ver}_{k_2}(z,\tau) = 1$ , then output $\mathsf{Dec}_{k_1}(z)$
- Otherwise, raise an error (i.e, output $\bot$ ).

By the correctness properties of the MAC scheme and CPA-secure encryption scheme, we must have $\mathsf{Dec}_k^*(\mathsf{Enc}_k^*(m)) = m$ for all messages $m$ and keys $k$ .

[edit]

Proof of security

We now show that this new scheme achieves IND-CCA security.

Let $A *$ be an adversary that attacks the $\mathsf{Enc}^*$ scheme in the IND-CCA experiment, with advantage $ε$ . We will show that this advantage must be negligible. We construct a simulator $A$ that attacks Enc in the IND-CPA experiment as follows:

Simulator $A$ , for the IND-CPA experiment attacking Enc

Receive a key $k 1$ for the Enc scheme in the IND-CPA experiment. (Privately) generate a key for the mac: $k_2 \gets \mathsf{KeyGen_{MAC}}$ .
Run $A *$ , simulating the IND-CCA experiment as follows:
Give $(k 1, k 2)-$ as the key for the IND-CCA experiment.
When $A *$ queries its encryption oracle, simulate the response by querying our own encryption oracle, and then appending a MAC of the ciphertext (using $k 2$ as the MAC key).
When $A *$ submits a challenge $(m 0, m 1)-$ , pass it along as our own challenge in the IND-CPA experiment. As above, append a MAC of the ciphertext response and give it to $A *$ .
When $A *$ queries its decryption oracle with $(z,τ)$ , simulate it as follows (note that the simulator does not have access to any decryption oracle for Enc, as it is running an IND-CPA experiment attacking Enc):
If $(z,τ)$ was the ciphertext response from a previous encryption oracle query, return the plaintext that generated that ciphertext.
Otherwise, return $\bot$ .

Clearly, our simulation provides $A *$ with a correctly distributed key for $\mathsf{Enc}^*$ and correctly distributed $\mathsf{Enc}^*$ -encryptions (including the challenge ciphertexts) under that key. In that respect, we correctly simulate the IND-CCA experiment with $A *$ attacking $\mathsf{Enc}^*$ . We must now argue that we also simulate the decryption oracle responses correctly:

In the first case in the description of the decryption oracle simulation, we clearly provide the correct response.
If $A *$ asks for a decryption of one of its challenge ciphertexts, we correctly reject.
For all other queries to the decryption oracle, the adversary is submitting $(z,τ)$ for some $z$ for which we have never generated a MAC. By the unforgeability property of the MAC, $τ$ is a valid MAC for $z$ only with negligible probability. Conditioned on this event not happening, our decryption oracle has the same behavior as the real decryption oracle in the IND-CCA experiment.

We have shown that our simulator $A$ gives a negligibly-close simulation of $A *$ in the IND-CCA experiment. The advantage of $A *$ in that experiment was $ε$ , so $A$ 's advantage in the IND-CPA experiment (attacking Enc) is negligibly close to $ε$ . Since we assumed that Enc was IND-CPA secure, $ε$ must be negligible, as desired.

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/An_IND-CCA_secure_private-key_encryption_scheme"

Category: Constructions

An IND-CCA secure private-key encryption scheme

From CRYPTUTOR

Construction

Proof of security

Views

Personal tools

Navigation

Search

Toolbox