According to the web page for NewHope, an R-LWE post-quantum key encapsulation mechanism (KEM) candidate for standardization, it comes in types that are IND-CPA or IND-CCA secure. I know what CPA and CCA security are, but I don't understand the difference between the two types of NewHope and why there needs to be a choice between one or the other (unlike, say, RSA-OAEP which provides both).
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Well, the CPA version is roughly twice as fast and may sometimes be sufficient in terms of security (even though a quick search didn't turn anything up). $\endgroup$– SEJPMCommented Dec 30, 2018 at 11:30
-
$\begingroup$ Roughly speaking I suppose to make the scheme CCA-secure, additional, stronger attacks need to be considered. To prevent these attacks and keep the same security level, the parameters need to be chosen larger than for CPA-security. (I'm sure the NewHope specification explains their choice of parameters for both settings.) $\endgroup$– TMMCommented Dec 31, 2018 at 15:15
-
$\begingroup$ I am not sure if this is what you are asking, but their statement is no exclusive or. CCA security always implies CPA security. So, if you choose the CCA version you got the same setting as RSA-OAEP (of course now against quantum adversaries but in terms of security games it is the same). $\endgroup$– mephistoCommented Jan 3, 2019 at 10:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times.
In this straight-forward implementation, Alice generates a private vector $a$, and sends his key share $a M + \epsilon$. Then, when Bob receives this key share, he generates a private vector $b$ and sends his key share $b M + \epsilon'$ and a reconciliation vector. This reconciliation vector is needed because the vectors that both sides compute won't be precisely the same (because of the error vectors $\epsilon, \epsilon'$), and advise Alice how to do the rounding.
The best known attack involves the attacker sending incorrect bits in the reconciliation vector, which (over a number of exchanges) can yield individual values from the $a$ vector.
In the CPA version, they assume that you'll never reuse the same public value over multiple exchanges, and so this attack is irrelevant.
In the CCA version, they can't make this assumption. What NewHope team has decided to do is to use to have Bob generate his key share from a seed in a deterministic way and encrypt that seed as a part of the ciphertext, and so when Alice gets it, she can decrypt the seed and then regenerate what Bob's key share should be (based on the seed), and see if that's the value she got; this prevents attacks (like the above) which are based on sending illegitimate keyshares.
Of course, all this extra checking slows things down; that's why the CCA version is slower.
-
$\begingroup$ Does that mean that the CPA version would be fine for forward secrecy, since each public value would be unique for that session, but any long-lived public key (for GnuPG in the future, say) would want to be CCA? $\endgroup$– forestCommented Jan 4, 2019 at 4:10
-
1$\begingroup$ @forest: yes, CPA is fine as long as generate a fresh public/private value each time (which is precisely what you do when trying for PFS) $\endgroup$– ponchoCommented Jan 4, 2019 at 14:27
-
$\begingroup$ @poncho can you share a paper or other resource where this attack is described in more detail? $\endgroup$– jvdhCommented Mar 10, 2020 at 11:01
-
1$\begingroup$ @jvdh: eprint.iacr.org/2016/085.pdf $\endgroup$– ponchoCommented Mar 10, 2020 at 11:26