SNARGs for Monotone Policy Batch NP

Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, Omer Paneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We construct a succinct non-interactive argument (SNARG ) for the class of monotone policy batch NP languages, under the Learning with Errors (LWE ) assumption. This class is a subclass of NP that is associated with a monotone function f: { 0, 1 }k→ { 0, 1 } and an NP language L, and contains instances (x1, …, xk) such that f(b1, …, bk) = 1 where bj= 1 if and only if xj∈ L. Our SNARG s are arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries. This is the first SNARG under standard hardness assumptions for a sub-class of NP that is not known to have a (computational) non-signaling PCP with parameters compatible with the standard framework for constructing SNARG s dating back to [Kalai-Raz-Rothblum, STOC ’13]. Indeed, our approach necessarily departs from this framework. Our construction combines existing quasi-arguments for NP (based on batch arguments for NP ) with a new type of cryptographic encoding of the instance and a new analysis going from local to global soundness. The main novel ingredient used in our encoding is a predicate-extractable hash (PEHash ) family, which is a primitive that generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our PEHash extracts a global property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II
EditorsHelena Handschuh, Anna Lysyanskaya
PublisherSpringer Science and Business Media Deutschland GmbH
Pages252-283
Number of pages32
ISBN (Print)9783031385445
DOIs
StatePublished - 2023
Externally publishedYes
EventAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings - Santa Barbara, United States
Duration: Aug 20 2023Aug 24 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14082 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAdvances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings
Country/TerritoryUnited States
CitySanta Barbara
Period8/20/238/24/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'SNARGs for Monotone Policy Batch NP'. Together they form a unique fingerprint.

Cite this