How to make cryptographic techniques more efficient?
Sharing scientific data, transferring money, or sending other sensitive information online: with cryptography, applications make sure your data does not fall into the wrong hands. Mathematician Thomas Attema (CWI/TNO/Leiden University) helps with this. For his PhD research, he developed a new technique to make data encryption even more efficient. PhD defence on 1 June.
In his thesis, Attema focuses on zero-knowledge proofs. ‘These are techniques that allow someone to prove that they know a secret without revealing that secret,’ he says. ‘Zero-knowledge proofs are already widely used, for example for digital signatures on the internet. You can use them to prove that you really are who you claim to be.’
Zero-knowledge proofs have been in use for years to secure communication channels. ‘A lot of knowledge about them has therefore been developed in recent years and all kinds of internet protocols already make use of them. Over twenty-five years ago, my supervisor Ronald Cramer introduced the Σ-protocol theory. That is an umbrella theory for designing and analysing a building kit for a large group of zero-knowledge proof systems: the Σ-protocols.’
Could it be a bit smaller?
Σ protocols are very useful and usually very efficient, but in certain application scenarios, this efficiency still falls short. Attema: ‘If you want to prove something complicated, for example that your outcome of a super complicated calculation is correct, Σ-protocols are no longer so efficient. This is because the size of a proof grows proportionally to the size of the calculation. In some applications, that requires a lot of data traffic.’
‘Our 25 years of experience could go straight into the bin.’
Folding mechanism should replace old technology
Between 2016 and 2018, others therefore developed a clever "folding mechanism" that made the proofs a lot smaller. ‘This new theory should replace the ordinary Σ-protocol theory,’ says Attema. ‘It is definitely a breakthrough in terms of more efficient proofs. However, the downside is that there are no theories and tools for this yet. So our 25 years of experience with Σ-protocol theory could go straight into the bin, after which we would have to redevelop all the knowledge and techniques.’
To avoid that, Attema and colleagues developed the so-called compressed Σ-protocol theory. 'With this, we reconcile Σ-protocol theory with the new folding mechanism. We thus show that the folding mechanism need not be a replacement for Σ-protocol theory, but can complement and strengthen it.' The researchers built their theory out of several separate building blocks, allowing analyses of smaller chunks of information as well. That too contributes to efficiency. Furthermore, Attema and co-authors proved some outstanding theorems within the general theory of zero-knowledge proofs.
Helping patients without violating their privacy
Attema’s research findings will undoubtedly find their way into the real world. ‘The desire to make blockchain technologies more privacy-friendly has greatly stimulated the development of new efficient zero-knowledge proof systems,’ he says. ‘Nowadays, however, people are also working on all kinds of other applications. Think, for example, of cloud computing, where you let another party perform calculations on your data. With zero-knowledge proofs, you can efficiently test whether the results you receive are actually correct.’
‘At TNO we are also working on multi-party computation (MPC), a way to release calculations on combined data from multiple parties, without those parties having to share their data with each other. This is useful for hospitals, for example. They can then combine patient data to improve treatments or develop new drugs, without compromising privacy. Using zero-knowledge proofs, we can further improve the security of some MPC solutions.’
Collaboration with TNO
Attema did his doctoral studies part-time. ‘I am employed by TNO, Department of Applied Cryptography and Quantum Algorithms. There I do applied research. In addition, I did more fundamental mathematical research at the Centrum Wiskunde & Informatica (CWI) in Amsterdam.’ Even after his PhD, Attema continues to work in the same structure. 'After graduating in algebraic number theory, I wanted something more towards practical application. I certainly found that possibility in cryptography.'
Text: Diana de Veld