TU Eindhoven makes future internet safer

Andreas Huelsing, Assistant professor in the Coding Theory and Cryptology group at TU Eindhoven, has made future Internet security quantum computer proof by developing the eXtended Merkle Signature Scheme (XMSS). XMSS is the first post-quantum digital signature scheme that now has been approved as a request for comments (RFC) by the RFC editor. RFCs define the standards for the Internet. This is a major step to enable the use of it in everyday applications.

Today, cryptography is all around us. It secures messaging apps on mobile phones, transactions between banks when paying with a debit card at a local grocery shop, the data we send through a contact form on a secure website, and the many more times people send messages in any form from A to B. Signature schemes provide authenticity of any kind of data, like messages or documents. In a secured Internet connection with your bank, for example, they are used to ensure that you are really talking to your bank and not to an attacker. In general, the most important application of digital signatures are software updates. These are signed by the software company such that you do not install an update by a malicious party. 

Quantum computers
Current cryptographic algorithms are sufficient for protecting our personal data in the current time. However, more and more research is going into the development of a quantum computer. When they succeed in building such a computer, it will have a major impact on cryptography. A quantum computer is not just a super-fast computer, the power of a quantum computer lies in exploiting certain structures in mathematical problems. And those are exactly the problems on which current Internet cryptography is based. This means that the moment the quantum computer arrives, our data will no longer be safe.

That is the reason why, among others, Andreas Huelsing has been anticipating the post quantum era and worked on post-quantum cryptography; cryptographic algorithms that can withstand the power of quantum computers. His research, funded by the Horizon 2020 project PQCRYPTO, lead to the development of the eXtended Merkle Signature Scheme (XMSS) and its acceptance as a de-facto Internet standard in the RFC editor. 

Hash-based signature scheme
XMSS belongs to the class of hash based signatures. Hash-based signatures provide cryptographic digital signatures without relying on the conjectured hardness of mathematical problems. Instead, it is proven that they only rely on the properties of cryptographic hash functions which makes them resistant to quantum attacks. Most schemes rely on the following two properties of cryptographic hash functions:

1. One-wayness: Cryptographic hash functions are easy to evaluate but hard to invert. Given an output of the function it is practically infeasible to find any input which the function maps to this output.
2. Collision resistance: It is practically infeasible to find two inputs which the function maps to the same output.

XMSS
XMSS is the most recent of these hash-based signature schemes which comes with several security and performance improvements compared to previous proposals. Most notably XMSS is collision resilient: its security does not rely on collision-resistance. Collision-resistance turned out to be a hard to achieve property as demonstrated by collision attacks for previous hashing standards MD5 and SHA1. Therefore, not relying on collision resistance improves security. It also directly improves performance as it allows to use smaller parameters at the same level of security.

XMSS is suitable for compact implementations, is relatively simple to implement, and naturally resists side-channel attacks. Unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers.

Basic idea of hash-based signatures
The very basic idea is the following: Assume two friends -- Alice and Bob -- sitting in the train discussing about going out the next evening. Alice is not sure if she can make it as she forgot her agenda at home. So, she wants to inform Bob when she is home and checked her agenda. She will send 1 if she can make it or 0 if she can't.

As Alice has a mean little sister Eve that knows computers very well she want to make sure that Eve will not alter her message. Hence, Alice generates a pair of random bit strings x_0 and x_1, computes their hash values y_0 and y_1, and hands these to Bob. When she is home, she will send her one bit message b to Bob together with x_b. Now, Bob can hash x_b and compare the result to y_b. If the two match Bob knows the message was sent by Alice. Indeed, even if Eve would have learned y_0, and y_1 and intercepted Alice message, she could not have altered Alice message without making the verification fail.

In this example the x_0, x_1 take the role of the private key, the y_0,y_1 that of the public key and x_b is the signature. This very basic scheme can be extended to n bit messages, using n pairs x_0,x_1,one pair per message bit. The resulting scheme is one-time: a key pair can only be used once. Hence, there are several more steps needed to actually arrive at a full signature scheme.

Major step
Approving XMSS as an Internet standard is a major step in taking the research into practice, and thus making the Internet quantum computer proof. For most applications it is now the point where profiles for XMSS data structures can be specified to allow using XMSS. It is also the point where national advisory bodies like the German BSI or the US NSA-IAD can actually require the use of XMSS for applications in their guidelines and algorithm catalogues. However, for any proprietary use these hurdles do not exist. Hence, there are new crypto currencies and mechanisms for software updates that already make use of the schemes described in the RFC.