OFFICIAL COMMENT: Round2

[Alperin-Sheriff, Jacob (Fed)]

Round2 Team:

 

Your submissions appear vulnerable to the “precomputation” reaction (CCA) attack.

 

To remind those of what I’m talking about, the way this sort of attack works on LWE/LWR-like schemes is

 

1. Adversary receives the public key
2. Using a large amount of computation (equivalent to more than 2^64 operations but still quite a bit less than 2^128 operations),

It identifies a large number of messages m to use in the CCA-secure scheme to generate rho (and from there to generate R) such that i_U (as used in the error analysis) will be a fair amount bigger than it would be on average. This will make decryption failure significantly more likely on these messages than on an average one.

 

My guess is there are somewhat more sophisticated techniques for choosing such messages such that, e.g. with even higher probability among subset of messages at least one is much higher than expected probability to cause a decryption failure (possibly choosing such messages to be closer to orthogonal to each other might help?) but I’m pretty sure even this will allow you to get a set of 2^64 messages (maximum we allow CCA queries on) such that the probability of any of these messages resulting in a decryption failure is somewhat under 2^{-64}, meaning that with high probability, decryption failures can be caused with the 2^64 required queries.

Hopefully I’ll get a more sophisticated analysis of this done next week.

—Jacob Alperin-Sheriff

 

[Alperin-Sheriff, Jacob (Fed)]

Certainly this makes all of the parameters for  nRound2.KEMn=d  parameters dead because either the decryption failure rate is less than 2^{-64} for fully honest running of the algorithm or it falls to < 2^{128} classical attacks

[Alperin-Sheriff, Jacob (Fed)]

This comment was a mistake. When I was reading through the parameters I mistakenly thought that (as for almost every other submission) the KEM was the CCA version.

 

Long story short, assuming the error rates given in the supporting documentation are correct (I’m a little leery about this since using prime-order cyclotomic rings should be causing a big jump in the noise unless I’m missing something …), I don’t see any clear “precomputation” reaction CCA attack.

 

From: "Alperin-Sheriff, Jacob (Fed)" <jacob.alpe...@nist.gov>
Date: Friday, May 25, 2018 at 4:12 PM
To: pqc-comments <pqc-co...@nist.gov>
Cc: "pqc-...@list.nist.gov" <pqc-...@list.nist.gov>
Subject: OFFICIAL COMMENT: Round2

 

Round2 Team: