Succinct non-interactive arguments via linear interactive proofs

DOI10.1007/S00145-022-09424-4zbMATH Open1487.94103OpenAlexW3030345336WikidataQ113906158 ScholiaQ113906158MaRDI QIDQ2136170FDOQ2136170

Authors: Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth

Publication date: 10 May 2022

Published in: Journal of Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00145-022-09424-4

Recommendations

Succinct non-interactive arguments via linear interactive proofs
Quasi-optimal SNARGs via linear multi-prover interactive proofs
On succinct arguments and witness encryption from groups
On the size of pairing-based non-interactive arguments
Succinct arguments from multi-prover interactive proofs and their efficiency benefits

zbMATH Keywords

homomorphic encryption zero-knowledge probabilistically-checkable proofs interactive proofs succinct arguments

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Cites Work

Probabilistic encryption
On ideal lattices and learning with errors over rings
Efficient Fully Homomorphic Encryption from (Standard) LWE
On lattices, learning with errors, random linear codes, and cryptography
Combinatorial PCPs with short proofs
Nearly-linear size holographic proofs
Small-Bias Probability Spaces: Efficient Constructions and Applications
Proof verification and the hardness of approximation problems
Locally testable codes and PCPs of almost-linear length
Short PCPs with Polylog Query Complexity
A public key cryptosystem and a signature scheme based on discrete logarithms
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Probabilistic checking of proofs
Title not available (Why is that?)
Interactive proofs and the hardness of approximating cliques
Title not available (Why is that?)
Pairing-Friendly Elliptic Curves of Prime Order
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Sound 3-query PCPPs are long
Minimum disclosure proofs of knowledge
Universal Arguments and their Applications
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Homomorphic encryption: from private-key to public-key
Factoring Polynomials Over Large Finite Fields
Perfect NIZK with Adaptive Soundness
Advances in Cryptology - CRYPTO 2003
Does co-NP have short interactive proofs ?
On interactive proofs with a laconic prover
On the complexity of interactive proofs with bounded communication
The Knowledge Complexity of Interactive Proof Systems
Non-interactive verifiable computing: outsourcing computation to untrusted workers
Improved delegation of computation using fully homomorphic encryption
From secrecy to soundness: efficient verification via secure computation (extended abstract)
A New Algorithm for Factoring Polynomials Over Finite Fields
Factoring polynomials over finite fields: A survey
Pseudorandom bits for polynomials
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Title not available (Why is that?)
Separating succinct non-interactive arguments from all falsifiable assumptions
Hiding information and signatures in trapdoor knapsacks
Deterministic extractors for affine sources over large fields
IP = PSPACE
Extractors and rank extractors for polynomial sources
Practical verified computation with streaming interactive proofs
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
Secure two-party computation with low communication
Short pairing-based non-interactive zero-knowledge arguments
Probabilistically Checkable Arguments
Succinct NP Proofs from an Extractability Assumption
Title not available (Why is that?)
Computationally Sound Proofs
Verifiable delegation of computation over large datasets
Two protocols for delegation of computation
Title not available (Why is that?)
On polynomial systems arising from a Weil descent
Advances in Cryptology – CRYPTO 2004
Title not available (Why is that?)
The PCP theorem by gap amplification
Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
Two-query PCP with subconstant error
Robust PSPs of proximity, shorter PSPs and applications to coding
Quadratic span programs and succinct NIZKs without PCPs
On the concrete efficiency of probabilistically-checkable proofs
Small PCPs with low query complexity
Interactive PCP
Query efficient PCPs with perfect completeness
Witness encryption and its applications
Title not available (Why is that?)
Title not available (Why is that?)
On the size of pairing-based non-interactive arguments
Polylogarithmic two-round argument systems
Automata, Languages and Programming
Targeted malleability: homomorphic encryption for restricted computations
Square span programs with applications to succinct NIZK arguments
Recursive composition and bootstrapping for SNARKs and proof-carrying data
The hunting of the SNARK
Succinct arguments from multi-prover interactive proofs and their efficiency benefits
Linear-time zero-knowledge proofs for arithmetic circuit satisfiability
Towards Plaintext-Aware Public-Key Encryption Without Random Oracles
The power of distributed verifiers in interactive proofs
Transparent SNARKs from DARK compilers
Zero-knowledge proofs on secret-shared data via fully linear PCPs
On succinct arguments and witness encryption from groups

Cited In (7)

Succinct non-interactive arguments via linear interactive proofs
Linear-time arguments with sublinear verification from tensor codes
On the size of pairing-based non-interactive arguments
Quasi-optimal SNARGs via linear multi-prover interactive proofs
Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
Succinct arguments from multi-prover interactive proofs and their efficiency benefits
On succinct arguments and witness encryption from groups

This page was built for publication: Succinct non-interactive arguments via linear interactive proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136170)