Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract

No abstract is available for this paper.

• Publication year

  2013

• Venue

  Information Technology Convergence and Services

• Publication date

  2013-01-09

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/2422436.2422481
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multi-prover interactive proofs: how to remove intractability assumptions

  2019cited by this paper
• On the Complexity of the Satisfiability Problem

  2015cited by this paper
• Fully Homomorphic Encryption without bootstrapping

  2015cited by this paper
• (Leveled) Fully Homomorphic Encryption without Bootstrapping

  2014cited by this paper
• Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems (full version)

  2013cited by this paper
• Recursive composition and bootstrapping for SNARKS and proof-carrying data

  2013influential reference
• Fully Homomorphic Message Authenticators

  2013cited by this paper
• Quadratic Span Programs and Succinct NIZKs without PCPs

  2013cited by this paper
• Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits

  2012influential reference
• On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

  2012influential reference
• Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments

  2012cited by this paper
• Secure Two-Party Computation with Low Communication

  2012cited by this paper
• Compilation Techniques for Efficient Encrypted Computation

  2012cited by this paper
• Fully Homomorphic Encryption with Polylog Overhead

  2012cited by this paper
• From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again

  2012cited by this paper
• Better Bootstrapping in Fully Homomorphic Encryption

  2012cited by this paper
• Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits

  2011cited by this paper
• Implementing Gentry's Fully-Homomorphic Encryption Scheme

  2011cited by this paper
• Verifying Computations with Streaming Interactive Proofs

  2011cited by this paper
• Memory Delegation

  2011cited by this paper
• Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs

  2011cited by this paper
• Practical verified computation with streaming interactive proofs

  2011cited by this paper
• Two 1-Round Protocols for Delegation of Computation

  2011cited by this paper
• Short Non-interactive Zero-Knowledge Proofs

  2010cited by this paper
• Short Pairing-Based Non-interactive Zero-Knowledge Arguments

  2010cited by this paper
• Improved Delegation of Computation using Fully Homomorphic Encryption

  2010cited by this paper
• Proof-Carrying Data and Hearsay Arguments from Signature Cards

  2010cited by this paper
• Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

  2010cited by this paper
• From Secrecy to Soundness: Efficient Verification via Secure Computation

  2010cited by this paper
• Fully homomorphic encryption using ideal lattices

  2009cited by this paper
• Linear Algebra with Sub-linear Zero-Knowledge Arguments

  2009cited by this paper
• The universal automaton

  2008cited by this paper
• Delegating computation: interactive proofs for muggles

  2008cited by this paper
• Short PCPs with Polylog Query Complexity

  2008influential reference
• Succinct NP Proofs from an Extractability Assumption

  2008cited by this paper
• Perfect NIZK with Adaptive Soundness

  2007cited by this paper
• Non-interactive Zaps and New Techniques for NIZK

  2006cited by this paper
• On Round-Efficient Argument Systems

  2005cited by this paper
• I Computational Complexity

  2005cited by this paper
• Short PCPs verifiable in polylogarithmic time

  2005cited by this paper
• Implementing Probabilistically Checkable Proofs of Proximity

  2005cited by this paper
• Robust pcps of proximity and shorter pcps

  2004cited by this paper
• Robust pcps of proximity, shorter pcps and applications to coding

  2004cited by this paper
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

  2003cited by this paper
• The KR-Benes network: a control-optimal rearrangeable permutation network

  2003cited by this paper
• Locally testable codes and PCPs of almost-linear length

  2002cited by this paper
• Universal arguments and their applications

  2002influential reference
• Modern computer algebra

  2002cited by this paper
• On interactive proofs with a laconic prover

  2001cited by this paper
• Computationally Sound Proofs

  2000cited by this paper
• Small PCPs with low query complexity

  2000cited by this paper
• Efficient computation of minimal polynomials in algebraic extensions of finite fields

  1999cited by this paper
• On the Complexity of Interactive Proofs with Bounded Communication

  1998cited by this paper
• Software protection and simulation on oblivious RAMs

  1996cited by this paper
• On Finding Primitive Roots in Finite Fields

  1996cited by this paper
• Arithmetic and factorization of polynomials over F_2

  1996cited by this paper
• Computationally efficient error-correcting codes and holographic proofs

  1995cited by this paper
• Quasilinear Time Complexity Theory

  1994cited by this paper
• Nearly-linear size holographic proofs

  1994influential reference
• Synthesis of Parallel Algorithms

  1993cited by this paper
• Constant time factors do matter

  1993cited by this paper
• The Complexity of Computation on the Parallel Random Access Machine

  1993cited by this paper
• Deterministic Simulation of a Single Tape Turing Machine by a Random Access Machine in Sub-linear Time

  1992cited by this paper
• A note on efficient zero-knowledge proofs and arguments (extended abstract)

  1992cited by this paper
• Optimal On-Line Simulations of Tree Machines by Random Access Machines

  1992cited by this paper
• Checking the correctness of memories

  1991cited by this paper
• An O (T log T) Reduction from RAM Computations to Satisfiability

  1991influential reference
• Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes

  1991cited by this paper
• Checking computations in polylogarithmic time

  1991influential reference
• One-way functions are necessary and sufficient for secure signatures

  1990cited by this paper
• A Certified Digital Signature

  1989cited by this paper
• Nearly Linear Time

  1989cited by this paper
• Universal one-way hash functions and their cryptographic applications

  1989cited by this paper
• Fast Simulation of Turing Machines by Random Access Machines

  1988cited by this paper
• The ultimate RISC

  1988cited by this paper
• New algorithms for finding irreducible polynomials over finite fields

  1988cited by this paper
• Random instances of a graph coloring problem are hard

  1988cited by this paper
• Minimum Disclosure Proofs of Knowledge

  1988cited by this paper
• Does co-NP Have Short Interactive Proofs?

  1987cited by this paper
• Fast Probabilistic RAM Simulation of Single Tape Turing Machine Computations

  1986cited by this paper
• Speedups of deterministic machines by synchronous parallel machines

  1983cited by this paper
• Fast Fourier Transform Algorithms with Applications

  1983influential reference
• An 0(n log n) sorting network

  1983cited by this paper
• private communication

  1983cited by this paper
• Finite fields

  1983cited by this paper
• Parallel Algorithms to Set Up the Benes Permutation Network

  1982cited by this paper
• Relations Among Complexity Measures

  1979influential reference
• Storage Modification Machines

  1979cited by this paper
• On time versus space II

  1979cited by this paper
• Satisfiability Is Quasilinear Complete in NQL

  1978cited by this paper
• Generalized Connection Networks for Parallel Processor Intercommunication

  1978cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• On Time Versus Space

  1977cited by this paper
• The Complexity Theory of Switching Networks.

  1973cited by this paper
• Rechner-Architektur / Computer Architecture

  1972cited by this paper
• Time-bounded random access machines

  1972cited by this paper
• On a class of rearrangeable switching networks part I: Control algorithm

  1971cited by this paper
• A Permutation Network

  1968cited by this paper
• Mathematical Theory of Connecting Networks and Telephone Traffic.

  1966cited by this paper
• On the Definition of an Algorithm

  1963cited by this paper

• Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs

  2025cites this paper
• CoBBL: Dynamic Constraint Generation for SNARKs

  2025cites this paper
• Linear-Time Polynomial Holographic Interactive Oracle Proofs with Logarithmic-Time Verification for Rank-1 Constraint System from Lookup Protocol

  2025cites this paper
• SNARKs for Stateful Computations on Authenticated Data

  2025cites this paper
• Volatile and Persistent Memory for zkSNARKs via Algebraic Interactive Proofs

  2025cites this paper
• A survey of folding-based zero-knowledge proofs

  2025cites this paper
• On Soundness Notions for Interactive Oracle Proofs

  2024cites this paper
• zkPi: Proving Lean Theorems in Zero-Knowledge

  2024cites this paper
• Hekaton: Horizontally-Scalable zkSNARKs Via Proof Aggregation

  2024cites this paper
• Dora: A Simple Approach to Zero-Knowledge for RAM Programs

  2024cites this paper
• Less is more: refinement proofs for probabilistic proofs

  2023cites this paper
• Efficient Proofs of Software Exploitability for Real-world Processors

  2023cites this paper
• Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS

  2023cites this paper
• Jolt: SNARKs for Virtual Machines via Lookups

  2023cites this paper
• Rinocchio: SNARKs for Ring Arithmetic

  2023cites this paper
• Dora: Processor Expressiveness is (Nearly) Free in Zero-Knowledge for RAM Programs

  2023cites this paper
• Polynomial IOPs for Memory Consistency Checks in Zero-Knowledge Virtual Machines

  2023cites this paper
• Interactive Proofs for Rounding Arithmetic

  2022cites this paper
• SuperNova: Proving universal machine executions without universal circuits

  2022cites this paper
• On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives

  2022influential citation
• Multivariate lookups based on logarithmic derivatives

  2022cites this paper
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs

  2022cites this paper
• Efficient Oblivious Permutation via the Waksman Network

  2022cites this paper
• Honest Majority Multi-Prover Interactive Arguments

  2022cites this paper
• Proofs for Inner Pairing Products and Applications

  2021cites this paper
• Linear-Time Oblivious Permutations for SPDZ

  2021cites this paper
• PrORAM

  2021cites this paper
• Polaris: Transparent Succinct Zero-Knowledge Arguments for R1CS with Efficient Verifier

  2021influential citation
• Privacy-Preserving IP Verification

  2021cites this paper
• Transparency Dictionaries with Succinct Proofs of Correct Operation

  2021cites this paper
• PrORAM - Fast P(logn) Authenticated Shares ZK ORAM

  2021cites this paper
• Brakedown: Linear-time and post-quantum SNARKs for R1CS

  2021cites this paper
• Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments

  2021cites this paper
• Shorter and Faster Post-Quantum Designated-Verifier zkSNARKs from Lattices

  2021cites this paper
• Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

  2021cites this paper
