Back to Events

Seminar Series

November 30

Amit Sahai: Obfuscation without multilinear maps

Amit Sahai, UCLA

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-11-30 10:30:00 2018-11-30 12:00:00 America/New_York Amit Sahai: Obfuscation without multilinear maps Abstract: Suppose we sample a set of m>>n constant-degree polynomials over n real variables, and evaluate them on a random vector. How hard is it to solve the resulting set of equations over the reals? Such questions have a long history of scientific inquiry; indeed, solving polynomial equations over the reals has been studied by mathematicians, scientists, and engineers for hundreds of years. In this talk, we show that simple-to-state hardness assumptions closely related to this question, when combined with LWE and bilinear maps, can be used to construct indistinguishability obfuscation for general circuits. In particular, we do not require any assumptions related to multilinear maps. Critical to our work are techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. In particular, as a byproduct of our work, we obtain a new security amplification theorem for functional encryption. Talk based primarily on joint work with Prabhanjan Ananth and Aayush Jain, and joint work with Aayush Jain. Hewlett, G882

November 16

Hoeteck Wee: Obfuscation from LWE: How Far Are We?

Hoeteck Wee, ENS

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-11-16 10:30:00 2018-11-16 12:00:00 America/New_York Hoeteck Wee: Obfuscation from LWE: How Far Are We? Abstract:GGH15 provide a way to encode many pairs of matrices, such that we cancheck whether any subset product is zero, while potentially hiding allother information about the matrices. This immediately yields acandidate obfuscator for log-space computation, whose security seemsrelated to the LWE assumption. So, how far are we from obfuscation forcircuits or NC1 from LWE? How about smaller classes of functions, likeread-once branching programs, or the constant all-reject function?In this talk, we will present some answers to this question:* a proof from LWE that we can use GGH15 to securely obfuscate a largesub-class of the all-reject function (which yields new constructionsof lockable obfuscation, private constrained PRFs and mixed FE schemesfor NC1);* an attack on the GGH15-based obfuscator for read-once branchingprograms from CCS17;* a new and simple candidate obfuscator for NC1 (and an even simplerone for witness encryption). Hewlett, G882

November 09

Oxana Poburinnaya: Fully bi-deniable interactive encryption

Oxana Poburinnaya, Boston University

Part Of

10:30A
- 12:00P

Location

32-155 (please make note of location)
Add to Calendar 2018-11-09 10:30:00 2018-11-09 12:00:00 America/New_York Oxana Poburinnaya: Fully bi-deniable interactive encryption Abstract: Deniable encryption guarantees an extremely strong level of privacy: It provides the parties with algorithmic ways to come up with fake keys and random inputs that ``open'' the public communication to any plaintext of the parties' choice. This allows the actual plaintext to remain hidden even in face of an after-the-fact attacker that coerces the communicating parties to disclose all their data, keys, and local random choices. However, to date we only have public-key encryption schemes that provide partial deniability guarantees: Either deniability only for the sender, or only for the receiver, or a weaker form of deniability where the fake keys and random input are only consistent with different algorithms than the ones used.We construct the first encryption protocol that provides full deniability even when both the sender and the receiver are coerced, separately, with respect to the same interaction. Furthermore, our scheme satisfies an additional property which we call off-the-record deniability: when the parties` accounts are inconsistent with each other (i.e. the sender claims it sent m, but the receiver claims it received m'!=m), off-the-record deniability guarantees that there is no way for the coercer to tell which one is lying. Our protocol has three messages, which is tight with the known impossibility of Bendlin et al (Asiacrypt 2011) for two-message protocols. We assume sub-exponential indistinguishability obfuscation (IO) and one way functions, and work in a model where all parties have access to public obfuscated programs (these programs can be generated in advance and then reused arbitrary polynomial number of times). Our construction involves program with a special hidden logic that thwarts all potential adversarial recombinations of pieces of a transcript and random inputs to the parties. To show that this logic suffices even when protected only by IO, we employ techniques which are traditionally used in the ``iterated circuits'' setting, such as the construction of garbled Turing machines from circuit-IO.Joint work with Ran Canetti and Sunoo Park 32-155 (please make note of location)

November 02

Mark Zhandry: Quantum Lightning Never Strikes the Same State Twice

Mark Zhandry, Princeton

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-11-02 10:30:00 2018-11-02 12:00:00 America/New_York Mark Zhandry: Quantum Lightning Never Strikes the Same State Twice Abstract: Quantum no-cloning states that it is physically impossible to clone a quantum state. No-cloning is a central to the study of quantum cryptography, where it allows for objects such as physically unforgeable currency. In this work, I study two strong variants of no-cloning: (1) public key quantum money, where the would-be cloner is given a verification oracle for checking if it successfully cloned; and (2) quantum lightning, where the cloner even knows all the details of how the initial state was constructed. I then give a variety of results for public key quantum money and quantum lightning, yielding new constructions and interesting connections to other areas of cryptography. Hewlett, G882

