NIST publishes quantum resistant encryption algorithms – Tutanota already uses them in a prototype!

CRYSTALS-Kyber and CRYSTALS-Dilithium have proven to be the best choice for quantum resistant encryption in our email prototype.

NIST publishes quantum resistant encryption algorithms.
Encryption is the best tool to protect your private data. To make sure your data stays secure in the future, post-quantum secure encryption is needed. Now, NIST pushes ahead with CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, SPHINCS+ algorithms to harden encryption against future attacks from quantum computers. We at Tutanota have already built a prototype with these same algorithms. We plan to upgrade the encryption in Tutanota well before quantum computers are able to break currently used algorithms.

Tutanota has already developed a working prototype to securely encrypt emails with the now defined algorithms by NIST, namely CRYSTALS-Kyber and CRYSTALS-Dilithium. “The algorithms now picked by NIST have proven to the best choice for quantum resistant encryption in our email prototype”, explains Vitor Sakaguti, member of the research project PQMail.

PQMail research project

During the research project that Tutanota executed together with the L3S research institution of Leibniz University Hanover, the researchers evaluated all NIST algorithms from Round Two in regards to security, a low resource impact and a fast performance before settling on CRYSTALS-Kyber and CRYSTALS-Dilithium.

NIST candidates: CRYSTALS-KYBER & CRYSTALS-Dilithium

Now, NIST said in a statement that they “recommend two primary algorithms to be implemented for most use cases: CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures)”.

“That these algorithms have now been picked as final candidates by NIST is the best case scenario for us”, says Vitor. “At the same time, it does not surprise us that NIST settled on these algorithms as they performed the fastest. Our protocol was designed to theoretically being able to work with any of the candidates from the NIST competition, but our performance tests showed that the CRYSTALS family would provide the best experience for our users.”

“CRYSTALS-Kyber and CRYSTALS-Dilithium had the lowest resource impact (key and signature sizes) and were the fastest while still providing the security levels we were targeting, that is, at least as secure as 128 bit security with current algorithms on classical computers.”

Next steps: Harden security

The next step of NIST, Round Four, is being eyed closely by the cybersecurity community, and particularly by us at Tutanota: “Now we are going to see a lot of effort going into trying to break these algorithms. This is a good thing: We want researchers to find any possible weaknesses so that they can be fixed. The more mature these algorithms get, the more confident we can be about the security of our protocol”, adds Vitor.

The selection process of NIST is going exactly as it should to achieve cryptographic resilience. For instance one of the already ruled out candidates in the NIST process has been proven to be completely broken: The algorithm Rainbow can be broken within two days – not with a quantum computer, but with a normal laptop, according to researchers from IBM.

Tutanota secure data automatically

By investing early-on in post-quantum secure encryption we at Tutanota deliver on the promise made to our users: to build the most secure email service out there.

The next step for us will be to implement the new post-quantum secure encryption protocol into Tutanota itself. Once that is completed, millions of Tutanota users will instantly benefit from post-quantum secure encryption.

As the migration to new algorithms is done automatically in Tutanota, users will not have to do anything. Once the new protocol is implemented, all data stored in Tutanota – that is emails, contacts, and calendars – are automatically encrypted with the new algorithms.

This will safeguard all data of millions of users against attacks from quantum computers.