30.07.2024IDEAS NCBR: How do you see the role of traditional cryptographic methods evolving with the advent of quantum computing?
Daniele Micciancio: In some sense, not much will change. One of the main achievements of modern cryptography is the ability to give precise mathematical definitions for what it means for something to be secure. This study can be done independently of how you build a cryptographic solution to a problem. Solutions are based on different mathematical problems and some of them are breakable using quantum computers.
Today, researchers are developing solutions that are secure against quantum computers. For example, there are different methods to build an encryption scheme that will make communication secret, even in the presence of an adversary. One can use, among others, problems from number theory, factoring and elliptic curves. We use these solutions every day, but they can be broken using quantum computers.
Lattice problems that I work on are currently considered one of the main approaches to post-quantum security. For instance, digital signatures, currently used to certify that a message is authentic, are not secure against quantum computing and we will need to replace them with solutions based on lattices. But this substitution is something that should not be visible for the end user, so the application will have the same interface. Of course, there are some technical challenges, as lattice cryptography tends to produce larger messages. If your application or protocol has been designed to use messages of a fixed size, it can be harder to replace one with the other. For certain applications, even getting one more bit can be a challenge, if an application has very little flexibility.
What are the particular challenges of lattice cryptography?
Lattice cryptography has already been standardized as a ready to use solution. For cryptography to be useful, everybody has to use the same system or a small number of agreed upon systems. Standardization is about narrowing things down to a small set of parameters and candidate algorithms so everybody can use and implement the same system. In effect, the cryptographic function implemented and used by your cell phone or computer is the same as the one used by people you contact in other countries. Cryptography exists in a global interconnected world where there are no national boundaries.
This year, Warsaw IACR Summer School focuses on post-quantum cryptography. How this field of study can impact the world?
In terms of impact, due to postquantum security challenges, cryptography is getting more attention today, even from people who don’t have a technical level of understanding. The fact that quantum computers may change the picture is something to worry about.
There is talk about buying a quantum computer in Poland, in Poznań, which will be worth circa $40 million. But let’s turn to deepfakes. While we regularly encounter them on social media, a more interesting issue is deepfake creation during online conferences. For instance, someone could impersonate a chief financial officer at a company and tell an employee to make a money transfer to fraudsters. Recently, IDEAS NCBR researchers from the group of Stefan Dziembowski created a prototypical software that uses zero-knowledge proofs to prove whether one is really talking with a living person through the online camera. Can you share some real world applications where zero-knowledge proofs (ZKPs) are being used today?
Zero-knowledge proofs are a very powerful tool. It’s something that has become more popular outside of the cryptographic research community during the last 10 years, primarily because of its potential applications in the blockchain area.
In encryption, you want to protect your messages. It is a technical notion with a formal definition, and you can consider different type of security for encryption, e.g. encryption which is secure against a passive adversary that can only intercept messages, or security against active adversaries that can intercept and modify messages. In the latter scenario the secret key of the scheme may be leaked and the encryption may become completely insecure. Getting an encryption scheme which is secure against this type of more powerful active adversaries is very important.
In an open communication network like the internet, when you send a message to another computer, your message will go through a large number of intermediate, nodes and routers that are not under your control. The possibility of messages being tampered with and changed is an actual threat. The process of transforming an encryption scheme secure against passive attacks into a stronger encryption scheme that counters these more realistic attacks was first achieved using ZKPs.
Imagine you’re sending a money transfer message to your bank. If the adversary can add one digit to the message, even without knowing the content of the message, then it’s a serious attack. We achieve security against this type of attacks by building an enhanced encryption scheme where we encrypt the message and then give a proof that we know the message. It has to be a zero-knowledge proof (ZKP) – a proof that you know the message, but you want to keep the message secret. Using ZKPs, you can keep the message secret, show that you know the message, and this makes it harder for an adversary to change the message, because if they do it, they cannot prove that they know the message.
The attackers don’t know the message, so they will not be able to change the proof. Now, the first theoretical solutions to this problem were built using explicitly ZKPs. Today on the internet more lightweight and simpler protocols are used, but still what they do is something that can be interpreted as an implicit zero-knowledge proof. Other possible applications of ZKPs are in identification protocols. When you’re connecting to a remote computing system, you want to prove who you are in order to gain access and make sure that other people don’t gain access. This can be done with a password, but password is not zero-knowledge. As the system checks it that’s the correct password, somebody on the receiving side may see your password and impersonate you.
Solutions similar to ZKPs are used in the internet to achieve secure identification. There is some secret that you know, and the system knows that. That’s what identifies you. And you prove the knowledge of the secret using a ZKP system so that even the verifier that checks your identity doesn’t get to learn the secret. They know that you know it, but they don’t get it. ZKPs also open the door to a more refined, anonymous form of proving your identity.
For example, if you’re entering Poland, you may want to prove that you are a citizen with a valid passport or a visitor with a visa, but you could do that without disclosing your individual identity. ZKPs offer a way to prove that your identity has certain properties, without disclosing the specific identity. However, this is not yet done at the level of passport identification, because many countries want to know the identity of people who are arriving. As for the internet, when performing electronic transactions, you may want this type of limited form of authenticity and anonymity. This is one of the reasons why ZKPs has been attracting a lot of attention in the context of blockchain applications. Blockchains are public, so all the transactions can be read by anybody. ZKPs can protect the transactions that are being registered on the blockchain.
Actually, all the systems that don’t use passwords are doing something very similar to zero-knowledge identification. Passwordless authentication has become more popular these days: it’s a solution where you use some hardware token which has a secret key stored on it. The key never leaves the token. It can look like a USB stick, but there is a microprocessor that uses the key which is generated inside. Then the key is used to prove provenance or identity when connecting to remote sites. You can register some public identifier, and then the only way to connect is to possess the device. By using a challenge response protocol it allows you to prove that you are in possession of the object, but without leaving any information that can be used by others to impersonate you. If you look down at exactly how the protocol works, it’s something that could be done using ZKPs, and it is often very similar.
What advice would you give to students and young researchers who would like to pursue a career in cryptography research?
Today, machine learning is getting all the attention. But there is a component of fashion about it. Before LLMs, which boomed in the last few years, blockchain and cryptocurrencies were also very popular. In a sense, machine learning has taken that spot.
Machine learning and AI can be a good source of security problems. The combination of AI and cryptography is very powerful. There are a lot of concerns about attacks on ML systems and misuse of them. For example, systems used in self-driving cars use sensors and cameras to recognize images to avoid hitting the pedestrians, other cars, obstacles etc. Research has shown that you can create an image that to a human looks like an elephant, but the system will say “no, that’s a giraffe.” That’s because the machine learning system is not robust. Once you know how it works, you can do small changes that will trick it into giving you the wrong answer. You could put billboards near the road that would look like perfectly fine ads and cause car accidents. This is where cryptography may play a role.
As for potential cryptography students, I would tell those who have a sense of importance of potential real-world applications, of security in practice, that it’s best to focus on theory and math and the theoretical foundation of computer science. Even if you want a system that works well in practice, theory is more fundamental in cryptography than in other areas of computer science. In case of most applications, you can build a prototype system, then test it, and if it works, you are confident that you did something useful. In case of cryptography, you cannot test security.
You need security against attacks that you can’t predict. The attacker will try to come up with a way to subvert the system after the system has been designed and deployed. You don’t have the opportunity of product development and testing. The only way to design a secure product is to analyze the security in a mathematical way. By now, this is accepted even within the practical, more engineering-oriented community. It was not quite so when I started working in cryptography. “Theory is nice”, people said, “but not quite useful.”
As for students who are attracted to cryptography because they like mathematics, I would tell them to look also at potential applications, because these are the best source of theoretical problems. I do like theory, but I also have an appreciation for applications. From the very beginning, I could really see the connections between those two fields and opportunity to do work that was both theoretically satisfying and had potential practical use.
Can you elaborate on what drew you to the field of cryptography? What was particularly interesting for you?
My work is mostly considered theoretical. When people ask me, what tools do I use as a cryptographer, I reply that it’s primarily paper and pencil. But I also do like to turn cryptographic ideas into actual computer programs. What attracted me to cryptography is exactly this combination.
Cryptography is something that I didn’t know anything about until after I started my PhD at MIT, nearly 30 years ago. At the time, cryptography was much smaller than today. Very few universities had even one cryptographer who was teaching courses because it was important for students to know about it, even though they didn’t want to do research.
Today, there are many more opportunities to get jobs in cryptography. Students should be courageous. If you know for certain that something is going to work, then it’s not research. Research is when you work on something and don’t know what you will get at the end. You have to make a bet and win.
MIT has had a very strong group of cryptographers for a long time. Shafi Goldwasser, Silvio Micali, Ron Rivest are the founders of modern cryptography. There were also visiting scholars such as Adi Shamir and Oded Goldreich. I started taking cryptography courses during the first year of my doctoral studies, just out of curiosity. I thought that cryptography was something interesting to learn about, but without the idea of going into research in this field. I liked it so much and the environment played an important role in drawing me to that area.
