Compact NIZKs from Standard Assumptions on Bilinear Maps

Explore a 25-minute conference talk presented at Eurocrypt 2020 on compact Non-Interactive Zero-Knowledge proofs (NIZKs) based on standard assumptions for bilinear maps. Delve into the paper by Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa, which introduces novel techniques for constructing efficient NIZKs. Learn about the Common Reference String (CRS) model, the motivation behind compact NIZKs, and the current state-of-the-art in CRS-NIZK for NP-complete problems. Understand the high-level ideas, including constrained signatures, their security properties, and the authors' new compact constrained signature scheme. Follow the progression from initial attempts to the final idea of decomposable online-offline efficient constructions. Gain insights into the efficiency and additional results of this compact NIZK approach, concluding with a comprehensive summary of the presented research.

Intro
(CRS)Non-Interactive Zero Knowledge
Motivation
State-of-the-arts (CRS-NIZK for NP)
High Level Idea
Constrained Signature (CS)
Security
Our New Compact Constrained SIG
First Attempt
Analysis of Second Attempt
Our idea (online-offline efficient C5)
Final idea (decomposable online offline eff.)
Our compact NIZK
Note on Efficiency
Additional Results
Summary