Making cryptographic techniques more efficient

Sharing scientific data, transferring money, or sending other sensitive information online: with cryptography, application make sure your data does not fall into the wrong hands. Mathematician Thomas Attema (CWI/TNO/University of Leiden) helps with this. For his Ph.D. research, he developed a new technique to make data encryption even more efficient.

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."

Overarching theory

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 analyzing 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."

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."

Reconciled theories

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."

Provided by Leiden University