CPA + one-time strong signature --> CCA?

cn flag

Does combining a CPA PKE (public key encryption) scheme with a one-time strong signature construct a CCA PKE scheme? More specifically, let $(Enc,Dec)$ be a CPA PKE scheme, and $(V,S)$ be a one-time signature, i.e., one cannot forge a valid signature even for once-queried messages without $S$.

Then, constructing a new PKE scheme:

$Enc'$ algorithm on $(pk,m,s)$: $$c1 = Enc(pk,m),$$ $$c2=Sign(s,c1),$$ $$return (c1,c2).$$ and $Dec'$ algorithm on $(sk,c,v)$: $$if \ Very(v,c2)=0,\ return \ False;$$ $$else \ return \ Dec(sk,c1).\ \ \ \ $$

Is this a CCA scheme?

Mark avatar
ng flag
While this doesn't cover your particular proposed construction, people typically use the Fujisaki-Okomoto transformation for what you want, which is very similar. Is the particular transformation you mention important, or do you just want generic pointers towards achieving CCA security?
Huanhuan Chen avatar
cn flag
Thanks, Mark. I came out this idea when I was reading Naor-Yung transformation, where NIZP + Signature + CPA are used to construct schemes with CCA security. I am wondering if NIZP is necessary in this scheme, so I asked this question.
us flag
How does the decryption algorithm obtain the signature verification key?
Mark avatar
ng flag
@Mikero this is the right criticism of this idea, but "backwards". The signature verification key can be made publicly available, so you can freely include it in the secret key of the overall scheme. By "backwards" I mean that one cannot publicly compute encryptions, as the signing key must be kept secret for security, so if it is stuck in the public key of $Enc'$ one cannot appeal to the security of the signature scheme in any meaningful way.
Huanhuan Chen avatar
cn flag
Thanks, Mark. I've got it now.
us flag

The construction can't be made CCA-secure

The algorithm that you wrote doesn't say how the decryption algorithm obtains the signature verification key.

  • If the verification key is part of the public key, then nobody can encrypt because nobody has access to the signing key (as Mark observed in the comments above). Also, this doesn't seem to fit with your proposal to use a one-time signature.

  • If the verification key is included in the ciphertext (in the clear), then this doesn't work either. Now ciphertexts have the form $$(c=\textsf{Enc}(pk,m), vk, \sigma=\textsf{Sign}(sk,c\|vk))$$ where $(sk,vk)$ is a one-time signature key pair. I can take a ciphertext of this form, modify $c$ in any way, and replace $vk,\sigma$ with my own $vk',\sigma'$ that I generate. This allows me to directly perform any chosen-ciphertext attack against $\textsf{Enc}$ on this new scheme.

  • If the verification key is inside the encryption, this is better, but still not secure. Now ciphertexts have the form $$(c=\textsf{Enc}(pk,m\|vk), \sigma=\textsf{Sign}(sk,c))$$ The goal is that the new scheme is CCA-secure for any choice of CPA-secure $\textsf{Enc}$. However, it is possible to construct a pathological CPA-secure scheme, in which it is possible to change $\textsf{Enc}(pk,m\|vk)$ into $\textsf{Enc}(pk,m\|vk')$ for any $vk'$ of the attacker's choice, and without knowledge of $m$ or $vk$. So a CCA attack on the new scheme involves changing $c$ into $c'$ in this way, with $vk'$ chosen by the attacker. Then the attacker can generate the correct signature on the new $c'$ and ask for it to be decrypted to reveal $m$.

There is no "simple" construction that compiles CPA to CCA security

There is a famous open problem in cryptography:

Is there a black-box construction of a CCA-secure public-key encryption scheme from an arbitrary CPA-secure public-key encryption scheme, in the plain model?

It is possible to construct a CCA-secure scheme from a CPA-secure scheme if we change the parameters of this open problem:

  • If we leave the plain model and allow random oracles, then the Fujisaki-Okamoto transformation achieves CCA security.

  • If we allow non-black-box constructions, then we can achieve CCA security using the Naor-Yung transformation. Non-black-box means that the CCA-secure scheme somehow uses the source code of the CPA-secure scheme. In the case of Naor-Yung, you need the source code of the CPA-secure scheme in order to prove a zero-knowledge claim about the ciphertexts.

There is some partial progress proving this open problem -- in particular, there can be no such construction if the CCA decryption algorithm does not use the CPA encryption algorithm.

The techniques you use in this question are all black-box and therefore are unlikely to be useful in constructing a CCA-secure scheme.

Similar techniques work if the CPA scheme is identity-based

Your construction reminds me of the Canetti-Halevi-Katz transformation from a CPA-secure identity-based scheme to a CCA-secure (non-identity-based) scheme.

Let $\textsf{Enc}(pk,id,m)$ denote the identity-based encryption (IBE) of $m$ to identity $id$, using public global parameters $pk$. Then the CHK construction is: $$ \textsf{Enc}^*(pk,m) = (vk, c = \textsf{Enc}(pk, vk, m), \sigma = \textsf{Sign}(sk,c)) $$ In other words, to encrypt:

  1. generate a one-time signature keypair $(sk,vk)$.
  2. encrypt the plaintext with IBE, using $vk$ as the identity
  3. sign the IBE ciphertext with $sk$
  4. give $vk$, the IBE ciphertext, and the signature

The result is CCA-secure, and the rough intuition is that CPA-secure IBE might be malleable with respect to the plaintexts, but it must be non-malleable with respect to the identities.

Huanhuan Chen avatar
cn flag
Thanks, Mikero. It is very clear. I understand.
Patriot avatar
cn flag
@Huanhuan Chen Please consider voting up the answer that you accepted.

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.