12
$\begingroup$

NIST selected Kyber for key agreement and Dilithium for digital signature applications some days ago. But IDF's MATZOV group, in their paper, broke Kyber and Dilithium and brought the security levels of these schemes below the thresholds defined by NIST for a secure PQC scheme.

Why did NIST not consider MATZOV's attacks? And because attacks only get better, if the security of these schemes is currently below the thresholds, can these schemes remain secure for a long time?

$\endgroup$
1
  • 5
    $\begingroup$ The answer by Daniel S is very good. I would just emphasize that the MATZOV analysis is in the RAM model, which (unrealistically) assumes that random access to an arbitrarily large memory is essentially free. $\endgroup$ Jul 14, 2022 at 12:51

1 Answer 1

10
$\begingroup$

NIST did consider the MATZOV attacks. If we read their Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process, we see in section 4.1.1 on page 29:

During the third round, some improvements to the dual attack were proposed [163, 164], leading to lower estimated security in the RAM model than was claimed in the KYBER specification. These results suggest that all three KYBER parameter sets fall slightly below the security targets for their claimed security levels when the cost of memory access for the attacker is not explicitly taken into account.

with a similar statement in section 4.4.1 on Dilithium. This suggests that either NIST will be tightening their costing definitions to more explicitly account for memory access or that the standard when produced will reflect the newly assessed security.

Costing Models

Again from the status report section 2.2.1:

In some cases, questions have arisen regarding whether various parameter sets meet their claimed security strength categories.[...] NIST security strength categories are defined in a way that leaves open the relative cost of various computational resources, including quantum gates, classical gates, quantum memory, classical memory, hardware, energy, and time.[...] Different opinions can therefore arise regarding what constitutes a plausible assumption regarding the relative cost of computational resources.

It may be that NIST elect to be define a tighter, more explicit attack model under which the MATZOV attacks require more resources than are allowed by the thresholds set. There's some discussion of attack models in Appendix B. However, they do go on to note in section 2.2.1:

even if one has agreed upon a model or a range of models for evaluating the relative cost of various computational resources, there may still be uncertainty how much of a given resource an attack actually requires.[...] the comparative lack of published cryptanalysis using more realistic models may bring into question whether sufficient effort has been made to optimize the best-known attacks to perform well in these models.

and as the questioner observes the attacks may improve.

Recommendations of the standard

Also in the report, section 5

As part of the drafting process, NIST will seek input on which specific parameter sets to include, particularly for any at security category 1.

which appears to leave room to adjust the matching of security levels to parameter sets. For example, NIST may produce a standard that endorses Kyber-768 (intended to meet security level 3 equivalent to 192-bit AES) to meet security level 1 (equivalent to AES-128). Note that the pq-crystals.org contains the following advice to those wishing to use Kyber today:

We recommend using the Kyber-768 parameter set, which—according to a very conservative analysis—achieves more than 128 bits of security against all known classical and quantum attacks

with a similar statement for Dilithium3 (they also recommend any current usage deploy in hybrid mode with existing methods).

All of this will be somewhat speculative until the draft standards are available. NIST may propose changes to parameters between the selection and standardisation, though this proved controversial with SHA3.

$\endgroup$
3
  • $\begingroup$ This is a very good point, but doesn't quite address the question why these if there are attacks. Are similar or better attacks known for the other contenders? $\endgroup$
    – DRF
    Jul 14, 2022 at 12:57
  • $\begingroup$ Thanks for the NIST link - I was going to ask why they selected only one KEM, but the link answered that (they are still looking at other KEMs) $\endgroup$ Jul 14, 2022 at 14:31
  • 4
    $\begingroup$ @DRF the MATZOV attack also applied to SABER; there were also much more serious attacks on Rainbow and GeMMS by Buellens. Other contenders typically were not felt to have performance and bandwidth properties to match Kyber. The NIST report gives reasons for its decision for each candidate. $\endgroup$
    – Daniel S
    Jul 14, 2022 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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