At Upgrade 2021, NTT Scientist Dr. Justin Holmgren presented recent work on transparent interactive arguments.

In these systems, a Prover and a Verifier work together to prove an NP claim made by the Prover.  The Verifier is always honest but has bounded computational power. The Prover may be dishonest (it may attempt to get the Verifier to accept an incorrect claim), but also has bounded computational power. Their communications are limited in size, so the Prover cannot afford to prove its claim directly by sending an NP witness. The aim is for the Verifier to pose a series of challenges to the Prover that with high probability a Prover can only answer if its claim is true; this enables the Verifier to accept all correct claims but reject incorrect claims except with negligible probability.

In his talk, Dr. Holmgren presented joint work with Alex Block (Purdue University), Alon Rosen (IDC Herzliya), Ron Rothblum (Technion) and Pratik Soni (CMU). Building on the 2020 paper B. Bünz, B. Fisch and A. Szepeniec, Transparent SNARKS from DARK Compilers (BFS), Holmgren’s team developed an interactive proof system with a combination of desirable properties not achieved together in any previous system.

Their system is transparent, meaning all randomness used by the Verifier, including during setup, is assumed to be known to the (possibly malicious) Prover.  This transparency is important in blockchain applications. The only assumptions needed are well-studied and falsifiable cryptographic assumptions related to the hardness of factoring. Finally, the time and space required for the interactive proof are nearly optimal; they are comparable to what is required to verify an NP witness for the claim without a Prover.

Dr. Holmgren gave a substantial technical overview of the new technique. This involved a non-trivial fix of a bug found in BFS and a close analysis of the messages exchanged between the Prover and the Verifier to reduce the time and space required, using new batching techniques. The hash functions involved are the “doubly homomorphic” hash functions of BFS, and the only cryptographic assumptions required by the method are those needed for the existence of such functions.

Click below for the full transcript.