October 26

Urmila Mahadev (Berkeley): Classical Homomorphic Encryption for Quantum Circuits

Urmila Mahadev

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-10-26 10:30:00 2018-10-26 12:00:00 America/New_York Urmila Mahadev (Berkeley): Classical Homomorphic Encryption for Quantum Circuits Abstract: We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to blindly delegate a quantum computation to a quantum server: an honest server is able to run the computation while a malicious server is unable to learn any information about the computation. We show that it is possible to construct such a scheme directly from a quantum secure classical homomorphic encryption scheme with certain properties. Finally, we show that a classical homomorphic encryption scheme with the required properties can be constructed from the learning with errors problem. Hewlett, G882

October 19

Yevgeniy Dodis: Small-Box Cryptography

Yevgeniy Dodis, NYU

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-10-19 10:30:00 2018-10-19 12:00:00 America/New_York Yevgeniy Dodis: Small-Box Cryptography Abstract: One of the ultimate goals of symmetric-key cryptography is to find rigorous theoretical framework for building block ciphers from small pseudorandom components, such as cryptographic S-boxes, and then argue why iterating such small components for sufficiently many rounds would yield a secure construction. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond than 2^{-n}, where n is the size of the corresponding component. As a result, prior provably secure approaches --- which we call "big-box cryptography" --- always made n larger than the security parameter, which led to several problems divorcing such results from reality. In this work introduce a novel paradigm for justifying the security of existing block ciphers, which we call *small-box cryptography*. Unlike the "big-box" paradigm, it allows one to go much deeper inside the existing block cipher constructions, by only idealizing a small (and, hence, realistic!) building block of very small size n, such as an 8-to-32-bit S-box. It then introduces a clean and rigorous mixture of proofs and hardness conjectures which allow one to lift traditional, and seemingly meaningless, "at most 2^{-n}" security proofs for *reduced-round* idealized variants of the existing block ciphers, into meaningful, *full-round* security justifications of the actual ciphers used in the real world. We then apply our framework to the design of popular SPN-based ciphers, which include AES, Serpent, and PRESENT, among others. To the best of our knowledge, our results give the most accurate and plausible theoretical justification for the security of SPN ciphers to date. Hewlett, G882

October 12

Xiao Wang (MIT): Covert Security with Public Verifiability: Simpler, Faster, and Leaner

Xiao Wang, MIT

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Hewlett, G882
Add to Calendar 2018-10-12 10:30:00 2018-10-12 12:00:00 America/New_York Xiao Wang (MIT): Covert Security with Public Verifiability: Simpler, Faster, and Leaner Abstract:The notion of covert security for secure two-party computation serves as acompromise between the traditional semi-honest and malicious securitydefinitions. Roughly, covert security ensures that cheating behavior isdetected by the honest party with reasonable probability (say, 1/2). Itprovides more realistic guarantees than semi-honest security withsignificantly less overhead than is required by malicioussecurity.The rationale for covert security is that it dissuades cheating by partiesthat care about their reputation and do not want to risk being caught. Furtherthought, however, shows that a much stronger disincentive is obtained if thehonest party cangenerate a publicly verifiable certificate of misbehavior when cheating isdetected. While the corresponding notion of publicly verifiable covert (PVC)security has been explored, existing PVC protocols are complex and lessefficient than the best-known covert protocols, and have impractically largecertificates.We propose a novel PVC protocol that significantly improves on prior work. Ourprotocol uses only ''off-the-shelf'' primitives (in particular, it avoidssigned oblivious transfer) and, for deterrence factor 1/2, has only 20--40\%overhead (depending on the circuit size and network bandwidth) compared tostate-of-the-art semi-honest protocols. Our protocol also has, for the firsttime, constant-size certificates of cheating (e.g., 488 bytes long at the128-bit security level). As our protocol offers strong security guarantees with low overhead, wesuggest that it is the best choice for many practical applications of securetwo-party computation. Hewlett, G882

October 05

Willy Quach: Laconic Function Evaluation and Applications

Willy Quach, Northeastern

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-10-05 10:30:00 2018-10-05 12:00:00 America/New_York Willy Quach: Laconic Function Evaluation and Applications Abstract: We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties:_ We construct a 2-round 2PC protocol between Alice and Bob with respective inputs x_A, x_B in which Alice learns the output f(x_A,x_B) in the second round. This is the first such protocol which is ``Bob-optimized'', meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit f or even Alice's input x_A. In contrast, prior solutions based on fully homomorphic encryption are ``Alice-optimized''._ We construct an MPC protocol, which allows N parties to securely evaluate a function f(x_1,...,x_N) over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size. Joint work with Hoeteck Wee and Daniel Wichs. Hewlett, G882

