OFFICIAL COMMENT: Round2
Jan-Pieter D'Anvers
Dear all,
I believe that the proof of the IND-CPA security of Round2
contains a flaw.
In the security proof of ROUND2.CPA-PKE, you state that the
advantage of an adversary distinguishing between game G3 and G4 is
less or equal then his advantage of solving the specific dGLWR
problem mentioned in formula 13. However, the adversary has
possibly more information in the first case (distinguishing games
G3 and G4) since he is given extra information about the secret
key R embedded in v (line 6-7 in Game G3 and G4). Therefore, it is
possible that the advantage of the adversary in distinguishing
Game G3 and G4 is actually bigger than solving the dGLWR problem.
A similar problem can be found in the security proof of
ROUND2.CPA-KEM.
To work around this issue, the step from Game G3 to Game G5 could
be done in one step, comparing it with one similar dLWR problem
(with extra samples), similar to Bos et al. [1]. However, due to
the rounding, it becomes more involved when working with LWR.
For the uRound (powers of two) parameters, you can take the same
route as we did in the security prove of Saber (the paper
containing the proof has not been put on eprint yet). This proof
proceeds from game G3 by adding two additional games G3a and G3b.
In game G3a, B is generated uniformly from R^{d/nxn}_{n,q},
X is calculated as <B^T R>_q, and v is now send with
log2(t*q/p) bit coefficients. Here you can prove that the
advantage of the adversary in Game G3a is at least as big in Game
G3, since he can easily calculate the same values as in Game G3 by
taking mod p of B and mod t of v.
In game G3b, the amount of error introduced in the coefficients of
v, and the coefficients of U, is equalized. This can be done by
calculating both with Rcompress_q-->max(p,t*q/p). Again, the
advantage of the adversary in Game G3b is at least as big as in
Game G3a, since he can easily calculate the same values as in Game
G3a.
After this, you can go to Game G5 in one step analogue to
Algorithm C.
Kind regards,
Jan-Pieter D'Anvers
[1] Joppe Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael
Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas
Stebila. Frodo: Take off the ring! Practical, Quantum-Secure Key
Exchange from LWE. Cryptology ePrint Archive, Report 2016/659,
2016. http://eprint.iacr.
org/2016/659.
Mike Hamburg
Could you explain how you derived your NIST category claims?
As I understand them, the categories are roughly:
Category 1: >= 2^128/MAXDEPTH
Category 2: >= 2^128
Category 3: >= 2^192/MAXDEPTH
Category 4: >= 2^192
Category 5: >= 2^256/MAXDEPTH
where MAXDEPTH is probably between 2^40 and 2^64 for a quantum machine, and 1 for a classical machine.
Compare for example nRound2.KEM_{n=d}, as shown in Table 11. The estimated security levels against the strongest attack (hybrid) are as follows:
NIST1: 2^74
NIST2: 2^97
NIST3: 2^106
NIST4: 2^139
NIST5: 2^139
Am I misreading these tables, or misunderstanding the categories? Is the attack model here something very favorable to the attacker, so that it doesn’t match NIST’s model?
Thanks,
— Mike Hamburg