0
$\begingroup$

Let PKE $\Pi' = (Gen', Enc', Dec')$ and it is secure in the sense of $S'$.

Let PKE $\Pi'' = (Gen'', Enc'', Dec'')$ and it is secure in the sense of $S''$.

$S'$ and $S''$ may be separation which means that $S' \not\Rightarrow S''$ and $S'' \not\Rightarrow S'$. For example, $S' = \text{IND-CCA}, S'' = \text{NM-CPA}$ or $S' = \text{OW-CCA}, S'' = \text{IND-CPA}$.

Let $\Pi = (Gen, Enc, Dec)$ be the double encryption such that

$Gen(1^\lambda) = (pk, sk)$

  1. $(pk', sk') \gets Gen'(1^\lambda)$ and $(pk'', sk'') \gets Gen''(1^\lambda)$.

  2. $pk = pk' \Vert pk ''$ and $sk = sk' \Vert sk''$.

$Enc_{pk}(m) = c$

  1. $(pk' , pk'') \gets pk$

  2. $c \gets Enc'_{pk'}( Enc''_{pk''}(m)) $.

$Dec_{sk}(c) = m$

  1. $(sk' , sk'') \gets sk$

  2. $c \gets Dec''_{sk''}( Dec'_{sk'}(m))$.

Is $\Pi$ secure both in the sense of $S'$ and $S''$?

In my opinion, it is true.

We define the CPA game of $\Pi$ against an adversary $A = (A_{1}, A_{2})$ as follows:

  1. $(pk, sk) \gets Gen(1^\lambda)$
  2. $(m_{0}, m_{1}, s) \gets A_{1}(pk)$
  3. $b \leftarrow \{\, 0,1 \,\}$ and $c \gets Enc_{pk}(m_{b})$.
  4. $d \gets A_{2}(c, s)$.

We say $A$ wins if $b = d$, and $\Pi$ is IND-CPA secure if $A$ has at most negligible advantage.

For example, if $S'' = \text{IND-CPA}$, assume there exists an adversary $A$ with non-negligible advantage against $\Pi$. Then we construct an adversary $A''$ against $\Pi''$ as follows:

$A''_{1}(pk'') = (m_{0}, m_{1}, s)$:

  1. $(pk', sk') \gets Gen'(1^\lambda)$.

  2. $pk = pk' \Vert pk''$.

  3. $(m_{0}, m_{1}, s) \gets A(pk)$.

$A''_{2}(c, s) = d$:

  1. $c' \leftarrow Enc'_{pk'}(c)$

  2. $d \gets A(c', s)$.

We see that $A''$ wins the CPA game against $\Pi''$ if and only if $A$ would have won the corresponding game against $\Pi$. Thus $\Pi''$ is IND-CPA secure implies that $\Pi$ is IND-CPA secure.

If $S' = \text{IND-CPA}$, assume there exists an adversary $A$ with non-negligible advantage against $\Pi$. Then we construct an adversary $A'$ against $\Pi'$ as follows:

$A'_{1}(pk') = (m_{0}, m_{1}, s)$:

  1. $(pk'', sk'') \gets Gen''(1^\lambda)$.

  2. $pk = pk' \Vert pk''$.

  3. $(m'_{0}, m'_{1}, s) \gets A(pk)$.

  4. $m_{0} \gets Enc''_{pk''}(m'_{0})$ and $m_{1} \gets Enc''_{pk''}(m'_{1})$

$A'_{2}(c, s) = d$:

  1. $d \gets A(c, s)$.

We see that $A'$ wins the CPA game against $\Pi'$ if and only if $A$ would have won the corresponding game against $\Pi$. Thus $\Pi'$ is IND-CPA secure implies that $\Pi$ is IND-CPA secure.

Am I right? So I conclude that $\Pi$ is a little stronger than $\Pi'$ and $\Pi''$. If it is true, why is there no double public-key encryption scheme?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.