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

Question

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?

Answer 1

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.