Research, Collaboration, Impact! Privacy technologies for the quantum age

Professor Martin Albrecht, a recently appointed expert in post-quantum cryptography, has won one of the most prestigious grants from the European Union to do foundational work at the Department of Informatics at King's College London. Martin develops robust algorithms that make sure that privacy-preserving applications from contact lookups on messaging apps to e-cash will be safe for us to use once powerful quantum computers arrive.  

Background

Quantum computing has captured the mainstream – hardly a day goes by without an announcement of breakthroughs in engineering, or pieces in the media that either rejoice at or warn about ‘Q Day’. A time when a useful quantum computer arrives that can run new types of algorithms that are unavailable or impractical for ‘classical’ computer systems.

Quantum computing exploits the quantum phenomena of superposition and entanglement to build a radically different kind of computer. Qubits, the quantum equivalent of bits, can be made to stand in a special kind of relationship with each other that enables them to hold many calculations simultaneously. In principle, this would make quantum computers exponentially faster in solving certain types of problems.

While not universally better at everything, quantum computers are likely going to be particularly good at cracking the encryption protocol we presently use to secure our online communication. For good reason, much of the media attention has therefore focused on the risks and challenges of a future quantum computer potentially breaking into our online banking or the fallout of a nation-state adversary siphoning off sensitive communication. In response to the challenges that quantum computing poses for keeping our data secure, NIST, the US National Institute of Standards and Technology, has started standardising quantum-resistant public-key cryptographic algorithms.

Quantum-resistant cryptography research at the Department of Informatics

In July 2022, NIST announced the first four winners of its competition to find quantum-proof algorithms that secure our online communication and computer systems against attacks from a powerful quantum computer. Three out of the four winning specifications that NIST selected cite Martin’s ongoing research on lattice-based cryptography. Lattices are complicated point structures that are placed over information in order to encrypt it – even a quantum computer will find it impossibly difficult to find the key that is hidden in these intricate mathematical structures.

Figure 1: Example illustration of the volume of a lattice. Picture credit: Joop van de Pol. 

However, with the focus on public key cryptography, too little attention has been paid on getting other important technologies quantum-ready, Martin says. Perhaps unbeknownst to many users, we employ a great deal of algorithms in our everyday lives that make our communications and interactions safe and ensure that things run as they should. Examples are algorithms that expediate recovery from security breaches, which is important in cloud storage, or protocols that preserve data privacy when we look up contacts on messaging apps such as Signal and WhatsApp, require credentials or make online payments.

‘I had been working a lot on figuring out how long it would take a quantum computer to find the shortest vector for an attack and I noticed this really big gap in what we focus on protecting’, Martin recalls. It is by no means straightforward to carry over functionalities that work well today into the world of quantum. ‘There is a lot of cool, privacy-preserving technology that will go away unless we find replacements for a post-quantum setting’, Martin continues.

Recently, Martin was awarded a grant worth €2 million from the European Research Council to carry out foundational work in getting privacy-preserving technologies ready for the quantum age. The Consolidator grant is one of the most prestigious awards that the European Commission has to offer. ‘This is a big success and something I’m quite proud of’, Martin affirms.

Next steps: finding practical solutions

Over the course of the grant, Martin wants to pursue three interrelated issues at the department. Making headway in finding post-quantum replacements for privacy-preserving technologies first requires a solid understanding of the true computational costs of lattice-based approaches in cryptography, he says. This means finding a principled answer to the question, how difficult will it actually be for quantum computers to crack lattice-based schemes, in particular if they can glean additional signals or hints about some structure. This is in order to get a firm sense of their goodness and usefulness for encryption.

Figure 2: Details of a construction for a quantum-resistant, privacy-preserving scheme.

Responses to this problem will then enable Martin and his team to arrive at a better understanding of the assumptions that can allow for feature parity with ‘classical’ solutions so that post-quantum algorithms can be as good as their pre-quantum counterparts. And finally, there is the challenge of working out how well exactly lattice-based cryptography sits with other assumptions and approaches to cryptography.

There are many exciting practical applications of this line of work beyond the examples above. ‘If you hit a website and it asks you to fill out these CAPTCHAs all the time, it can be annoying. Cloudflare has a solution for that’, Martin explains. ‘And that is, instead of doing that every single time you visit the site you do it only once, and then they give you a bunch of tokens that you can spend each time you go back to the site–of course, these tokens need to be anonymous’, he continues. This is just one example of many practical functionalities we employ today that Martin wants to preserve in a quantum-enabled world. While the domain of quantum computing is riddled with uncertainties about quantum advantage and timelines for development, one thing seems certain: the project Martin and his team are going to deliver will be crucial to get us ready for the arrival of quantum computers.

Martin has joined the Department of Informatics at the right time. Cryptography is a strategic priority there. The department is committed to hire new, internationally recognised, permanent staff to bolster King’s research in this critical domain. Martin is very much spearheading this move. ‘We’ll have exciting opportunities coming up for PhD students and postdocs’, he says, and ‘we’re going to have a sizeable team of cryptographers here at King’s Informatics’, Martin continues. ‘They’ll be well embedded in the Cybersecurity group and of course have links with the Department of Mathematics due to many intersections of our research.’

Looking ahead towards standardisation

What is the ultimate aim of Martin’s research? ‘I hope that at the end of the grant, we’re ready towards standardising some of these more advanced solutions’, he says and points to the fact that he really wants his work to have a tangible impact on the real world. ‘So the way cryptography gets deployed is similar to what NIST are doing’, he explains. ‘You put your academic papers to the standardisation bodies so that they can turn them into standards that can be implemented by companies and other organisations’.

Martin is well placed to make sure standards work for industry thanks to his deep expertise of the private sector. A member of the post-quantum cryptography team at SandboxAQ, his research aligns with the cutting-edge work that is being carried out at companies looking to commercialise quantum technologies.

Reflecting on the first six months of his time with the Department of Informatics, Martin seems to have found the perfect institutional home. ‘My colleagues are all extremely competent and very ambitious’, he says, ‘which is the perfect combination’. With Martin being all set and ready to deliver quantum-safe solutions soon enough, the arrival of quantum computers should become less of a spectre for cryptographers and privacy champions alike.

Written by Juljan Krause