We need to do it all the time: proving to someone who we are or what we own. For instance, proving to a social media platform that we own an account and have the right to post messages from this account, proving to a bank that we are the owner of a bank account, or proving to a liquor store that we are over 18 years old. In the case of the liquor store we can just show our ID and the cashier does not store any information that was on the ID. But when we need to prove something online, this is a different story. We need to somehow prove to the other party that we are who we are, but we would rather not reveal any private data. How can this be done in an efficient way?

Nicolas Resch, a computer scientist originally from Canada, works as an assistant professor at the Theory of Computer Science (TCS) group at UvA’s Informatics Institute. His research is about zero-knowledge proofs. “It almost seems like a paradox”, says Resch. “I want to somehow prove to you that something is true without actually telling you anything about why it's true.” To demonstrate how this could work, Resch refers to Where’s Waldo?, the famous illustrated book where you need to find Waldo on a page with hundreds of other people. “I could for example put a blank sheet of paper on the page, and cut out a piece where Waldo is. This way you would only see Waldo and the rest of the information would stay hidden.”

Trade-off

Although the example is very simplified, this is roughly the concept that scientists have been working on as an idea to use zero-knowledge proof in encryption. Encryption is a technique for transferring data while keeping it hidden. But for sensitive information, encryption alone is not enough. There are other ways to send proof, without sending detailed personal information, but they typically take a lot more time because more interaction between the sender and the receiver is needed – the receiver needs to be convinced of the proof. Therefore, the current length of the scheme of encrypted data (all the zeros and ones together) is much larger than the original scheme.

There are different theoretical concepts of tackling this. Currently, the most popular method for constructing proof systems is modular, wherein proof systems are constructed from a large number of separate pieces. “If we put all the pieces back together, you need to make sure that you don’t introduce security vulnerabilities.” Research in cryptography is all about finding the optimal outcome in the trade-off between security and efficiency. “Making things more efficient means you give up on security. If you make things too efficient, then all sorts of private information may be leaked. With our research, we hope to move a little more towards efficiency without compromising security.”

Quantum computer

One important development which requires better cryptography is the quantum computer. Current computers take up too much time when trying to decrypt information, but quantum computers are expected to be much faster. “Already since the nineties we knew that if somebody had a working quantum computer, all current cryptographic schemes would be broken. Fortunately, concepts that I have been working on like code-based cryptography, where error-correcting code is used to protect data from errors, are safe in a quantum computer world.”

Google Wallet

Cryptography with zero-knowledge proof will keep it safe for everyone to securely share data, even when quantum computers will be around. As one of the first big tech companies, Google is now using zero knowledge proof-technology in Google Wallet, making it easier to prove age and identity. The same technique could also be applied to develop so-called ‘delegated computing’. “If you need to do a computationally intensive task, for instance as a scientist or data journalist, you will need to do this computation in the cloud. If you want to know for sure the computer did this computation correctly, you would want to get a proof. We hope to develop zero-knowledge proof in such an efficient way that we would not need to carry around big computers with us, but will still be able to do powerful computing in a trustworthy way. That would be a nice end goal for me.”