Crypto Seminar - Surya Mathialagan

— 5:30pm

Location:
In Person and Virtual - ET - Blelloch-Skees Conference Room and Zoom

Speaker:
SURYA MATHIALAGAN , Ph.D. Student, Theory Group, Electrical Engineering & Computer Science Department, Massachusetts Institute of Technology
https://suryamathialagan.com/

Universal SNARGs for NP from Proofs of Completeness

In this work, we give new constructions of succinct non-interactive arguments SNARGs for NP in the settings of both non-adaptive and adaptive soundness. First, we construct a succinct non-interactive argument system (SNARG) for any NP language L, and prove the non-adaptive soundness assuming the security of an FHE scheme, a batch argument (BARG) scheme, as well as the existence of any two-message argument system for L where the prover’s message is succinct, and the completeness property has a polynomial-size Extended Frege proof. Our SNARG is universal in the sense that the construction does not depend on the two-message argument system. The set-up of our SNARG scheme is transparent (i.e. no private randomness). Beyond universality, we note that weaker primitives such as designated verifier SNARGs, and witness encryption both imply such 2-message arguments. Such an amplification of these primitives was not known before. 

In the adaptive setting, we also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness. 

Our framework yields several corollaries, including:

  • a SNARG for NP with a transparent CRS and non-adaptive soundness, assuming LWE and the (non-explicit) existence of any witness encryption for NP that has a polynomial-size 'Extended Frege proof of correctness'. As a corollary, we obtain SNARGs for NP under the evasive LWE and subexponential LWE assumptions, with a (long) transparent CRS and non-adaptive soundness.
  • a SNARG for UP (NP language with unique witnesses) with a long (and even transparent!) CRS and adaptive soundness under the evasive LWE and subexponential LWE assumptions.
  • a SNARG for NP with a short CRS and non-adaptive soundness assuming LWE, FHE, and the (non-explicit) existence of any hash function that makes Micali's SNARG construction sound.

We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a “best possible SNARG''. 

Based on the joint work with Zhengzhong Jin, Yael Tauman Kalai, and Alex Lombardi.

In Person and Zoom Participation.  See announcement.

Based on the joint work with Zhengzhong Jin, Yael Tauman Kalai, and Alex Lombardi.

Event Website:
https://sites.google.com/view/crypto-seminar/home

Add event to Google
Add event to iCal