February 09

Add to Calendar 2018-02-09 10:30:00 2018-02-09 12:00:00 America/New_York Yupeng Zhang: Verifiable Databases and RAM Programs Abstract: The talk covers the following two papers:vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced DatabasesCloud database systems such as Amazon RDS or Google Cloud SQL enable the outsourcing of a large database to a server who then responds to SQL queries. A natural problem here is to efficiently verify the correctness of responses returned by the (untrusted) server. In this paper we present vSQL, a novel cryptographic protocol for publicly verifiable SQL queries on dynamic databases. At a high level, our construction relies on two extensions of the CMT interactive-proof protocol [Cormode et al., 2012]: (i) supporting outsourced input via the use of a polynomial-delegation protocol with succinct proofs, and (ii) supporting auxiliary input (i.e., non-deterministic computation) efficiently. Compared to previous verifiable-computation systems based on interactive proofs, our construction has verification cost polylogarithmic in the auxiliary input (which for SQL queries can be as large as the database) rather than linear. In order to evaluate the performance and expressiveness of our scheme, we tested it on SQL queries based on the TPC-H benchmark on a database with 6 x 106 rows and 13 columns. The server overhead in our scheme (which is typically the main bottleneck) is up to 120 x lower than previous approaches based on succinct arguments of knowledge (SNARKs), and moreover we avoid the need for query-dependent pre-processing which is required by optimized SNARK-based schemes. In our construction, the server/client time and the communication cost are comparable to, and sometimes smaller than, those of existing customized solutions which only support specific queries.vRAM: Faster Verifiable RAM With Program-Independent PreprocessingWe study the problem of verifiable computation (VC) for RAM programs, where a computationally weak verifier outsources the execution of a program to a powerful (but untrusted) prover. Existing efficient implementations of VC protocols require an expensive preprocessing phase that binds the parties to a single circuit. (While there are schemes that avoid preprocessing entirely, their performance remains significantly worse than constructions with preprocessing.) Thus, a prover and verifier are forced to choose between two approaches: (1) Allow verification of arbitrary RAM programs, at the expense of efficiency, by preprocessing a universal circuit which can handle all possible instructions during each CPU cycle; or (2) Sacrifice expressiveness by preprocessing an efficient circuit which is tailored to the verification of a single specific RAM program. We present vRAM, a VC system for RAM programs that avoids both the above drawbacks by having a preprocessing phase that is entirely circuit-independent (other than an upper bound on the circuit size). During the proving phase, once the program to be verified and its inputs are chosen, the circuit-independence of our construction allows the parties to use a smaller circuit tailored to verifying the specific program on the chosen inputs, i.e., without needing to encode all possible instructions in each cycle. Moreover, our construction is the first with asymptotically optimal prover overhead; i.e., the work of the prover is a constant multiplicative factor of the time to execute the program. Our experimental evaluation demonstrates that vRAM reduces the prover's memory consumption by 55-110x and its running time by 9-30x compared to existing schemes with universal preprocessing. This allows us to scale to RAM computations with more than 2 million CPU cycles, a 65x improvement compared to the state of the art. Finally, vRAM has performance comparable to (and sometimes better than) the best existing scheme with program-specific preprocessing despite the fact that the latter can deploy program-specific optimizations (and has to pay a separate preprocessing cost for every new program). Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu
Add to Calendar 2018-02-09 10:30:00 2018-02-09 12:00:00 America/New_York Yupeng Zhang: Verifiable Databases and RAM Programs Abstract: The talk covers the following two papers:vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced DatabasesCloud database systems such as Amazon RDS or Google Cloud SQL enable the outsourcing of a large database to a server who then responds to SQL queries. A natural problem here is to efficiently verify the correctness of responses returned by the (untrusted) server. In this paper we present vSQL, a novel cryptographic protocol for publicly verifiable SQL queries on dynamic databases. At a high level, our construction relies on two extensions of the CMT interactive-proof protocol [Cormode et al., 2012]: (i) supporting outsourced input via the use of a polynomial-delegation protocol with succinct proofs, and (ii) supporting auxiliary input (i.e., non-deterministic computation) efficiently. Compared to previous verifiable-computation systems based on interactive proofs, our construction has verification cost polylogarithmic in the auxiliary input (which for SQL queries can be as large as the database) rather than linear. In order to evaluate the performance and expressiveness of our scheme, we tested it on SQL queries based on the TPC-H benchmark on a database with 6 x 106 rows and 13 columns. The server overhead in our scheme (which is typically the main bottleneck) is up to 120 x lower than previous approaches based on succinct arguments of knowledge (SNARKs), and moreover we avoid the need for query-dependent pre-processing which is required by optimized SNARK-based schemes. In our construction, the server/client time and the communication cost are comparable to, and sometimes smaller than, those of existing customized solutions which only support specific queries.vRAM: Faster Verifiable RAM With Program-Independent PreprocessingWe study the problem of verifiable computation (VC) for RAM programs, where a computationally weak verifier outsources the execution of a program to a powerful (but untrusted) prover. Existing efficient implementations of VC protocols require an expensive preprocessing phase that binds the parties to a single circuit. (While there are schemes that avoid preprocessing entirely, their performance remains significantly worse than constructions with preprocessing.) Thus, a prover and verifier are forced to choose between two approaches: (1) Allow verification of arbitrary RAM programs, at the expense of efficiency, by preprocessing a universal circuit which can handle all possible instructions during each CPU cycle; or (2) Sacrifice expressiveness by preprocessing an efficient circuit which is tailored to the verification of a single specific RAM program. We present vRAM, a VC system for RAM programs that avoids both the above drawbacks by having a preprocessing phase that is entirely circuit-independent (other than an upper bound on the circuit size). During the proving phase, once the program to be verified and its inputs are chosen, the circuit-independence of our construction allows the parties to use a smaller circuit tailored to verifying the specific program on the chosen inputs, i.e., without needing to encode all possible instructions in each cycle. Moreover, our construction is the first with asymptotically optimal prover overhead; i.e., the work of the prover is a constant multiplicative factor of the time to execute the program. Our experimental evaluation demonstrates that vRAM reduces the prover's memory consumption by 55-110x and its running time by 9-30x compared to existing schemes with universal preprocessing. This allows us to scale to RAM computations with more than 2 million CPU cycles, a 65x improvement compared to the state of the art. Finally, vRAM has performance comparable to (and sometimes better than) the best existing scheme with program-specific preprocessing despite the fact that the latter can deploy program-specific optimizations (and has to pay a separate preprocessing cost for every new program). Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu

