Disruptive Cryptography: Post-Quantum & Machine Learning With Encrypted Data

by Internet Summit Team

Photo by Cloudflare Staff

Shay Gueron, Associate Professor of Mathematics, University of Haifa, Israel, and Raluca Ada Popa, Assistant Professor of Computer Science, UC Berkeley

Moderator: John Graham-Cumming, CTO, Cloudflare


Raluca is also a Co-Director of the RISELab at UC Berkeley as well as Co-Founder and CTO of a cybersecurity startup called PreVeil. She developed practical systems that protect data confidentiality by computing over encrypted data as well as designed new encryption schemes that underlie these systems.

Shay was previously a Senior Principal Engineer, serving as Intel’s Senior Cryptographer and is now senior principal at AWS, and an expert in post-quantum, security, and algorithms.

JGC: Tell us about what you actually do.

RP: Computing on encrypted data is not just theoretical; it’s also exciting because you can keep data encrypted in the cloud. It covers hacking attacks while still enabling the functionality of the system. This is exciting because we can cover so many hacking attacks in one shot.

SG: I’m working on making new algorithms; also on making solutions for quantum computers that are increasingly strong.

SG: I’ve been working on cryptography: making it faster, recently I’ve been thinking about solutions for what will happen when we have a quantum computer strong enough to threaten the known methods for cryptography.

JGC: Why are we worrying ahead of time?

SG: Protocols and implementations have been improved; performance on processors allows for most things to be encrypted. We are entering a stable situation. But right now, there is a new threat where there may be quantum computers that can solve difficult problems. This means that we need to start thinking about a replacement to the current cryptography.

RP: If someone is saving encrypted communications now, they could decrypt past conversations that could still be relevant in the future.

JGC: We don’t have the quantum computer yet but we already have the programs that will run on it.

SG: Cryptography is based on a belief in “reduction of a difficult problem.” All cryptography is based on a belief that something is difficult to do; based on this there are theoretical works that run “if… then”; but there is no robust proof that factorization is difficult, or that solving a particular problem is hard. We are just not smart enough yet.

JGC: Talk about this concept that there are classes of problems that are hard.

RP: There are classes of problems. There are many studies that people used to boost their confidence about specific algorithms.

JGC: Why can’t we just make keys bigger to deal with quantum threat?

SG: We have to be practical in some sense. The amount of traffic that occurs prior to encrypting data is significant. This causes computational burdens.

RP: Shor’s algorithm is particularly effective; it can break certain properties of RSA. This is not the same for symmetrical cryptography, where increasing the key is more hopeful.

JGC: So what are we going to fix today?

SG: When you establish communications, first we agree on crypto-ciphers. The symmetric key will be used for encryption based on algorithm and signatures. Signatures are more urgent. For the symmetric key encryption, we can start today, because the quantum algorithms can’t reverse the key.

JGC: Give us an idea of what kinds of things you can do without decrypting something?

RP: In theory, you can compute any function without decrypting. We can do specialized computations effectively and machine learning on encrypted data.

For instance: How can you do summation of encrypted data? You get encryption of the sum. It’s not difficult to do an encryption summation. There are practical examples: startups, doc sharing in email; there are many solutions for classes of computation that apply to products we are using today.

So there are services for all sorts of classes of computation out there.

SG: But some of those encryption systems also depend on difficulty of factorization.

JGC: How fast will it be before companies become “post-quantum certified’?

RP: For certain classes of computation it is happening quickly, but there are still many factors making that difficult. For specialized classes of computations, it should happen in the near future … hopefully within the next 5 years. Why? Because encrypted computation brings new functionality. I.e. sharing encrypted data across hospitals to measure effectiveness of cancer treatments and enable new studies.

Encrypted computation brings you new functionality. A lot of businesses can’t share data: for instance, medical companies — which means they cannot help their patients as effectively, so we’ll be able to do many more studies when we can enable this encrypted computation.

SG: There is a call for proposals by NIST for quantum-resistant algorithms. They estimate that this will be a 5-year process. Industry will have to start integrating; the safe way would be to do both: If you want to do a key exchange, you do the classical and the quantum resistant one.

JGC: How long before we create a quantum computer?

SG: The question is how long it will take before they are strong enough… this will take some time. But there is a lot of motivation.

Quantum computing is not designed to break cryptography, but to go some good. Many industries and governments are trying to do this right now. It’s a race against the human mind.

JGC: One of the arguments against new cryptography is that it is slow. Are there costs?

RP: Certainly; what’s sped up encryption are hardware implementations. There are already startups trying to build specialized hardware for advanced encryption.

RP: For the masses to enjoy acceleration, you would need quantum computers for the masses. To speed up usage, you need quantum computers for the masses.

JGC: If there are quantum computers for the masses, what will I get?

SG: You can get better AI, faster searches.

JGC: Tell us about quantum encryption vs. quantum computing: for instance, the Chinese sending data between two satellites

RP: You’d need a lot of quantum computers, but to break it you’d just need a few. 
 A widespread adoption of quantum encryption is going to be much slower.

Q&A: What is lattice-based cryptography?

Why do the two of your domains intersect?

RP: Lattices are much more expressive in terms of the computations they can do. Lattices are more resilient to quantum attackers and classical algorithms.

SG: We have no idea how to solve lattice problems, even if we had quantum computers. New cryptography is trying to solve these issues.

This is why the new cryptography is trying to build on these problems in the hopes we can come up with an algorithm.

A quantum computer is not going to allow you to do a million computations.

JGC: What would you like the audience to take away from this session?

RP: Mainly, encrypted computation is practical. There are actually practical solutions; it can enable new functionalities. Secondly, you can enable interesting studies (medical, financial) with encrypted computation.

SG: People shouldn’t worry about quantum-resistant encryption. We’re working on it.

So it can enable new functionalities for you.

Q&A:

Q: What advice for people who want to make cheap, future-proof “internet of things” devices?

SG: There is a set of algorithms that are known to be secure against quantum attacks. These are hash-based signatures. These are slow, but practical solutions. But in general, I’d like to say: Don’t lose any sleep over the threat of quantum computers; it will happen gradually. There is still time to prepare.

RP: I agree; but do start thinking about it. First get Internet of Things right; then worry about the quantum part.

Q: What are some primitives that are missing in programming language that allow you to build easily? How to balance security with programming?

RP: We have some libraries; there are some.

Q: What do you think of the quantum resistant crypto put into the Chrome browser’s TLS stack? Will secrets stand up to a quantum computer?

SG: This experiment was already performed by Google, They wanted to test what would happen to the overhead. This particular algorithm was just an exercise to see what would happen in reality, if you do both classical and quantum-safe key exchange. Conclusion: yes, we can handle it.


Originally published at blog.cloudflare.com on September 14, 2017.