4
$\begingroup$

I am looking for a faster alternative to RSA with OAEP as a IND-CCA2 public key scheme. Elliptic Curve Integrated Encryption Scheme might be a candidate, but I am not sure if it provides IND-CCA2 security.

So the question is if ECIES offers IND-CCA2 security by default? If not, what should be changed so that it does offer it?

$\endgroup$
  • 1
    $\begingroup$ Yes. ECIES is CCA2-secure. $\endgroup$ – Yehuda Lindell Jan 4 at 9:50
  • $\begingroup$ Thanks for the quick answer. Are you aware of a formal proof that I can refer to? $\endgroup$ – stefanix Jan 4 at 10:46
  • 1
    $\begingroup$ @YehudaLindell Would you mind expanding on that and putting it in an answer? $\endgroup$ – forest Jan 4 at 10:49
  • $\begingroup$ @sejpm’s answer is sufficient. I suggest looking at the paper. Note that Katz Lindell doesn’t give a proof of this, but only explains the idea. $\endgroup$ – Yehuda Lindell Jan 5 at 17:42
3
$\begingroup$

So the question is if ECIES gives by default IND-CCA2 security?

Yes it does. There's a proof in modern Cryptography by Katz and Lindell, but I'll leave that one to Yehuda to write an answer around. This answer will instead be based on DHIES (PDF) which is the generalization of ECIES and essentially does an ephemeral DH key exchange with the public key, hashes the shared secret and performs an encrypt-then-mac authenticated encrytion of the payload using the hashed secret.

The paper states the security bound as

$$\mathrm{Adv}^{\text{ind-cca-fg}}_\text{DHIES}(t,q,\mu,c) \leq \mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}(t,0,0)+ 2\cdot\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}(t,q)+ 2\cdot\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}(t,1,c,q,\mu)$$

with $t$ being the upper bound on the time complexity of the adversary and $q$ being the upper bound on the number of decryption queries and $\mu$ being the upper bound on the number of bits asked to the decryption oracle and $c$ being an upper bound on the length of the challenge ciphertext for the CCA experiment. $\mathrm{Adv}^{\text{suf-cma}}_\text{MAC}$ is the SUF-CMA security of the MAC and $\mathrm{Adv}^{\text{ind-cpa-fg}}_\text{SYM}$ is the CPA security of the symmetric cipher.

Now only remains $\mathrm{Adv}^{\text{odh}}_{\mathcal G,H}$ which is the advantage with which an adversary can distinguish $(g^u,g^v,H(g^{uv}))$ from $(g^u,g^v,R)$ with $R,u,v$ being randomly sampled from either the group or the hash output set. Additionally the adversary is given access to an oracle computing $\mathcal H_v(X)=H(X^v)$.

So if the above Oracle Diffie-Hellman (ODH) assumption is hard for the given group (and it should be for elliptic curves), and if the symmetric cipher and the MAC are secure, then ECIES is also secure.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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