Back to Events

Seminar Series

March 02

Rio LaVigne: Topology Hiding Computation for All Graphs

Rio LaVigne, MIT

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-03-02 10:30:00 2018-03-02 12:00:00 America/New_York Rio LaVigne: Topology Hiding Computation for All Graphs Abstract:A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC’15; Hirt et.al, Crypto’16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt’17], but the feasibility question for general graphs was open. In this work we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under the Decisional Diffie-Hellman assumption and the QR assumption against passive adversaries. Our techniques employ random-walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple random-walks that, together, are locally identical to receiving at each round a message from each neighbors and sending back processed messages in a randomly permuted order. We can also extend this result to use deterministic walks (exploration sequences), opening up the possibility for a perfectly-complete topology hiding broadcast. Joint work with Adi Akavia and Tal Moran.Time permitting, I will also discuss the next sequence of results: we can also get topology hiding computation for all graphs against fail-stop adversaries while leaking an arbitrarily small polynomial fraction of a bit. This is based on joint work with Chen-Da Liu Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi. Hewlett, G882

February 23

Mukul Kulkarni: on-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering

Mukul Kulkarni, University of Maryland, College Park

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
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

February 16

Charles River Crypto Day

Siyao Guo, Northeastern University; Muthuramakrishnan Venkitasubramaniam, University of Rochester; Yael Kalai, MSR and MIT; Daniel Genkin, UPenn

Part Of

9:30A
- 3:45P

Location

G882, Hewlett
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

February 09

Yupeng Zhang: Verifiable Databases and RAM Programs

Yupeng Zhang, University of Maryland, College Park

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
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

Yupeng Zhang: Verifiable Databases and RAM Programs

Yupeng Zhang, University of Maryland, College Park

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
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

February 02

Saleet Klein: The Edited Truth

Saleet Klein, MIT

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-02-02 10:30:00 2018-02-02 12:00:00 America/New_York Saleet Klein: The Edited Truth Abstract: We introduce two new cryptographic notions in the realm of public and symmetric key encryption.– Encryption with invisible edits is an encryption scheme with two tiers of users: “privileged” and “unprivileged”. Privileged users know a key pair (pk, sk) and “unprivileged” users know a key pair (pk_e, sk_e) which is associated with an underlying edit e to be applied to messages encrypted. When an unprivileged user attempts to decrypt a ciphertext generated by a privileged user of an underlying plaintext m, it will be decrypted to an edited m’=Edit(m,e). Here, Edit is a supported edit function and e is a description of the particular edit. A user shouldn’t be able to tell whether he’s an unprivileged or a privileged user.– An encryption with deniable edits is an encryption scheme which allows a user who owns a ciphertext c encrypting a large corpus of data m under a secret key sk, to generate an alternative but legitimate looking secret key sk_{c,e}, that decrypts c to an “edited” version of the data m’=Edit(m,e). This generalizes classical receiver deniable encryption, which is a special case of deniable edits where the edit function completely replaces the original data. The new flexibility allows to design solutions with much smaller key sizes than required in classical receiver deniable encryption allowing the key size to only scale with the description size of the edit e which can be much smaller than the plaintext data m.We construct encryption schemes with invisible and deniable edits for any polynomial-time computable edit function under minimal assumptions: in the public-key setting we require the existence of standard public-key encryption and in the symmetric-key setting require the existence of one-way functions.The solutions to both problems use common ideas, however there is a significant conceptual difference between deniable edits and invisible edits. Whereas encryption with deniable edits enables a user to modify the meaning of a single ciphertext in hindsight, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts.Joint work with: Shafi Goldwasser and Daniel Wichs Hewlett, G882

January 26

Xiao Wang: Authenticated Garbling: Efficient Maliciously Secure Two-Party Computation and Global-Scale Secure Multiparty Computation

Xiao Wang, University of Maryland, College Park

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-01-26 10:30:00 2018-01-26 12:00:00 America/New_York Xiao Wang: Authenticated Garbling: Efficient Maliciously Secure Two-Party Computation and Global-Scale Secure Multiparty Computation Abstract: This talk consists of two papers:== Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation ==We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two parties; this information is then used to construct a single ``authenticated'' garbled circuit which is transmitted and evaluated.We also show how to efficiently instantiate the preprocessing phase by designing a highly optimized version of the TinyOT protocol by Nielsen et al. Our overall protocol outperforms existing work in both the single-execution and amortized settings, with or without preprocessing:- In the single-execution setting, our protocol evaluates an AES circuit with malicious security in 37 ms with an online time of just 1 ms. Previous work with the best online time (also 1 ms) requires 124 ms in total; previous work with the best total time requires 62 ms (with 14 ms online time).- If we amortize the computation over 1024 executions, each AES computation requires just 6.7 ms with roughly the same online time as above. The best previous work in the amortized setting has roughly the same total time but does not support function-independent preprocessing.Our work shows that the performance penalty for maliciously secure two-party computation (as compared to semi-honest security) is much smaller than previously believed.== Global-Scale Secure Multiparty Computation ==We propose a new, constant-round protocol for multi-party computation of boolean circuits that is secure against an arbitrary number of malicious corruptions. At a high level, we extend and generalize recent work of Wang et al. in the two-party setting and design an efficient preprocessing phase that allows the parties to generate authenticated information; we then show how to use this information to distributively construct a single ``authenticated'' garbled circuit that is evaluated by one party.Our resulting protocol improves upon the state-of-the-art both asymptotically and concretely. We validate these claims via several experiments demonstrating both the efficiency and scalability of our protocol:- Efficiency: For three-party computation over a LAN, our protocol requires only 95 ms to evaluate AES. This is roughly a 700× improvement over the best prior work, and only 2.5× slower than the best known result in the two-party setting. In general, for n parties our protocol improves upon prior work (which was never implemented) by a factor of more than 230n, e.g., an improvement of 3 orders of magnitude for 5-party computation.- Scalability: We successfully executed our protocol with a large number of parties located all over the world, computing (for example) AES with 128 parties across 5 continents in under 3 minutes. Our work represents the largest-scale demonstration of secure computation to date. Hewlett, G882