Dr. Sanjam Garg: Foundations, Constructions and Applications

In May 2021, Dr. Sanjam Garg joined NTT Research as a Senior Scientist in the Cryptography & Information Security (CIS) Lab. Dr. Garg was most recently Associate Professor in the department of Electrical Engineering and Computer Science at the University of California, Berkeley. Dr. Garg received his Ph.D. from the University of California, Los Angeles, in 2013 and his B.Tech in Computer Science and Engineering from the Indian Institute of Technology, Delhi, India. His research has been recognized with best paper awards at Eurocrypt 2013, Crypto 2017 and Eurocrypt 2018. Five of his co-authored papers have been recognized as journal-invited papers, including “Candidate iO [indistinguishability obfuscation] from Homomorphic Encryption Schemes,” at Eurocrypt 2020.Dr. Garg is the author or co-author of more than 160 papers. In addition to iO and homomorphic encryption, recently addressed topics include multiparty computing (MPC), functional encryption, the ‘right to be forgotten,’ identity-based encryption (IBE), non-interactive zero-knowledge (NIZK) proofs and learning with errors (LWE) encryption. A newly posted NTT Research video further introduces Dr. Garg, who points to a widespread loss of control over data and how some of the advanced cryptography techniques that NTT Research is developing will be “central in bringing the control back in the hands of the consumer.” For more about Dr. Garg’s background and ongoing research, please read the following Q&A:

Which areas of research are you most interested in pursuing going forward?

My research interests span from foundations of cryptography to new applications. On the front of foundations, a key focus of my research is the realization of far-reaching cryptographic primitives while also minimizing the computational hardness assumptions used for realizing them. For example, my prior works have made progress in answering questions such as: Can we realize a method to obfuscate computer programs without revealing how they work? Can such obfuscation methods be made secure against quantum computers? Can encryption be performed using a recipient’s identity relying on well-established assumptions that form the basis of modern public-key encryption? How much further can we go in realizing far-reaching cryptographic applications from such age-old assumptions?

I am also interested in the design of new cryptographic constructions that support demanding application settings. For example, I have been working to realize the following vision: Alice would like to squish and encrypt her life’s confidential data into a few bits that she can share with the world on her website. Next, Bob has a private program that he wants Alice to compute on her data while communicating only a few bits to Alice. I have been working on this emerging paradigm of laconic cryptography that enables realizing cryptographic tasks with virtually minimal communication costs.

Does your recent paper for Crypto 2021 on “Compact Ring Signatures from Learning with Errors” fall more toward the foundational or application ends of the spectrum? Could you share what you were aiming to achieve with that paper?

Ring signatures allow a user to sign a message on behalf of a “ring” of signers, while hiding the true identity of the signer, with natural applications related to whistleblowing, authenticating leaked information and more recently to cryptocurrencies.

Are there any other recent or forthcoming publications that you’d like to mention?

Over this summer, I along with my NTT summer intern Alex Bienstock and our collaborators, Jaiden Fairoze, Pratyay Mukherjee and Srinivasan Raghuraman, have been working on precisely defining the security of the Signal protocol which forms the backbone of the many modern secure messaging platforms, such as the Signal application itself, Facebook Messenger, WhatsApp, etc. The core of Signal – the Double Ratchet protocol ­– has enjoyed a recent line of analyses which attempt to formally define its security. However, we show that these analyses overlook non-trivial aspects of the protocol’s security and suggest modifications to the protocol for better security.

You were co-supervised in your dissertation at UCLA by Professor Rafail Ostrovsky and Professor Amit Sahai. How would you say they influenced your thinking and approach to cryptography, and have you continued to collaborate since then?

Rafi and Amit have very different styles of research, and this served as an ideal learning experience for me. I learnt a lot from both, but certain aspects of our interactions stood out. Rafi has worked on a huge range of topics. His breadth of knowledge has helped me build a better perspective about finding important research problems. On the other hand, Amit’s clarity of expression stood out in my conversations with him. He has a knack for stating vague ideas more concretely; something that I have tried to imbibe in myself.

After my graduation, I have had the opportunity to work closely with Rafi on the notions of garbled RAM and other aspects of efficient secure computation. Also, since my graduation, I have been fortunate to collaborate with Amit on several projects aimed at basing program obfuscation on solid mathematical foundations.

As a relatively new member of the CIS Lab, how do you see your interests and research goals aligning or overlapping with the overall team?

Cryptographers in the CIS Lab have an established record of working on foundational problems in cryptography and my own research is closely aligned with that goal.

In the past, I have been fortunate to have opportunities to collaborate with CIS Lab members: (i) Vipul Goyal and Susumu Kiyoshima on constructing secure computation protocols that remain secure in sophisticated application scenarios, with (ii) Brent Waters and Mark Zhandy on new constructions of indistinguishability obfuscation and functional encryption schemes and with (iii) Daniel Wichs on foundations of cryptography. I look forward to further strengthening these collaborations.