Seminar Series

## Yupeng Zhang: Verifiable Databases and RAM Programs

Yupeng Zhang, University of Maryland, College Park

#### Part Of

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

## Yupeng Zhang: Verifiable Databases and RAM Programs

Yupeng Zhang, University of Maryland, College Park

#### Part Of

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

## Charles River Crypto Day

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

#### Part Of

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&lt;\eps &lt;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

## March 02

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 Belfer sarah_donahue@hks.harvard.edu

## March 09

Add to Calendar 2018-03-09 10:30:00 2018-03-09 12:00:00 America/New_York Hayim Shaul: Scalable Secure Computation of Moments with Application to k-Nearest Neighbors Abstract:Given a set S of n d-dimensional points, the k-nearest neighbors (kNN) is the problem of quickly finding k points in S that are nearest to a query point q.The k-nearest neighbors problem has applications in machine learning for classifications and regression and also in searching.The secure version of kNN where either q or S are encrypted, has applications such as providing services over sensitive (such as medical or localization) data.In this work we present a scalable and efficient algorithm for solving kNN with Fully Homomorphic Encryption (FHE).The efficiency stems from the fact that it is realized by a polynomial whose degree is independent of n, the number of points, or d the dimension.We implemented our algorithm based on HELib implementation for the Brakerski-Gentry-Vaikuntanthan’s FHE scheme, and ran experiments on a standard server.Our algorithm computes the set of k=13 nearest points to a query point q for databases with more than a thousand points in close to half an hour, compared to several hours via existing approaches.Our result introduces a statistical coreset, which is a data summarization technique that allows sums such as moments to be efficiently and scalably approximated. As a central tool, we design a new coin toss technique which we use to build the coreset. This coin toss technique and computation of moments may be of independent interest.Bio: Hayim Shaul is a postdoc in MIT working with Daniela Rus. His research interests are in building efficient secure systems. Prior to being a postdoc Hayim did his PhD in computational geometry in Tel-Aviv University under the supervision of Micha Sharir. Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu

## Jack Doerner: ORAM for Secure Computation

Jack Doerner, Northeastern University

#### Part Of

Add to Calendar 2018-03-23 10:30:00 2018-03-23 12:00:00 America/New_York Jack Doerner: ORAM for Secure Computation Abstract: We design and implement a Distributed Oblivious Random Access Memory (DORAM) data structure that is optimized for use in two-party secure computation protocols. We improve upon the access time of previous constructions by a factor of up to ten, their memory overhead by a factor of one hundred or more, and their initialization time by a factor of thousands. We are able to instantiate ORAMs that hold 234 bytes, and perform operations on them in seconds, which was not previously feasible with any implemented scheme.Unlike prior ORAM constructions based on hierarchical hashing, permutation, or trees, our Distributed ORAM is derived from the new Function Secret Sharing scheme introduced by Boyle, Gilboa and Ishai. This significantly reduces the amount of secure computation required to implement an ORAM access, albeit at the cost of O(n) efficient local memory operations.We implement our construction and find that, despite its poor O(n) asymptotic complexity, it still outperforms the fastest previously known constructions, Circuit ORAM and Square-root ORAM, for datasets that are 32 KiB or larger, and outperforms prior work on applications such as stable matching or binary search by factors of two to ten.This is a joint work with Abhi Shelat G882, Hewlett Belfer sarah_donahue@hks.harvard.edu

## April 13

Add to Calendar 2018-04-13 10:30:00 2018-04-13 12:00:00 America/New_York Alex Lombardi: Cryptographic Hashing From Strong One-Way Functions Abstract: Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standingopen problem and source of frustration in theoretical cryptography. In fact, there are strong negativeresults: black-box separations from exponentially secure one-way functions (Simon,EUROCRYPT '98) and even indistinguishability obfuscation (Asharov and Segev, FOCS '15).In this work, we formulate a mild strengthening of exponentially secure one-way functions, and weconstruct CRHFs from such functions. Specifically, our security notion requires that everypolynomial-time algorithm has exponentially small probability of inverting two independentchallenges. More generally, we consider the problem of simultaneously inverting $k$ functions(f_1, ..., f_k), which we say constitute a "one-way product function" (OWPF). We show thatsufficiently hard OWPFs yield hash families that are multi-input correlation intractable(Canetti, Goldreich, and Halevi, STOC '98) with respect to a restricted class of relations.Additionally assuming indistinguishability obfuscation, we construct hash families that achieve abroader notion of correlation intractability. In particular, these families aresufficient to instantiate the Fiat-Shamir heuristic in the plain model for a naturalclass of interactive proofs.An interesting consequence of our results is a new avenue for bypassing black-boxseparations: proving (with necessarily non-black-box techniques) that parallel repetition amplifies thehardness of a specific one-way function. Joint work with Justin Holmgren. Hewlett G882 Belfer sarah_donahue@hks.harvard.edu

## Charles River Crypto Day

Brent Waters, Mor Weiss, Tianren Liu and Ron Rothblum

#### Part Of

Add to Calendar 2018-04-20 9:30:00 2018-04-20 15:45:00 America/New_York Charles River Crypto Day Please visit the link for more information or contact Deborah Goodwin.https://bostoncryptoday.wordpress.com/ MS Research and Development Ovice, One Memorial Drive, Cambridge Belfer sarah_donahue@hks.harvard.edu

## April 27

Add to Calendar 2018-04-27 10:30:00 2018-04-27 12:00:00 America/New_York Adi Shamir: Towards Quantitative Analysis of Cyber Security ABSTRACT: Cyber security had become an extremely hot topic in the last few years, but almost all the research results published so far had been qualitative in nature: they do not formulate a precise mathematical model of the problem, do not numerically compare alternatives, and do not try to find optimal solutions for cyber security problems. In this paper I will describe some initial attempts (developed jointly with Bar-On Dinur Dunkelman Hod Keller and Ronen) to create such a quantitative theory of some particular subproblems in cyber security. In particular, I will consider the problem of how to protect a computer system against cyber and ransomware attacks by choosing an optimal backup scheme using k storage devices. While in standard backup schemes it is beneficial to backup as frequently as possible, in the case of sophisticated cyber attacks any attempt to connect a backup device to an already infected computer is likely to stealthily corrupt its data and thus make it unusable when the actual attack happens. Our formalization of the problem casts it as a special case of an online/offline optimization problem, in which the defender tries to minimize the maximal extra cost caused by his lack of knowledge about the time of the infection, and the strategies he can use resemble a pebbling game with k tokens which can be placed anywhere along the timeline. However, the optimal solution of this simple pebbling game is surprisingly complicated. In this talk I will describe concrete provably optimal backup strategies for all $k \leq 10$, and asymptotically optimal strategies for large k. Our results also solve a long standing open problem in fault tolerant computing called {\it optimal checkpointing}, which had been investigated in various forms for almost 50 years. Patil/Kiva G449 Belfer sarah_donahue@hks.harvard.edu

## Kevin Fu: Physics of Cybersecurity: Sensors, Acoustics, Cuba

Kevin Fu, University of Michigan

#### Part Of

Add to Calendar 2018-05-11 10:30:00 2018-05-11 12:00:00 America/New_York Kevin Fu: Physics of Cybersecurity: Sensors, Acoustics, Cuba Abstract: Medical devices, autonomous vehicles, and the Internet of Things depend on the integrity and availability of trustworthy data from sensors to make safety-critical, automated decisions. How can such cyberphysical systems remain secure against an adversary using intentional interference to fool sensors? Physics-based cybersecurity risks can bubble up into operating systems as bizarre, undefined behavior. Transduction attacks using audible acoustic, ultrasonic, and radio interference can manipulate sensors found in devices ranging from fitbits to hard drives to implantable medical devices with implications to file system integrity and human safety. Defenders can fight back with physics and more trustworthy software APIs. I’ll wrap up by explaining how ultrasonic exfiltration could have caused the symptoms experienced by diplomats harmed in Cuba.Biography: Kevin Fu enjoys early-stage, interdisciplinary research where there are still many par-baked problems to define and solve. Kevin was recognized as an IEEE Fellow, Sloan Research Fellow, and MIT Technology Review TR35 Innovator of the Year. He serves as chair of the CCC Cybersecurity Task Force. His students received some best paper awards. Kevin earned a certificate of artisanal bread making from the French Culinary Institute. http://web.eecs.umich.edu/~kevinfu/ Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu

## May 18

Add to Calendar 2018-05-18 10:30:00 2018-05-18 12:00:00 America/New_York Must the Communication Graph of MPC Protocols be an Expander? Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) Where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) Where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored.In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graph expansion. All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent.Our results consist of two types (for constant fraction of corruptions):* Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low locality and adaptive security) each assuming some form of input-independent setup.* Lower bounds: In the setting without setup and adaptive corruptions, we demonstrate that for certain functionalities, no protocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy), and requires a surprisingly delicate argument.More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties. This is a joint work with Elette Boyle, Deepesh Data, and Pavel Hubacek. Hewlett G882 Belfer sarah_donahue@hks.harvard.edu

