Marching Toward More Efficient Proof Systems: A Chat with Justin Holmgren

By NTT Research Staff

Dr. Justin Holmgren joined NTT Research as a scientist in the Cryptography & Information Security (CIS) Lab in May 2020. He was previously a Google Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley and as a Postdoctoral Research Fellow at Princeton University. He studied mathematics and computer science at the Massachusetts Institute of Technology (MIT), where he obtained a Ph.D. in Computer Science in 2018.

Dr. Holmgren studies the foundational theory of cryptography and its interplay with diverse areas of computer science. But much of his focus is on proof systems. His work has advanced the feasibility of securely outsourcing computation, private information retrieval and software watermarking. He is especially keen to reduce the amount of interaction in proof systems and thereby increase their efficiency and practical value. Please read on to learn more about his background and research agenda:

You originally studied mathematics and computer science. What made you decide to focus on the latter field of study?

Actually, as a theorist, I think I manage to do both. My work is to design cryptographic tools and protocols (that could be implemented on a computer), but most of my work is applying rigorous mathematical analysis to these protocols.

Some of us heard Shafi Goldwasser for the first time in her keynote on trustworthy machine learning in the NTT Research virtual conference. What was it like being advised by her at MIT?

It was fantastic; not only was she an inspirational fountain of creativity, but she also gave me the freedom and encouragement to pursue my own research directions.

It sounds like your work involves program obfuscation and homomorphic encryption, among other topics. What are your current areas of research?

Lately, one other thing I’ve been working on, which is a bit technical, is how to reduce interaction from proof systems, which are protocols in which a “prover” convinces an untrusting “verifier.” A highly interactive proof system might have the verifier repeatedly interrogating the prover over the course of many rounds of questioning. Some of my recent research has focused on transforming such a protocol into a better protocol, in which the prover is “fire and forget.” That is, the prover just sends a single convincing message, and doesn’t have to stick around to answer follow-up questions. This turns out to be quite difficult and it is intimately related to secure hash functions, which are some of the most fundamental objects in cryptography, but that’s just part of what makes the research fun.

Does the recent article by Jain, Lin and Sahai on Indistinguishability Obfuscation, relate to your field of study? Any comments?

Yes, over the last five years indistinguishability obfuscation has proven to be a tremendously useful tool with all kinds of cryptographic applications. I’ve used it in my previous work and will likely continue to use it in my future work. Until now though, we didn’t really know whether indistinguishability obfuscation was possible. It was a hypothetical object with a lot of heuristic proposals on how it might be constructed, but we didn’t have any good reason to believe that any of the proposals worked (and in fact many of the proposals were broken). In this seminal work, Jain et al. have for the first time proposed a *provable* construction under very reasonable assumptions.

You mention the outsourcing of personal data and professional data (such as an engineering simulation to a super-computer) in the short NTT Research video about your work. Is increasing the level of trust in these kinds of apps and digital workflows a big motivation for your work?

That’s one motivation, but I’m more excited about the new workflows that might only be possible with cryptography. Shafi mentioned in her talk how cryptography fundamentally enabled e-commerce (where trust is very important), first in regular encrypted credit card transactions, and then again with the rise of cryptocurrencies. I think that proof systems, if they become efficient enough, could lead to a similar breakthrough.

What has been your experience been like so far at NTT Research?

I’m still mostly working from home because of the pandemic, but I’m excited about the great team that NTT Research has put together, and I really appreciate how NTT Research is giving me the freedom to focus on basic research with long-term applications.