Cryptographic Proofs: Succinctness and Zero-Knowledge

Non-interactive proof systems allow a prover to convince a verifier that a statement is true in a single message. These systems can achieve two magical features: succinctness, meaning the proof can be very short for any complicated statement, and zero-knowledge, meaning the proof can hide why a statement is true. 

Non-interactive proof systems are a fundamental concept that has been studied since the 1980s. They have a fruitful interaction with complexity theory. These proof systems also have wide applications in cryptography and applied security, including cloud computing security, privacy-preserving machine learning, and blockchain.

In this talk, I will present my work on the following fundamental questions for non-interactive proof systems whose answers have remained elusive for decades:

1. How to achieve succinctness? My work has built the first succinct non-interactive proof systems for any deterministic computation based on a well-studied assumption in lattices. All previous works can only provide heuristics for security. A major open question in this field is how to build succinct non-interactive proof systems for all non-deterministic computation (NP). Towards this, my work has built succinct non-interactive proof systems for some subclasses of NP.

2. What assumptions are sufficient to achieve zero-knowledge? Previously, the Diffie-Hellman assumption was the oldest assumption in modern cryptography. It was initially used to achieve public key cryptography, but how to use Diffie-Hellman assumption to construct NIZKs has remained open for more than three decades. My work built the first NIZKs from the sub-exponential hardness of Decisional Diffie-Hellman.

My work has led to a series of works on other important topics in cryptography and complexity, including new program obfuscation schemes, new private information retrieval schemes, and implications in game theory. 

Bio:  Zhengzhong Jin is currently a postdoctoral associate at MIT, supervised by Vinod Vaikuntanathan. His research interests are cryptography and related topics in theoretical computer science, with a focus on the foundations of cryptographic proof systems. His work has been recognized with the Best Paper Award at EUROCRYPT 2021.