February 16

Charles River Crypto Day

Siyao Guo, Northeastern University; Muthuramakrishnan Venkitasubramaniam, University of Rochester; Yael Kalai, MSR and MIT; Daniel Genkin, UPenn
Add to Calendar 2018-02-16 9:30:00 2018-02-16 15:45:00 America/New_York Charles River Crypto Day Program:9:30 – 10:00. Coffee/Welcome10:00 – 11:00. Siyao Guo, Northeastern UniversityRandom Oracles and Non-Uniformity11:15 – 12:15. Muthuramakrishnan Venkitasubramaniam, University of RochesterLigero: Lightweight Sublinear Zero-Knowledge Arguments12:15 – 1:30. Lunch1:30 – 2:30. Yael Kalai, MSR and MITNon-Interactive Delegation for Low-Space Non-Deterministic Computation2:45 – 3:45. Daniel Genkin, UPennSpectre and Meltdown: Speculative Execution Considered HarmfulFor more information please visit the website:https://bostoncryptoday.wordpress.com/ G882, Hewlett Belfer sarah_donahue@hks.harvard.edu

February 23

Add to Calendar 2018-02-23 10:30:00 2018-02-23 12:00:00 America/New_York Mukul Kulkarni: on-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering Abstract:We show a general framework for constructing non-malleable codes against tampering families with average-case hardness bounds. Our framework adapts ideas from the Naor-Yung double encryption paradigm such that to protect against tampering in a class F, it suffices to have average-case hard distributions for the class, and underlying primitives (encryption and non-interactive, simulatable proof systems) satisfying certain properties with respect to the class.We instantiate our scheme in a variety of contexts, yielding efficient, non-malleable codes (NMC) against the following tampering classes:(1) Computational NMC against AC0 tampering, in the CRS model, assuming a PKE scheme with decryption in AC0 and NIZK.(2) Computational NMC against bounded-depth decision trees (of depth t^\eps, where t is the number of input variables and 0<\eps <1), in the CRS model and under the same computational assumptions as above.(3) Information theoretic NMC (with no CRS) against a streaming, space-bounded adversary, namely an adversary modeled as a read-once branching program with bounded width.Ours are the first constructions that achieve each of the above in an efficient way, under the standard notion of non-malleability.This is a joint work with my advisor Dana Dachman-Soled; and with Marshall Ball, and Tal Malkin from Columbia University Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu