2
$\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 say 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 say 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$
2
$\begingroup$

Am I right?

Yes, with double encryption, if both are functionally correct and at least one is CPA-secure, then the composition is CPA-secure.

If it is true, why is there no double public-key encryption scheme?

Because you took a scheme that can be reasonably classified to be "unbreakable" and then combined it with an other "unbreakable" one, you have constructed an "unbreakable" one that takes more time to compute than a single "unbreakable" one. There's no practical advantage to such combinators if we're confident in the security of the scheme we're using. If we're not confident either we pick a better one - or if we have also no faith in the better one we do indeed use such combinators. If you want a recent example of this, look no further than the hybrid ECDH / PQ-Crypto key exchanges that are being tested where we don't have faith in the PQ-Crypto yet so use ECDH to secure it against classical adversaries.

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

To prove this I suggest a simpler approach of checking whether $\pi\circ\operatorname{Enc}\circ\pi'$ is $S'$-secure assuming $\operatorname{Enc}$ is $S'$-secure (coming up with the correct decryption is left as an exercise to the reader) and $\pi,\pi'$ are any permuations applied to the input and the output.

| improve this answer | |
$\endgroup$
  • $\begingroup$ As for the second answer, maybe my question is not clear enough. Of course, double encryption is not efficient. I mean, if we consider the security level of the double enctryption $\Pi$, it is secure both in the sense of $S'$ and $S''$. However, it is more secure than $\Pi'$ and $\Pi''$ as they are only secure in the sense of $S'$ or $S''$. It means that we can improve the security by using double encryption. $\endgroup$ – TeamBright Apr 10 at 5:52
  • $\begingroup$ @TeamBright usually there will be an implication in security, e.g. $S'\implies S''$ or $S''\implies S'$ in that case you gain just about nothing in security. But if you have a pair of notions that don't imply each other in either direction and you prove the composition secure in both notions, then yes, the double encryption will be more secure (one example for this would probably be combining an INT-PTXT-secure scheme with a IND-CPA secure scheme). $\endgroup$ – SEJPM Apr 10 at 11:58
  • $\begingroup$ BTW, as you mention, if a $S'$-secure encryption algorithm $\text{Enc}$ satisfies that $\pi \circ \text{Enc} \circ \pi'$ is also $S'$-secure, is there a name about this kind of encryption algorithm $\text{Enc}$? I mean, does the properity have a name? $\endgroup$ – TeamBright Apr 10 at 13:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.