• PrORAM: Fast O(log n) Private Coin ZK ORAM

  2021cites this paper
• Linear-time and post-quantum zero-knowledge SNARKs for R1CS

  2021cites this paper
• Implementation of real estate contract system using zero knowledge proof algorithm based blockchain

  2021cites this paper
• Efficient permutation protocol for MPC in the head

  2021cites this paper
• Linear-time zero-knowledge SNARKs for R1CS

  2021cites this paper
• A Study of Zero-Knowledge Circuit Based on Reduce Transaction Storage Cost

  2021cites this paper
• Non-Interactive Zero-Knowledge for Blockchain: A Survey

  2020cites this paper
• Spartan: Efficient and general-purpose zkSNARKs without trusted setup

  2020influential citation
• TinyRAM Architecture Specification v2 . 000

  2020cites this paper
• Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads

  2020cites this paper
• On the (In)security of Kilian-Based SNARGs

  2019cites this paper
• Aurora: Transparent Succinct Arguments for R1CS

  2019cites this paper
• Verifiable Computing for Approximate Computation

  2019cites this paper
• Linear-Size Constant-Query IOPs for Delegating Computation

  2019cites this paper
• Scaling Verifiable Computation Using Efficient Set Accumulators

  2019influential citation
• zkInterface, a standard tool for zero-knowledge interoperability

  2019cites this paper
• Computation Verification for Noobs

  2019influential citation
• Local reduction

  2018cites this paper
• xJsnark: A Framework for Efficient Verifiable Computation

  2018cites this paper
• vRAM: Faster Verifiable RAM with Program-Independent Preprocessing

  2018cites this paper
• Proving the correct execution of concurrent services in zero-knowledge

  2018cites this paper
• Computational Complexity

  2018cites this paper
• Scalable, transparent, and post-quantum secure computational integrity

  2018cites this paper
• Algebraic RAM

  2017cites this paper
• Turning Computer Programs Into Circuits ( Part 1 )

  2017cites this paper
• Computational Integrity with a Public Random String from Quasi-Linear PCPs

  2017influential citation
• Decentralized Anonymous Payments

  2017cites this paper
• C ∅ C ∅ : A Framework for Building Composable Zero-Knowledge Proofs

  2016cites this paper
• On the security of authentication protocols on the web. (La sécurité des protocoles d'authentification sur leWeb)

  2016cites this paper
• A Certified Compiler for Verifiable Computing

  2016cites this paper
• Cinderella: Turning Shabby X.509 Certificates into Elegant Anonymous Credentials with the Magic of Verifiable Computation

  2016cites this paper
• Hash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data

  2016influential citation
• Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

  2016cites this paper
• Multi-variate Abstractions of Algebraic Geometry Codes, With Applications

  2016cites this paper
• Hybrid Publicly Verifiable Computation

  2016cites this paper
• Shorter arithmetization of nondeterministic computations

  2015cites this paper
• Extended Functionality in Verifiable Searchable Encryption

  2015cites this paper
• Efficient RAM and control flow in verifiable outsourced computation

  2015cites this paper
• Geppetto: Versatile Verifiable Computation

  2015influential citation
• Verifying computations without reexecuting them

  2015cites this paper
• Block Programs: Improving Efficiency of Verifiable Computation for Circuits with Repeated Substructures

  2015cites this paper
• Cryptography and Information Security in the Balkans

  2015cites this paper
• Short PCPs with Projection Queries

  2014cites this paper
• Outsourcing Private RAM Computation

  2014cites this paper
• Verifiable Oblivious Storage

  2014cites this paper
• Scalable Zero Knowledge Via Cycles of Elliptic Curves

  2014influential citation
• SNARKs for C : Verifying Program Executions Succinctly and in Zero Knowledge

  2014cites this paper
• Succinct non-Interactive arguments

  2014cites this paper
• Towards practical verifiable computation: Verification outsourcing, linear arguments without linearity tests, and repeated structures

  2014cites this paper
• Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture

  2014influential citation
• Succinct Computational Integrity (SCI) and Probabilistically Checkable Proofs (PCP)

  2014cites this paper
• Recursive composition and bootstrapping for SNARKS and proof-carrying data

  2013cites this paper
• Succinct Non-Interactive Arguments for a von Neumann Architecture

  2013cites this paper
• Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity

  2013cites this paper
• Local Reductions

  2013cites this paper
• Succinct Non-Interactive Arguments via Linear Interactive Proofs

  2013cites this paper
• A Fresh Look at Boolean Functions: Progress Report

  2013cites this paper
• Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles

  2013cites this paper
• Verifying computations with state ( extended version )

  2013cites this paper
• Resolving the conflict between generality and plausibility in verified computation

  2013cites this paper
• A Hybrid Architecture for Interactive Verifiable Computation

  2013cites this paper
• Verifying computations with state

  2013cites this paper
• SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge

  2013cites this paper
• Time-Optimal Interactive Proofs for Circuit Evaluation

  2013cites this paper
• SNARKs for C : Verifying Program Executions Succinctly and in Zero Knowledge by Madars Virza

  2013cites this paper