7
$\begingroup$

Recently, Fujisaki and Okamoto provided a revised version of the Fujisaki-Okamoto transformation [1], a generic transformation for achieving IND-CCA2 security in the Random Oracle model. This new version is slightly different than the original [2] and the security proof does not define a knowledge extractor (the original version actually proved that the transformation satisfies the Plaintext Awareness (PA) notion and used the fact that PA $\Rightarrow$ IND-CCA2 in the random oracle model). Instead, they directly provide an algorithm for the decryption oracle. When describing the decryption oracle construction, they stress that it does not require the secret key (in a similar way than the original version), and it only uses the information from previous random oracle queries.

Is this characteristic (i.e., not using the secret key) relevant in general for proofs for the IND-CCA2 notion, or is it simply something inherited in this particular case from the original transformation, aimed at the Plaintext Awareness notion? In other words, is there any inherent drawback in using the secret key in the decryption oracle when facing a security proof for IND-CCA2? I know that, usually, proofs are constructed as reductions to hard problems, which may force to define the decryption oracle without knowledge of the secret key. However, this does not seem to be the case.

I think I may be overthinking the problem, and that the answer may be a simple "No".

Update: I added some possible explanations in the comments. I'm starting to lean towards the answer "It is important in this particular proof, but not in general".

References:

[1] Fujisaki, E., & Okamoto, T. (2013). Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1), 80-101.

[2] Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. In Crypto (Vol. 99, No. 32, pp. 537-554). [link]

Improve this question
$\endgroup$
2
  • $\begingroup$ A possible explanation is that the proof does not use the secret keys, only the random oracle tables, in order to maintain its genericity. As described in the question, some schemes are proven secure as reductions to a hard problem, in such a way that it is not possible to resort to the secret key (e.g., the public key is an element from a Diffie-Hellman tuple, so the secret key is unknown for the simulator). Does it make any sense? $\endgroup$
    – cygnusv
    Jun 16 '15 at 15:16
  • $\begingroup$ Somewhat related to my previous comment, I found another possible reason for not using the secret key. In the proof of Lemma 7.2 of [1], they construct an adversary $A^{asy}$ against the OWE notion of the asymmetric scheme that uses an adversary $A^{hyb}$, defined against the CCA-RO notion of the hybrid scheme. In this proof, $A^{asy}$ receives the public key from the challenger of the OWE game, but does not receive the corresponding secret key. Therefore, $A^{asy}$ cannot provide the key for $A^{hyb}$, and assuming knowledge of this key would invalidate this proof. $\endgroup$
    – cygnusv
    Jun 24 '15 at 9:18
2
+50
$\begingroup$

As you say, CCA proofs are actually reductions to underlying problems. In all CCA proofs that I can think of at the moment, the underlying problem is a weaker security notion for an "embedded" encryption scheme - e.g. Cramer-Shoup and friends use IND-CPA of ElGamal and Fujisaki-Okamoto uses OWE of the contained scheme.

The general proof strategy is to take a public key from your challenger and pass this to the adversary. This lets you use the challenger to process the two challenge messages to get the challenge ciphertext - since the only bit of information that your adversary gives you is which of the two challenge messages he thinks was encrypted, I'd guess that all CCA proofs will somehow have to "embed" the hard problem they're reducing to in the challenge ciphertext. After all, the reduction could compute everything else by itself.

This strategy of getting the public key from the challenger means you don't know the matching secret key, so the interesting bit of the proof is then how you handle decryption queries without it. This is certainly general to all CCA proofs that I can think of at the moment.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. I don't understand something. If we assume that the decryption oracle should not use the secret key, how is it different from a knowledge extractor? $\endgroup$
    – cygnusv
    Jun 30 '15 at 8:17
  • 1
    $\begingroup$ The two concepts are closely related. Consider for example Shoup and Gennaro's '98 paper with the TDH schemes. The general principle is that you take an IND-CPA scheme (ElGamal will do), add some form of PoK and then hope it's CCA. The intuition is that we make the decryption oracle useless for the adversary by making sure that the only valid ciphertexts she can construct are ones where she already knows the message - formally, the decryption oracle is based on the knowledge extractor of the PoK. Unfortunately the details are a bit more complex. $\endgroup$
    – user2552
    Jun 30 '15 at 8:31

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.