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

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?

• 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?
– Mark
Sep 24, 2021 at 21:09
• 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. Sep 24, 2021 at 21:27
• How does the decryption algorithm obtain the signature verification key? Sep 24, 2021 at 21:38
• @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.
– Mark
Sep 24, 2021 at 22:04
• Thanks, Mark. I've got it now. Sep 25, 2021 at 9:02

## 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.

• Thanks, Mikero. It is very clear. I understand. Sep 25, 2021 at 8:57
• @Huanhuan Chen Please consider voting up the answer that you accepted. Sep 25, 2021 at 10:41
• Sorry for late voting. I have just got the privilege. Oct 8, 2021 at 20:39