## Sophia Yakoubov: "Fuzzy Password-Authenticated Key Exchange"

Sophia Yakoubov, Boston University

#### Part Of

Add to Calendar 2018-05-18 13:00:00 2018-05-18 14:00:00 America/New_York Sophia Yakoubov: &quot;Fuzzy Password-Authenticated Key Exchange&quot; Abstract:Consider key agreement by two parties who start out knowing a common secret (which we refer to as “pass-string”, a generalization of “password”), but face two complications: (1) the pass-string may come from a low-entropy distribution, and (2) the two parties’ copies of the pass-string may have some noise, and thus not match exactly. We provide the first efficient and general solutions to this problem that enable, for example, key agreement based on commonly used biometrics such as iris scans.The problem of key agreement with each of these complications individually has been well studied in literature. Key agreement from low-entropy shared pass-strings is achieved by password-authenticated key exchange (PAKE), and key agreement from noisy but high-entropy shared pass-strings is achieved by information-reconciliation protocols as long as the two secrets are “close enough.” However, the problem of key agreement from noisy low-entropy pass-strings has never been studied.We introduce (universally composable) fuzzy password-authenticated key exchange (fPAKE), which solves exactly this problem. fPAKE does not have any entropy requirements for the pass-strings, and enables secure key agreement as long as the two pass-strings are “close” for some notion of closeness. We also give two constructions. The first construction achieves our fPAKE definition for any (efficiently computable) notion of closeness, including those that could not be handled before even in the high-entropy setting. It uses Yao’s Garbled Circuits in a way that is only two times more costly than their use against semi-honest adversaries, but that guarantees security against malicious adversaries. The second construction is more efficient, but achieves our fPAKE definition only for pass-strings with low Hamming distance. It builds on very simple primitives: robust secret sharing and PAKE.Joint work with Pierre-Alain Dupont, Julia Hesse, David Pointcheval, and Leonid Reyzin. To appear at Eurocrypt 2018. Hewlett, G882 Belfer sarah_donahue@hks.harvard.edu

## June 18

Add to Calendar 2018-06-18 11:00:00 2018-06-18 12:30:00 America/New_York Merav Parter: Distributed Computing Made Secure: A New Cycle Cover Theorem Abstract: In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information (e.g., distributed networks of selfish agents, decentralized digital currency such as Bitcoin).While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptographic community. The existing secure MPC protocols do not quite fit the framework of classical distributed models in which only messages of bounded size are sent on graph edges in each round.In this paper, we introduce a new framework for secure distributed graph and provide the first general compiler that takes any natural'' non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot \poly(\Delta))$ rounds where $\Delta$ is the maximum degree in the graph and $D$ is its diameter. A natural'' distributed algorithm is one where the local computation at each node can be performed in polynomial time. An interesting advantage of our approach is that it allows one to decouple between the price of locality and the price of security of a given graph function $f$. The security of the compiled algorithm is information-theoretic but holds only against a semi-honest adversary that controls a single node in the network. The main technical part of our compiler is based on a new cycle cover theorem: We show that the edges of every bridgeless graph $G$ of diameter $D$ can be covered by a collection of cycles such that each cycle is of length $\widetilde{O}(D)$ and each edge of the graph $G$ appears in $\widetilde{O}(1)$ many cycles, existentially this is optimal, upto polylogarithmic terms. Joint work with Eylon Yogev. G575 Belfer sarah_donahue@hks.harvard.edu