3
$\begingroup$

I'm working on my bachelor thesis and I have some questions. I want to combine a CPA-secure private key encryption scheme and some unforgeable public key signature scheme (in my case some sanitizable signature scheme but I think it doesn't matter). The resulting scheme should be CCA-secure. How can I do that?

If I use a MAC instead of the signature scheme, I get a CCA-secure scheme, but I have to use signatures, since I'm in a juristic context. I tried to combine both schemes them by signing the message and then encrypting the signature together with the message. But I struggle with proving that such a scheme is CCA-secure. CCA Security is only defined for private-key encryption schemes or public key encryption schemes but I have to prove it for the combination of priv key encr. and pub key signatures.

So my questions are:

  1. How can I combine an unforgeable Public key signature scheme with a CPA secure private key encryption scheme, such that the resulting scheme is CCA secure?

  2. How can I prove CCA Security for such a scheme, since it is not defined?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm not quite clear on what goal you want to achieve with this. Can you clarify what your combination should achieve and what your exact question is? $\endgroup$
    – malexmave
    Mar 22, 2016 at 12:58
  • $\begingroup$ The typical way these proofs go is "if this scheme is not CCA-secure, then we can show either that the encryption is not CPA-secure, or the signature method can be forged" $\endgroup$
    – poncho
    Mar 22, 2016 at 13:00
  • 1
    $\begingroup$ I edited my question. Hope it's clearer now. Thanks for the help guys! $\endgroup$
    – Lukas Schüßler
    Mar 22, 2016 at 13:39

1 Answer 1

Reset to default
2
$\begingroup$

I tried to combine both schemes them by signing the message and then encrypting the signature together with the message. But i struggle with proving that such a scheme is CCA-secure.

I believe that the reason you're running into issues proving that is that CCA-secureness of this system doesn't actually follow from the CPA-security of the cipher and the unforgability of the signature. That is, you could design a CPA-secure cipher that, with unforgable signatures, that the system is not CCA-secure.

Consider a CPA-secure encryption where the attacker can modify the ciphertext in a way such that the decryption of the modified ciphertext might result in the original plaintext, or might not (and whether it does or not would give the attacker information on the secret key). CPA-secure allows such a vulnerability, as it doesn't consider modified ciphertexts.

It's fairly obvious how a CCA-attacker would break such a system; they would modify the ciphertext, and give it to the decryption oracle. The decryptor would first recover the signed plaintext; if it was the original signed plaintext, then the signature algorithm would accept it (because it's not a forgery if it's bitwise identical to a previously signed text), and so the decryption oracle would emit the plaintext.

You could place additional constraints on the CPA-encryption to ensure this doesn't happen. However, a better approach (both from a provability standpoint, and from an implementation standpoint) is to reverse the order of operations; first CPA-encrypt the plaintext, and then sign it. I believe you'll find that easy to prove CCA-secure.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thans for the answer! So i tried to do it in a sign-then-encrypt way and you recommended the encrypt-then-sign way. But now i have one problem, that i didn't recognize before: I'm using a sanitizable signature scheme and the sanit algorithm needs a message and the signature of the message as input. So i need to sign the message first. I read something about sign-then-encrypt-then-sign. I could sign the message first, encrypt the message and the signature and sign the whole thing again. Does this make any sense? $\endgroup$
    – Lukas Schüßler
    Mar 22, 2016 at 15:05
  • $\begingroup$ @LukasSchüßler: it's not at all clear how you'd use your santizer to generate a fresh ciphertext without the encrypt key. However, assuming that's not an issue, and that you're original approach mostly worked somehow (except for the CCA issue), it might be easiest to go with your original sign-then-encrypt, but just encrypt with a CCA-secure cipher (such as an authenticated encryption mode). $\endgroup$
    – poncho
    Mar 22, 2016 at 15:24
  • $\begingroup$ "first CPA-encrypt the plaintext, and then sign it." - ... and ensure you don't end up like Apple with iMessage (CTR then ECDSA), where the attacker just ripps the signature off and replace it with their own. $\endgroup$
    – SEJPM
    Mar 22, 2016 at 15:32
  • $\begingroup$ More generally, a non-malleable cipher would be sufficient. ​ Additionally, encrypt-then-sign doesn't work nearly as well in the symmetric-encryption case, since for non-repudiation the recipients must reveal the symmetric key and somehow show that the revealed key was the actual symmetric key. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 22, 2016 at 15:34
  • $\begingroup$ @LukasSchüßler : ​ I just realized that for sign-then-encrypt, you'd need to make sure the lengths of the encodings of the [message,signature] pairs don't reveal more about the messages than the lengths of the messages. ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 23, 2016 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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