PhD graduate pushes forward the field of cryptology

Mathematician and TU/e PhD graduate Christine van Vredendaal has pushed forward the field of cryptography by presenting new insights that strengthen cryptographic algorithms. Firstly, she investigated the mathematical structures on which cryptography is founded, and secondly, she developed a new and reliable post-quantum cryptosystem. Her work was of such high quality, Van Vredendaal was awarded her PhD with distinction.

Nowadays, cryptography is everywhere. Whether you are visiting a secure website, paying by debit or credit card, or messaging on your phone, most of it is encrypted; protected with cryptographic algorithms. These algorithms, that prevent ill-willed persons or organizations from spying on, or even modifying our communication channels, are founded on mathematics. Certain mathematical problems have the property that solving them is believed to be hard unless you have knowledge of some secret information: a secret key. This secret key can be used in combination with a cryptographic algorithm to encrypt messages such that only the owner(s) of the secret key can decrypt the information.

Research has shown that basing cryptography on more structured mathematics, applications become more efficient. However, adding this extra structure can instead harm security. That is why in her thesis Exploiting Mathematical Structures in Cryptography Van Vredendaal investigated exactly which structures are fine to use, and which give tools to attackers that they should not have, and thus might harm security instead of aiding it.

Exploiting side channels
Side channels of cryptographic algorithms are ways to get information on a cryptographic key by using the physical properties, such as the power consumption and the timings of the cache memory, of a device that is doing computations with it. The data gathered by a side-channel attack is often too big or too incomplete to recover meaningful data about the secret key.

However, using the mathematical structure of the secret key in combination with the data, the side channel information can be processed and more information about the key can be gained. Via this method, Van Vredendaal and her colleagues recovered secret keys of the encryption library of GnuPG, which is used on Ubuntu and Debian systems. A leak that has been patched last year.

Post-quantum security
Another threat Van Vredendaal looked at in her thesis is that of the power of quantum computers. More and more research is going into the development of a quantum computer. Although such a device would be a huge leap in physics research, for cryptography it would be a disaster of epic proportions. A quantum computer is not simply a fast computer, but can exploit certain structures in mathematics problems very well, and these are exactly the problems used in cryptography.

Post-quantum cryptography hopes to fix this potential future problem by developing new cryptographic algorithms that rely on hard problems that, to the best of our knowledge, a quantum computer cannot break. However, in many cases it is less researched than current cryptography. So scientists assume they are secure, but exactly how secure is not clear. It also has the drawback that keys are bigger, which in the context of cryptography is definitely not better, since this makes all algorithms much less efficient. It would, for instance, not be good if it takes two minutes to pay at a supermarket, or check in for a NS train.

To mitigate this, it is proposed to add more structure to the mathematical problems to reduce the key size, but also here it is not entirely clear whether this hurts security. Van Vredendaal collaborated with several other researchers to look into the questions whether this recovery of secret keys in post-quantum cryptography is really hard, and if adding more structure to the keys hurts security. This appears to be the case with certain structures called multiquadratic fields, and Van Vredendaal strongly recommends not to use them or structures that have similar properties.

In addition, a new cryptosystem was proposed based on structures that are foreseen to be safe against attacks in the era of quantum computers, but still allow for relatively small keys to guarantee its functionality in practice. Van Vredendaal and her coauthors submitted their system to the NIST competition for post-quantum cryptography, which plans to standardize a quantum-safe cryptosystem for the Internet in the next five years.