What’s With Cryptosystems on Lattices (Safety of Lattices)

Problem

The authors claim that cryptosystems on lattices are more “risky” than usually assumed. For example, this applies to establishment schemes common key on lattices currently under consideration by NIST.

In addition to problems with cryptographic primitives (and patents), the authors indicate problems with implementation. Some programs are written in Sage, which does not provide const code execution. Part is implemented in C and can be achieved constness, but this still needs to be checked because compilers do not guarantee.

You can check the constancy of execution, for example, using utilities TIMECOP.

Current implementations are not tested for correctness, compliance with the specification, reference implementation on Sage and implementations in C. And even if all this is carried out, this is only the beginning of testing.

Article

Article: Risks of lattice KEMs

Conclusions

The article presents two main types of risks:

1. Risks associated with cryptographic primitives (development of attacks on the bars, the emergence of new attacks)
2. Implementation risks

Risks associated with cryptographic primitives

The first risks were and always are, but they are not so critical, especially for cryptosystems of the third round of standardization and, in the future, standardized systems. They are related to the fact that candidates for there are many standardization and post-quantum cryptosystems in general, and there are relatively few cryptanalysts. They cannot quickly cover everything diversity. Due to the selection procedure, the cryptosystem becomes fewer, and there are more cryptanalysts since new scientists come in in the area due to the growing interest in the topic.

Implementation risks

These authors mainly include non-constant execution time, different cryptographic primitives, and inconsistencies in compiled programs and specifications. NIST is one of the strict requirements for candidates for post-quantum standardization is presented by a constant running time, and, in connection with the aforementioned selection, more and more incorrect implementations are discarded or modified in such a way as to replace non-constant (non-constant-time) operations are constant (constant-time).

We, in turn, also implement those parts to which access intruder, constant. Regarding compliance with the specification, we use known tests with a known answer (known-answer tests, KAT). If there is no possibility, we use the developments of the open-source community, comparing your implementation with existing ones. If we implement

some crypto-systems for which there are no known available implementations, we also implement the Sage version to compare values ​​with her.

In addition, all our developments are open source, and we follow the changes

candidates in the NIST competition and implement them promptly.

Result

Thus, it is impossible to get rid of risks completely. Yes, before the currently used DES3 cryptosystem, there were sets of weak keys, like the Magma symmetric encryption algorithm, which is part of GOST. There are also well-known attacks for public-key cryptosystems, but these cryptosystems continue to be used since attacks are only narrow the choice of cryptosystem parameters or key parameters. So, for example, attacks on RSA have known: an attack on a small size closed exponents, an attack using the Chinese remainder theorem on messages encrypted with the same private key but with different

modules and so on.

Links

🔗 https://ntruprime.cr.yp.to/warnings.html

Information on constant time:

🔗 https://www.bearssl.org/ctmul.html

🔗 https://research.tue.nl/en/studentTheses/a-performance-study-of-x25519-on-cortex-m3-and-m4