While quantum computers hold much promise, they also represent a critical threat to the security of the internet, as they may undo current cryptographic defenses. To develop new quantum-proof cryptography, the leading standards authority NIST has invited researchers all over the world to come up with solutions. Now, two algorithms developed at the Eindhoven University of Technology (TU/e) have been selected for the final of this competition, and may become the new standard. Two other TU/e solutions have been chosen as promising runner-ups for further consideration.
Researchers around the world, including here at TU/e, are working hard to build a quantum computer. It promises extremely speedy computing, enabling fast solutions for problems that would literally take ages for a classical computer. Quantum computing is however a double-edged sword: it threatens to break all cryptographic security mechanisms that currently protect our sensitive communications and data. Think of state secrets, or health records.
In particular, quantum computers would completely break many public-key cryptosystems, including RSA, DSA, and elliptic curve cryptosystems. These cryptosystems are used to implement digital signatures and key establishment and play a crucial role in ensuring the confidentiality and authenticity of communications on the internet and other networks.
Fortunately, researchers are working hard to build post-quantum algorithms that resist such attacks. To aid this process, the US-based National Institute of Standards and Technology (NIST) has launched a multi-year competition to select the best solutions. The winners will become the new standards, and will be adopted by governments and industry across the world.
The competition, which began in 2017 with 69 entries, has just entered its third round. For this round, NIST has selected seven finalists, including two from TU/e researchers: Classic McEliece and NTRU. NTRU is one of the three selected public-key encryption algorithms based on a so-called structured lattices, an approach which according to NIST’s current view appears to be “the most promising”.
In addition, NIST has selected eight so-called alternate candidates, again including two from TU/e: NTRU Prime and SPHINCS+. These runner-ups will be able to compete in the third round, but will probably need an extra fourth round before being considered as potential candidates for standardization.
“Classic McEliece is my recommendation to anybody who needs to protect today's secrets against tomorrow's quantum attackers. For users who have space constraints, I recommend NTRU and NTRU Prime for encryption. I am happy that NIST shares my recommendations”, says Tanja Lange, professor at the Coding theory and Cryptography group at the department of Mathematics and Computer Science and one of the researchers involved in the research.
Assistant professor Andreas Hülsing, lead of the SPHINCS+ team, adds: “It is great to see NIST has selected NTRU as one of the finalists. In addition, it has acknowledged the extremely reliable security of SPHINCS+ and declared it an immediately available algorithm for standardization for applications that need very high security. This means we reached our goal."
The finalists will now undergo a final evaluation round starting this autumn, in the run-up to which the participants have the opportunity to further ‘tweak’ their algorithms. NIST expects that the whole process will be concluded within the next two to four years.
Cryptography used on the internet requires many building blocks that all need to be secure individually and put together safely. Two of these are public-key encryption and digital signatures.
Public-key encryption uses two types of keys to encrypt messages: a public key and a private key. The private key is never shared with anyone else. When the sender wants to send a message, they encrypt it using the public key of the receiver. The message can only be decrypted by using the private key of the receiver.
To guarantee that online communication is with the right person or server, documents are digitally signed. Again, each user has a pair of public and private keys. Here, the private signing key of the sender is used to sign a message, showing that they approve of the message. The receiver can then use the sender's public signing key to verify that the signature is valid, showing that the message is authentic and has not been tempered with.
Although the current cryptographic algorithms work fine for much of our digital communications, they are vulnerable. They rely on hard mathematical problems, which are impossible to crack for classical computers, but which can easily be solved on a powerful quantum computer. Current quantum computers still lack the processing power to accomplish this task, but this may change anytime soon. The NIST competition is designed to come up with replacement algorithms before this happens.
This article was first published here: https://www.tue.nl/en/our-university/departments/mathematics-and-computer-science/the-department/news/news-overview/24-07-2020-algorithms-developed-at-tue-selected-as-potential-new-standards-for-quantum-proof-internet/