Concretely-Efficient Zero-Knowledge Arguments for Arithmetic Circuits and Their Application

Explore a conference talk on zero-knowledge arguments for arithmetic circuits and their applications, presented at PKC 2020. Delve into the paper by Carsten Baum and Ariel Nof, which covers topics such as MPC-in-the-head techniques, pre-processing in MPC, and the SIS problem. Learn about circuit sampling on the fly, bit test amortization, and implementation results. Gain insights into concrete efficiency improvements for zero-knowledge proofs and their potential applications in cryptography.

Syllabus

Intro
Our Results
MPC (in-the-Head) with Pre-Processing
Pre-processing in MPC
MPC-in-the-head: 1st approach [KKW18]
MPC-in-the-head: 2nd approach Ours
Comparing the two approaches
Application: The SiS problem
The Binary SIS problem
Can we do better?
Circuit Sampling on the Fly
Example: Amortize bit tests
Implementation & Experimental Results
Conclusions