September 28

Aikaterini Sotiraki: PPP-Completeness with Connections to Cryptography

Aikaterini Sotiraki, MIT

Part Of

10:30A
- 12:00P

Location

Hewlett, G882
Add to Calendar 2018-09-28 10:30:00 2018-09-28 12:00:00 America/New_York Aikaterini Sotiraki: PPP-Completeness with Connections to Cryptography Abstract: PPP is an important subclass of TFNP with profound connections tothe complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, prior to our work no complete problem was known for PPP. Our work identifies the first naturalPPP-complete problem: constrained-SIS (cSIS), and thus we answer a longstanding open question since[Papadimitriou1994]. Building on the inherent connection of PPP with collision-resistant hash functions,we use our completeness result to construct the first natural hash function familythat captures the hardness of all collision-resistant hash functions in aworst-case sense, i.e. it is universal in the worst-case. Hewlett, G882

September 14

Eylon Yogev (Weizmann Institute):On Distributional Collision Resistant Hashing

Eylon Yogev

Part Of

10:30A
- 12:00P

Location

G882, Hewlett
Add to Calendar 2018-09-14 10:30:00 2018-09-14 12:00:00 America/New_York Eylon Yogev (Weizmann Institute):On Distributional Collision Resistant Hashing Abstract:Collision resistant hashing is a fundamental concept that is the basis for many of the important cryptographic primitives and protocols. Collision resistant hashing is a family of compressing functions such that no efficient adversary can find {\em any} collision given a random function in the family. In this work we study a relaxation of collision resistance called \emph{distributional} collision resistance, introduced by Dubrov and Ishai (STOC '06). This relaxation of collision resistance only guarantees that no efficient adversary, given a random function in the family, can \emph{sample} a pair $(x,y)$ where $x$ is uniformly random and $y$ is uniformly random conditioned on colliding with $x$. Our first result shows that distributional collision resistance can be based on the existence of \emph{multi}-collision resistance hash (with no additional assumptions). Multi-collision resistance is another relaxation of collision resistance which guarantees that an efficient adversary cannot find any tuple of $k>2$ inputs that collide relative to a random function in the family. The construction is non-explicit, non-black-box, and yields an infinitely-often secure family. This partially resolves a question of Berman et al.\ (EUROCRYPT '18). We further observe that in a black-box model such an implication (from multi-collision resistance to distributional collision resistance) does not exist. Our second result is a construction of a distributional collision resistant hash from the average-case hardness of SZK. Previously, this assumption was not known to imply any form of collision resistance (other than the ones implied by one-way functions). Joint work with Ilan Komargodski. G882, Hewlett

June 18

Merav Parter: Distributed Computing Made Secure: A New Cycle Cover Theorem

Merav Parter, Weizmann

Part Of

1:30P
- 2:30P

Location

32-G882 (Hewlett Room)
Add to Calendar 2018-06-18 13:30:00 2018-06-18 14: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. 32-G882 (Hewlett Room)

May 18

Sophia Yakoubov: "Fuzzy Password-Authenticated Key Exchange"

Sophia Yakoubov, Boston University

Part Of

1:00P
- 2:00P

Location

Hewlett, G882
Add to Calendar 2018-05-18 13:00:00 2018-05-18 14:00:00 America/New_York Sophia Yakoubov: "Fuzzy Password-Authenticated Key Exchange" 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

Must the Communication Graph of MPC Protocols be an Expander?

Ran Cohen

Part Of

10:30A
- 12:00P

Location

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

May 11

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

Kevin Fu, University of Michigan

Part Of

10:30A
- 12:00P

Location

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

April 27

Adi Shamir: Towards Quantitative Analysis of Cyber Security

Adi Shamir, Weizmann

Part Of

10:30A
- 12:00P

Location

Patil/Kiva G449
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

April 20

Charles River Crypto Day

Brent Waters, Mor Weiss, Tianren Liu and Ron Rothblum

Part Of

9:30A
- 3:45P

Location

MS Research and Development Ovice, One Memorial Drive, Cambridge
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

April 13

Alex Lombardi: Cryptographic Hashing From Strong One-Way Functions

Alex Lombardi, MIT

Part Of

10:30A
- 12:00P

Location

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

March 23

Jack Doerner: ORAM for Secure Computation

Jack Doerner, Northeastern University

Part Of

10:30A
- 12:00P

Location

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

March 09

Hayim Shaul: Scalable Secure Computation of Moments with Application to k-Nearest Neighbors

Hayim Shaul, MIT

Part Of

10:30A
- 12:00P

Location

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