{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/144943"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/144943","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Rate-1 non-interactive arguments for batch-NP","abstract":"Succinct non-interactive arguments for batch-NP computations, called BARGs (Choudhuri, Jain and Jin, STOC 2021), have emerged as a powerful tool to construct succinct non-interactive arguments (SNARGs) for expressive classes of computations such as all deterministic computations (P), time-space bounded non-deterministic computations (NTISP), and so on. A BARG gives us a way to prove k NP statements where the size of the proof (resp. the verification time) is proportional to the size of a single witness (resp. the time for a single NP verification). We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-NP (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of k NP statements each with an m-bit witness, has size m + poly(λ). In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m · poly(λ) (Kalai, Paneth, and Yang, STOC 2019, and Choudhuri, Jain, and Jin, STOC 2021). The soundness of our construction relies on the learning with errors (LWE) assumption. We also observe we can obtain an incrementally verifiable computation (IVC) scheme for arbitrary deterministic computations, even beyond P; a multi-hop BARG scheme for NP; and a multi-hop aggregate signature scheme, in the standard model, with unbounded and universal aggregation. Prior to this work, IVC schemes were only known for P under a bilinear map assumption, and beyond P only under non-standard knowledge assumptions or in the random oracle model; multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; and aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model.","abstract_html":"Succinct non-interactive arguments for batch-NP computations, called BARGs (Choudhuri, Jain and Jin, STOC 2021), have emerged as a powerful tool to construct succinct non-interactive arguments (SNARGs) for expressive classes of computations such as all deterministic computations (P), time-space bounded non-deterministic computations (NTISP), and so on. A BARG gives us a way to prove k NP statements where the size of the proof (resp. the verification time) is proportional to the size of a single witness (resp. the time for a single NP verification). We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-NP (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of k NP statements each with an m-bit witness, has size m + poly(λ). In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m · poly(λ) (Kalai, Paneth, and Yang, STOC 2019, and Choudhuri, Jain, and Jin, STOC 2021). The soundness of our construction relies on the learning with errors (LWE) assumption. We also observe we can obtain an incrementally verifiable computation (IVC) scheme for arbitrary deterministic computations, even beyond P; a multi-hop BARG scheme for NP; and a multi-hop aggregate signature scheme, in the standard model, with unbounded and universal aggregation. Prior to this work, IVC schemes were only known for P under a bilinear map assumption, and beyond P only under non-standard knowledge assumptions or in the random oracle model; multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; and aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model.","abstract_has_math":false,"creators":["Devadas, Lalita"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Vaikuntanathan, Vinod","Kalai, Yael Tauman"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:22:10Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/144943","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Vaikuntanathan, Vinod","Kalai, Yael Tauman"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Devadas, Lalita"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-29T16:22:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-29T16:22:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-05"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Science in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/144943"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Succinct non-interactive arguments for batch-NP computations, called BARGs (Choudhuri, Jain and Jin, STOC 2021), have emerged as a powerful tool to construct succinct non-interactive arguments (SNARGs) for expressive classes of computations such as all deterministic computations (P), time-space bounded non-deterministic computations (NTISP), and so on. A BARG gives us a way to prove k NP statements where the size of the proof (resp. the verification time) is proportional to the size of a single witness (resp. the time for a single NP verification). We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-NP (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of k NP statements each with an m-bit witness, has size m + poly(λ). In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m · poly(λ) (Kalai, Paneth, and Yang, STOC 2019, and Choudhuri, Jain, and Jin, STOC 2021). The soundness of our construction relies on the learning with errors (LWE) assumption. We also observe we can obtain an incrementally verifiable computation (IVC) scheme for arbitrary deterministic computations, even beyond P; a multi-hop BARG scheme for NP; and a multi-hop aggregate signature scheme, in the standard model, with unbounded and universal aggregation. Prior to this work, IVC schemes were only known for P under a bilinear map assumption, and beyond P only under non-standard knowledge assumptions or in the random oracle model; multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; and aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Rate-1 non-interactive arguments for batch-NP"]}]}],"canonical_facts":{"dc:contributor.advisor":["Vaikuntanathan, Vinod","Kalai, Yael Tauman"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Devadas, Lalita"],"dc:date.accessioned":["2022-08-29T16:22:36Z"],"dc:date.available":["2022-08-29T16:22:36Z"],"dc:date.issued":["2022-05"],"dc:description.abstract":["Succinct non-interactive arguments for batch-NP computations, called BARGs (Choudhuri, Jain and Jin, STOC 2021), have emerged as a powerful tool to construct succinct non-interactive arguments (SNARGs) for expressive classes of computations such as all deterministic computations (P), time-space bounded non-deterministic computations (NTISP), and so on. A BARG gives us a way to prove k NP statements where the size of the proof (resp. the verification time) is proportional to the size of a single witness (resp. the time for a single NP verification). We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-NP (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of k NP statements each with an m-bit witness, has size m + poly(λ). In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m · poly(λ) (Kalai, Paneth, and Yang, STOC 2019, and Choudhuri, Jain, and Jin, STOC 2021). The soundness of our construction relies on the learning with errors (LWE) assumption. We also observe we can obtain an incrementally verifiable computation (IVC) scheme for arbitrary deterministic computations, even beyond P; a multi-hop BARG scheme for NP; and a multi-hop aggregate signature scheme, in the standard model, with unbounded and universal aggregation. Prior to this work, IVC schemes were only known for P under a bilinear map assumption, and beyond P only under non-standard knowledge assumptions or in the random oracle model; multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; and aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model."],"dc:description.degree":["S.M."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/144943"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Rate-1 non-interactive arguments for batch-NP"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Science in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:10Z"}