First off, we apologize for the long delay. We wanted to respond
to all of the raised issues at once, and coordinating that response
took longer than we expected.
There were two issues identified in the email thread Dan started.
The first issue is Theorem 5.1 about the tight IND-CCA security of
FrodoKEM from the OW-CPA (instead of IND-CPA) security of FrodoPKE in
the classical random oracle model.
Indeed, the change in hypothesis from IND-CPA to OW-CPA was a typo
that was inadvertently introduced in the revisions between the round-1
and round-2 submissions. We did not intend to claim a new tight
security proof from OW-CPA security; as stated in both submissions, we
rely on the prior results of Hofheinz, Hövelmanns, and Kiltz. (In the
round-2 submission we also use a more recent result of Jiang, Zhang,
Chen, Wang, and Ma on IND-CCA security from OW-CPA security, in the
*quantum* random oracle model.)
The second issue is how the Rényi divergence argument applies in the
FrodoKEM uses specific error distributions in its instantiations, but
we claim security based on LWE with rounded Gaussian distributions.
We argued that this substitution was sound due to the results of
Langlois, Stehlé, and Steinfeld, because the Rényi divergence of the
new distribution from the original one is sufficiently small. However,
as pointed out, the results of LSS hold for search problems, whereas
the problems named in the round 2 submission (IND-CCA, IND-CPA,
decision-LWE) are decision problems.
Nonetheless, there *is* a search problem in the HHK reductions (for
the classical ROM): the sequence is IND-CPA -> OW-PCA -> IND-CCA, so
we can apply the Rényi divergence argument at the OW-PCA step.
We have revised Section 5.1 of the specification to make this
explicit. In particular, the new Theorem 5.1 shows the result of
combining the IND-CPA -> OW-PCA -> IND-CCA reductions with the Rényi
divergence argument at the OW-PCA step. Various other parts of
Section 5.1-5.1.4 have been reorganized as part of this revision.
We emphasize that neither the FrodoKEM scheme nor any of its
parameters have changed. In addition, this analysis shows that the
IND-CCA security of FrodoKEM can be tightly based solely on the OW-PCA
security of the "T-transformed" (deterministic) version of FrodoPKE.
In other words, IND-CPA security of FrodoPKE and hardness of
decision-LWE are not *necessary* assumptions, but they can be used to
show OW-PCA security.
Finally, we have added concrete calculations of FrodoKEM's IND-CCA bit
security under the chain of classical reductions, assuming our
bit-security estimates for the LWE problem, taking into account the
various losses associated with the reductions (number of LWE samples,
Rényi divergence, probability of decryption failure). The new Table 2
shows these estimates.
A few other insubstantial typos were fixed during our revisions, and
various other arguments were made more precise. A list of changes
appears at the end of the revised document.
Our revised specification document, as well as all previous versions,
is available at https://www.frodokem.org/
The FrodoKEM team
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20190625171803.19157.qmail%40cr.yp.to