Elette Boyle

eboyle [at] alum [dot] mit [dot] edu

Director FACT Research Center

Senior Scientist at NTT Research

Associate Professor
Head of RRIS International Program
Efi Arazi School of Computer Science
Reichman University (IDC Herzliya), Israel

I received my Ph.D. in Mathematics at MIT, under the guidance of Shafi Goldwasser (and Yael Tauman Kalai). 2013-2015 I was a postdoctoral researcher at the Technion Israel Institute of Technology, hosted by Yuval Ishai. Summer 2013 I was a short-term postdoc at Cornell University (Cornell Tech NYC), hosted by Rafael Pass. Before MIT, I completed my undergraduate work in math at Caltech.

My research interests include cryptography, computer security, coding theory, algorithms, and other areas in the foundations of computer science.

Students:
Pierre Meyer (Ph.D.) (co-advised by Geoffroy Couteau)
Matan Hamilis (Ph.D.)
D'or Banon (MSc.) (co-advised by Ran Cohen)

Check out our survey (Jan 2022) on Function Secret Sharing, Homomorphic Secret Sharing, and Pseudorandom Correlation Generators: Survey

Publications

• Elette Boyle, Niv Gilboa, Matan Hamilis, Yuval Ishai, and Yaxin Tu
  Improved Constructions for Distributed Multi-Point Functions
  Oakland 2025 - IEEE Symposium on Security and Privacy.
  

  Elette Boyle, Niv Gilboa, Matan Hamilis, Yuval Ishai, and Ariel Nof
  Preprocessing for Life: Dishonest-Majority MPC with a Trusted or Untrusted Dealer
  Oakland 2025 - IEEE Symposium on Security and Privacy.
  

  This paper presents a new protocol for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client's string. A web-browser vendor, for instance, can use our protocol to figure out which homepages are popular, without learning any user's homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients.
  
  Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.
  
  In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.

  Elette Boyle, Lisa Kohl, Zhe Li, and Peter Scholl
  Direct FSS Constructions for Branching Programs and More from PRGs with Encoded-Output Homomorphism
  Asiacrypt 2024 - International Conference on the Theory and Applications of Cryptology and Information Security.
  [Abstract] [PDF]

  Function secret sharing (FSS) for a class F allows to split a secret function f into (succinct) secret shares f_0, f_1, such that for all x in {0,1}^n it holds f_0(x)-f_1(x)=f(x). FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class F translates to richness in the application. Unfortunately, concretely efficient FSS constructions are only known for very limited function classes.
  
  In this work we introduce the notion of pseudorandom generators with encoded-output homomorphism (EOH-PRGs), and give direct FSS constructions for bit-fixing predicates, branching programs and more based on this primitive. Further, we give constructions of FSS for deterministic finite automata (DFAs) from a KDM secure variant of EOH-PRGs.
  
  

  • New abstractions. Following the work of Alamati et al. (EUROCRYPT '19), who classify minicrypt primitives with algebraic structure and their applications, we capture the essence of our FSS constructions in the notion of EOH-PRG, paving the road towards future efficiency improvements via new instantiations of this primitive. The abstraction of EOH-PRG and its instantiations may be of independent interest, as it is an approximate substitution of an ideal homomorphic PRG.
  • Better efficiency. We show that EOH-PRGs can be instantiated from LWE and a small-exponent variant of the DCR assumption. A theoretical analysis of our instantiations suggest efficiency improvements over the state of the art both in terms of key size and evaluation time: We show that our FSS instantiations lead to smaller key sizes, improving over previous constructions by a factor of 3.5 and more. While for bit-fixing predicates our FSS constructions show comparable or mildly improved run time (depending on the instantiation), we achieve considerable improvements for branching programs by avoiding the expensive generic transformation via universal circuits, shaving off a factor of w and more in the number of abstract operations, where w corresponds to an upper bound on the width of the underlying class of branching programs.
  • New constructions. We show that our instantiations of EOH-PRGs additionally support a form of KDM-security, without requiring an additional circular-security assumption. Based on this, we give the first FSS construction for DFAs which supports the evaluation of inputs of a-priori unbounded length without relying on FHE.
  • Applications. We outline applications of our FSS constructions including pattern matching with wild cards, image matching, nearest neighbor search and regular expression matching.

  Amit Agarwal, Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Mahimna Kelkar, and Yiping Ma
  Secure Sorting and Selection via Function Secret Sharing
  CCS 2024 - ACM Conference on Computer and Communications Security.
  [Abstract]

  We revisit the problem of concretely efficient secure computation of sorting and selection (e.g., maximum, median, or top-k) on secret-shared data, focusing on the case of security against a single semi-honest party. Previous solutions either have a high communication overhead or many rounds of interaction, even when allowing input-independent preprocessing.
  
  We propose a suite of 2-party and 3-party offline-online protocols that exploit the efficient aggregation feature of function secret sharing to minimize the online communication and rounds. In particular, most of our protocols are optimal in terms of both online communication and online rounds up to small constant factors.
  
  We compare the performance of our protocols with prior works for different input parameters (number of items, bit length of items, batch size) and system parameters (CPU cores, network) and obtain up to 14x improvement in online running time under some settings

  D'or Banoun, Elette Boyle, and Ran Cohen
  Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond
  ITC 2024 - Conference on Information-Theoretic Cryptography.
  [Abstract] [PDF]

  Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the network topology from within a given class of graphs. Although broadcast is a privacy-free task, it is known that THB for certain graph classes necessitates computational assumptions, even against "honest but curious" adversaries, and even given a single corrupted party. Recent works have tried to understand when THB can be obtained with information-theoretic (IT) security (without cryptography or setup assumptions) as a function of properties of the corresponding graph class.
  
  We revisit this question through a case study of the class of wheel graphs and their subgraphs. The nth wheel graph is established by connecting n nodes who form a cycle with another "center" node, thus providing a natural extension that captures and enriches previously studied graph classes in the setting of IT-THB.
  
  We present a series of new findings in this line. We fully characterize feasibility of IT-THB for any class of subgraphs of the wheel each possessing an embedded star (i.e., a well-defined center connected to all other nodes). Our characterization provides evidence that IT-THB feasibility may correlate with a more fine-grained degree structure -- as opposed to pure connectivity -- of the corresponding graphs. We provide positive results achieving perfect IT-THB for new graph classes, including ones where the number of nodes is unknown. Further, we provide the first feasibility of IT-THB on non-degenerate graph-classes with t > 1 corruptions, for the class of friendship graphs (Erdos, Renyi, Sos'66).

  Amit Agarwal, Elette Boyle, Niv Gilboa, Yuval Ishai, Mahimna Kelkar, and Yiping Ma
  Compressing Unit-Vector Correlations via Sparse Pseudorandom Generators
  CRYPTO 2024 - International Conference on Cryptology.
  [Abstract]

  A unit-vector (UV) correlation is an additive secret-sharing of a vector of length B that contains 1 in a secret random position and 0s elsewhere. UV correlations are a useful resource for many cryptographic applications, including low-communication secure multiparty computation and multi-server private information retrieval. However, current practical methods for securely generating UV correlations involve a significant communication cost per instance, and become even more expensive when requiring security against malicious parties.
  
  In this work, we present a new approach for constructing a pseudorandom correlation generator (PCG) for securely generating n independent instances of UV correlations of any polynomial length B. Such a PCG compresses the n UV instances into correlated seeds whose length is sublinear in the description size n*log B. Our new PCGs apply in both the honest-majority and dishonest-majority settings, and are based on a variety of assumptions. In particular, in the honest-majority case they only require "unstructured" assumptions. Our PCGs give rise to secure end-to-end protocols for generating n instances of UV correlations with o(n) bits of communication. This applies even to an authenticated variant of UV correlations, which is useful for security against malicious parties. Unlike previous theoretical solutions, some instances of our PCGs offer good concrete efficiency.
  
  Our technical approach is based on combining a low-degree sparse pseudorandom generator, mapping a sparse seed to a pseudorandom sparse output, with homomorphic secret sharing for low-degree polynomials. We then reduce such sparse PRGs to local PRGs over large alphabets, and explore old and new approaches for maximizing the stretch of such PRGs while minimizing their locality.
  
  Finally, towards further compressing the PCG seeds, we present a new PRG-based construction of a multiparty distributed point function (DPF), whose outputs are degree-1 Shamir-shares of a secret point function. This result is independently motivated by other DPF applications.

  Elette Boyle, Ilan Komargodski, and Neekon Vafa
  Memory Checking Requires Logarithmic Overhead
  STOC 2024 - ACM Symposium on Theory of Computing.
  [Abstract] [PDF]

  We study the complexity of memory checkers with computational security and prove the first general tight lower bound.
  
  Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity O(log n / loglog n) and local space proportional to a computational security parameter, assuming one-way functions, where n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC '09) showed that for a restricted class of "deterministic and non-adaptive" memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem.
  
  In this work, we fully resolve the complexity of memory checkers by showing that any construction with local space p and query complexity q must satisfy p >= n / (log n)^O(q). This implies, as a special case, that q >= Omega( log n/ loglog n) in any scheme, assuming that p <= n^{1-eps} for eps>0. The bound applies to any scheme with computational security, completeness 2/3, and inverse polynomial in n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity q_r and write complexity q_w differ. For instance, we show the tight bound that if q_r=O(1) and p <= n^{1-eps} for eps>0, then q_w >= n^{Omega(1)}. This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off.
  
  Our proof is via a delicate compression argument showing that a "too good to be true" memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.

  Eden Aldema Tshuva, Elette Boyle, Ran Cohen, Tal Moran, Rotem Oshman
  Locally Verifiable Distributed SNARGs
  TCC 2023 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded.
  
  In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributed SNARGs (LVD-SNARGs), which are an analog of SNARGs for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms).
  
  We give two LVD-SNARG constructions: the first allows us to succinctly certify any network property in P, using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for NP (BARGs) and on RAM-SNARGs, which have recently been shown to be constructible from standard cryptographic assumptions.

  Erica Blum, Elette Boyle, Ran Cohen, and Chen-Da Liu-Zhang
  Communication Lower Bounds for Cryptographic Broadcast Protocols
  DISC 2023 - The International Symposium on Distributed Computing.
  Invited to Distributed Computing journal.
  [Abstract] [PDF]

  Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even in the face of malicious parties who collude to attack the protocol. In the honest-majority setting, a fruitful line of work harnessed randomization and cryptography to achieve low-communication broadcast protocols with sub-quadratic total communication and with "balanced" sub-linear communication cost per party.
  
  However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on the protocol of Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved even using randomization and cryptography. On the other hand, the only nontrivial omega(n) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages.
  
  We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound.

  • Static adversary. We demonstrate a tradeoff between resiliency and communication for randomized protocols secure against n-o(n) static corruptions. For example, Omega(n polylog(n)) messages are needed when the number of honest parties is n/polylog(n); Omega(n * sqrt{n}) messages are needed for O(sqrt{n}) honest parties; and Omega(n^2) messages are needed for O(1) honest parties. Complementarily, we demonstrate broadcast with O(n * polylog(n)) total communication and balanced polylog(n) per-party cost, facing any constant fraction of static corruptions.
  • Weakly adaptive adversary. Our second bound considers n/2 + k corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to k other parties. Our bound implies limitations on the feasibility of balanced low-communication protocols: For example, ruling out broadcast facing 51% corruptions, in which all non-sender parties have sublinear communication locality.

  Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai
  Arithmetic Sketching
  CRYPTO 2023 - International Conference on Cryptology.
  [Abstract] [PDF]

  This paper introduces arithmetic sketching, an abstraction of a primitive used in several previous works to achieve lightweight, low-communication zero-knowledge verification of secret-shared vectors. An arithmetic sketching scheme for a language L in F^n consists of (1) a randomized linear function compressing a long input x to a short "sketch," and (2) a small arithmetic circuit that accepts the sketch if and only if x is in L, up to some small error. Since multiplications are the dominant cost in protocols for computation on secret-shared, encrypted, and committed data, arithmetic sketching schemes give rise to lightweight protocols in each of these settings.
  
  Beyond the formalization of arithmetic sketching, our contributions are:

  • A general framework for constructing arithmetic sketching schemes from algebraic varieties. This framework unifies schemes from prior work and gives rise to schemes for useful new languages and with improved soundness error.
  • The first arithmetic sketching schemes for languages of sparse vectors: vectors with bounded Hamming weight, bounded L_1 norm, and vectors whose few non-zero values satisfy a given predicate.
  • A method for "compiling" any arithmetic sketching scheme for a language L into a low-communication malicious-secure multi-server protocol for securely testing that a client-provided secret-shared vector is in L.

  
  We also prove the first nontrivial lower bounds showing limits on the sketch size for certain languages (e.g., vectors of Hamming-weight one) and proving the non-existence of arithmetic sketching schemes for others (e.g., the language of all vectors that contain a specific value).

  Elette Boyle, Geoffroy Couteau, and Pierre Meyer
  Sublinear-Communication Secure Multiparty Computation Does Not Require FHE
  Advances in Cryptology - EUROCRYPT 2023.
  [Abstract] [PDF]

  Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. Significant advances have been made affirmatively answering this question within the two-party setting, based on a variety of structures and hardness assumptions. In contrast, in the multi-party setting, only one general approach is known: using Fully Homomorphic Encryption (FHE). This remains the state of affairs even for just three parties, with two corruptions.
  
  We present a framework for achieving secure sublinear-communication (N + 1)-party computation, building from a particular form of Function Secret Sharing for only N parties. In turn, we demonstrate implications to sublinear secure computation for various function classes in the 3-party and 5-party settings based on an assortment of assumptions not known to imply FHE.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl
  Oblivious Transfer with Constant Computational Overhead
  Advances in Cryptology - EUROCRYPT 2023.
  [Abstract] [PDF]

  The computational overhead of a cryptographic task is the asymptotic ratio between the computational cost of securely realizing the task and that of realizing the task with no security at all.
  
  Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2008) showed that secure two-party computation of Boolean circuits can be realized with constant computational overhead, independent of the desired level of security, assuming the existence of an oblivious transfer (OT) protocol and a local pseudorandom generator (PRG). However, this only applies to the case of semi-honest parties. A central open question in the area is the possibility of a similar result for malicious parties. This question is open even for the simpler task of securely realizing many instances of a constant-size function, such as OT of bits.
  
  We settle the question in the affirmative for the case of OT, assuming: (1) a standard OT protocol, (2) a slightly stronger "correlation-robust" variant of a local PRG, and (3) a standard sparse variant of the Learning Parity with Noise (LPN) assumption. An optimized version of our construction requires fewer than 100 bit operations per party per bit-OT. For 128-bit security, this improves over the best previous protocols by 1-2 orders of magnitude.
  
  We achieve this by constructing a constant-overhead pseudorandom correlation generator (PCG) for the bit-OT correlation. Such a PCG generates N pseudorandom instances of bit-OT by locally expanding short, correlated seeds. As a result, we get an end-to-end protocol for generating N pseudorandom instances of bit-OT with o(N) communication, O(N) computation, and security that scales sub-exponentially with N.
  
  Finally, we present applications of our main result to realizing other secure computation tasks with constant computational overhead. These include protocols for general circuits with a relaxed notion of security against malicious parties, protocols for realizing N instances of natural constant- size functions, and reducing the main open question to a potentially simpler question about fault- tolerant computation.

  Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, and Gal Yehuda
  On Low-End Obfuscation and Learning
  ITCS 2023 - Innovations in Theoretical Computer Science.
  [Abstract]

  Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of "low-end" obfuscation, focusing on simpler representation models and information-theoretic notions of security. We obtain the following results.

  • Positive results via "white-box" learning. We present a general technique for obtaining perfect indistinguishability obfuscation from exact learning algorithms that are given restricted access to the representation of the input function. We demonstrate the usefulness of this approach by obtaining simple obfuscation for decision trees and multilinear read-k arithmetic formulas.
  • Negative results via PAC learning. A proper obfuscation scheme obfuscates programs from a class C by programs from the same class. Assuming the existence of one-way functions, we show that there is no proper indistinguishability obfuscation scheme for k-CNF formulas for any constant k >= 3; in fact, even obfuscating 3-CNF by k-CNF is impossible. This result applies even to computationally secure obfuscation, and makes an unexpected use of PAC learning in the context of negative results for obfuscation.
  • Separations. We study the relations between different information-theoretic notions of indistinguishability obfuscation, giving cryptographic evidence for separations between them.

  Elette Boyle, Geoffroy Couteau, and Pierre Meyer
  Sublinear Secure Computation from New Assumptions
  TCC 2022 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size.
  
  We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings:

  • Circuit size. We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular "decomposability" property. In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility: from Quadratic Residuosity (QR) together with polynomial-noise-rate Learning Parity with Noise (LPN).
    Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing.
  • Input size. We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size n. Previous constructions from CDH required communication Omega(n). In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor Kolobov
  Programmable Distributed Point Functions
  CRYPTO 2022 - International Conference on Cryptology.
  [Abstract] [PDF]

  A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret unit vector across two or more parties. Despite growing ubiquity within applications and notable research efforts, the best 2-party DPF construction to date remains the tree-based construction from (Boyle et al, CCS'16), with no significantly new approaches since.
  
  We present a new framework for 2-party DPF construction, which applies in the setting of feasible (polynomial-size) domains. This captures in particular all DPF applications in which the keys are expanded to the full domain. Our approach is motivated by a strengthened notion we put forth, of programmable DPF (PDPF): in which a short, input-independent "offline" key can be reused for sharing many point functions.

  • PDPF from OWF: We construct a PDPF for feasible domains from the minimal assumption that one-way functions exist, where the second "online" key size is polylogarithmic in the domain size N.

  Our approach offers multiple new efficiency features and applications:

  • Privately puncturable PRFs: Our PDPF gives the first OWF-based privately puncturable PRFs (for feasible domains) with sublinear keys.
  • O(1)-round distributed DPF Gen: We obtain a (standard) DPF with polylog-size keys that admits an analog of Doerner-shelat (CCS'17) distributed key generation, requiring only O(1) rounds (versus log N).
  • PCG with 1 short key: Compressing useful correlations for secure computation, where one key is of minimal size. This provides up to exponential communication savings in some application scenarios.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl
  Correlated Pseudorandomness from Expand-Accumulate Codes
  CRYPTO 2022 - International Conference on Cryptology.
  [Abstract] [PDF]

  A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost.
  
  We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions:

  • Competitive concrete efficiency backed by provable security against relevant classes of attacks;
  • An offline-online mode that combines near-optimal cache-friendliness with simple parallelization;
  • Concretely efficient extensions to pseudorandom correlation functions, which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations.

  
  To further improve the concrete computational cost, we propose a method for speeding up a full-domain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor Kolobov
  Information-Theoretic Distributed Point Functions
  ITC 2022 - Conference on Information-Theoretic Cryptography.
  [Abstract] [PDF]

  A distributed point function (DPF) (Gilboa-Ishai EC'14) is a cryptographic primitive that enables compressed additive secret-sharing of a secret unit vector across two or more parties. DPFs support a wide range of cryptographic applications, including advanced forms of Private Information Retrieval, and beyond. Up to now, the question of construction of DPF has only been considered in the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority.
  
  We present the first statistically private 3-party DPF for domain size N with subpolynomial key size N^{o(1)}. We also present a similar perfectly private 4-party DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity (and better potential for "MPC friendliness" in the sense of efficient distributed key generation), all while having comparable communication complexity for moderate-sized parameters.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof
  Secure Multiparty Computation with Sublinear Preprocessing
  Advances in Cryptology - EUROCRYPT 2022.
  [Abstract]

  A common technique for enhancing the efficiency of secure multiparty computation (MPC) with dishonest majority is via preprocessing: In an offline phase, parties engage in an input-independent protocol to securely generate correlated randomness. Once inputs are known, the correlated randomness is consumed by a "non-cryptographic" and highly efficient online protocol.
  
  The correlated randomness in such protocols traditionally comes in two flavors: multiplication triples (Beaver, Crypto '91), which suffice for security against semi-honest parties, and authenticated multiplication triples (Bendlin et al., Eurocrypt '11, Damgard et al., Crypto '12) that yield efficient protocols against malicious parties. Recent constructions of pseudorandom correlation generators (Boyle et al., Crypto '19, '20) enable concretely efficient secure generation of multiplication triples with sublinear communication complexity. However, these techniques do not efficiently apply to authenticated triples, except in the case of secure two-party computation of arithmetic circuits over large fields.
  
  In this work, we propose the first concretely efficient approach for (malicious) MPC with preprocessing in which the offline communication is sublinear in the circuit size. More specifically, the offline communication scales with the square root of the circuit size. From a feasibility point of view, our protocols can make use of any secure protocol for generating (unauthenticated) multiplication triples together with any additive homomorphic encryption. We propose concretely efficient instantiations (based on strong but plausible "linear-only" assumptions) from existing homomorphic encryption schemes and pseudorandom correlation generators.
  
  Our technique is based on a variant of a recent protocol of Boyle et al. (Crypto '21) for MPC with preprocessing. As a result, our protocols inherit the succinct correlated randomness feature of the latter protocol.

  Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein
  Locality-Preserving Hashing for Shifts with Connections to Cryptography
  ITCS 2022 - Innovations in Theoretical Computer Science.
  [Abstract] [PDF]

  Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically close to us can decrypt? To solve this kind of problems, we introduce and study a new type of hash functions for finding shifts in sublinear time. A function h : {0,1}^n -> Z_n is a (d,delta) locality-preserving hash function for shifts (LPHS) if: (1) h can be computed by (adaptively) querying d bits of its input, and (2) Pr[h(x) neq h(x << 1)+1] <= delta, where x is random and << 1 denotes a cyclic shift by one bit to the left. We make the following contributions.
  
  

  • Near-optimal LPHS via Distributed Discrete Log. We establish a general two-way connection between LPHS and algorithms for distributed discrete logarithm in the generic group model. Using such an algorithm of Dinur et al. (Crypto 2018), we get LPHS with near-optimal error of delta = ~O(1/d^2). This gives an unusual example for the usefulness of group-based cryptography in a post-quantum world. We extend the positive result to non-cyclic and worst-case variants of LPHS.
  • Multidimensional LPHS. We obtain positive and negative results for a multidimensional extension of LPHS, making progress towards an optimal 2-dimensional LPHS.
  • Applications. We demonstrate the usefulness of LPHS by presenting cryptographic and algorithmic applications. In particular, we apply multidimensional LPHS to obtain an efficient "packed" implementation of homomorphic secret sharing and a sublinear-time implementation of location-sensitive encryption whose decryption requires a significantly overlapping view.

  Fabrice Benhamouda, Elette Boyle, Niv Gilboa, Shai Halevi, Yuval Ishai, and Ariel Nof
  Generalized Pseudorandom Secret Sharing and Efficient Straggler-Resilient Secure Computation
  TCC 2021 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  Secure multiparty computation (MPC) enables n parties, of which up to t may be corrupted, to perform joint computations on their private inputs while revealing only the outputs. Optimizing the asymptotic and concrete costs of MPC protocols has become an important line of research. Much of this research focuses on the setting of an honest majority, where n >= 2t + 1, which gives rise to concretely efficient protocols that are either information-theoretic or make a black-box use of symmetric cryptography. Efficiency can be further improved in the case of a strong honest majority, where n > 2t + 1.
  
  Motivated by the goal of minimizing the communication and latency costs of MPC with a strong honest majority, we make two related contributions.
  

  • Generalized pseudorandom secret sharing (PRSS). Linear correlations serve as an important resource for MPC protocols and beyond. PRSS enables secure generation of many pseudorandom instances of such correlations without interaction, given replicated seeds of a pseudorandom function. We extend the PRSS technique of Cramer et al. (TCC 2005) for sharing degree-d polynomials to new constructions leveraging a particular class of combinatorial designs. Our constructions yield a dramatic efficiency improvement when the degree d is higher than the security threshold t, not only for standard degree-d correlations but also for several useful generalizations. In particular, correlations for locally converting between slot configurations in “share packing” enable us to avoid the concrete overhead of prior works.
  • Cheap straggler resilience. In reality, communication is not fully synchronous: protocol executions suffer from variance in communication delays and occasional node or message- delivery failures. We explore the benefits of PRSS-based MPC with a strong honest majority toward robustness against such failures, in turn yielding improved latency delays. In doing so we develop a novel technique for defending against a subtle “double-dipping” attack, which applies to the best existing protocols, with almost no extra cost in communication or rounds.

  
  Combining the above tools requires further work, including new methods for batch verification via distributed zero-knowledge proofs (Boneh et al., CRYPTO 2019) that apply to packed secret sharing. Overall, our work demonstrates new advantages of the strong honest majority setting, and introduces new tools--in particular, generalized PRSS--that we believe will be of independent use within other cryptographic applications.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof
  Sublinear GMW-Style Compiler for MPC with Preprocessing
  CRYPTO 2021 - International Conference on Cryptology.
  [Abstract] [PDF]

  We consider the efficiency of protocols for secure multiparty computation (MPC) with a dishonest majority. A popular approach for the design of such protocols is to employ preprocessing. Before the inputs are known, the parties generate correlated secret randomness, which is consumed by a fast and "information-theoretic" online protocol.
  
  A powerful technique for securing such protocols against malicious parties uses homomorphic MACs to authenticate the values produced by the online protocol. Compared to a baseline protocol, which is only secure against semi-honest parties, this involves a significant increase in the size of the correlated randomness, by a factor of up to a statistical security parameter. Different approaches for partially mitigating this extra storage cost come at the expense of increasing the online communication.
  
  In this work we propose a new technique for protecting MPC with preprocessing against malicious parties. We show that for circuit evaluation protocols that satisfy mild security and structural requirements, that are met by many standard protocols with semi-honest security, the extra additive storage and online communication costs are both logarithmic in the circuit size. This applies to Boolean circuits and to arithmetic circuits over fields or rings, and to both information-theoretic and computationally secure protocols. Our protocol can be viewed as a sublinear information-theoretic variant of the celebrated "GMW compiler" that applies to MPC with preprocessing.
  
  Our compiler makes a novel use of the techniques of Boneh et al. (Crypto 2019) for sublinear distributed zero knowledge, which were previously only used in the setting of honest-majority MPC.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl
  Low-Complexity Weak Pseudorandom Functions in AC0[Mod2]
  CRYPTO 2021 - International Conference on Cryptology.
  [Abstract]

  A weak pseudorandom function (WPRF) is a keyed function f_k: {0,1}^n -> {0,1} such that, for a random key k, a collection of samples (x, f_k(x)), for uniformly random inputs x, cannot be efficiently distinguished from totally random input-output pairs (x,y). We study WPRFs in AC0[Mod2], the class of functions computable by AC0 circuits with parity gates, making the following contributions.
  
  

  • WPRF by sparse polynomials. We propose the first WPRF candidate that can be computed by sparse multivariate polynomials over F_2. We prove that it has subexponential security against linear and algebraic attacks.
  
  
  • WPRF in AC0[Mod2]. We study the existence of WPRFs computed by AC0 circuits over parity gates. We propose a modified version of a previous WPRF candidate of Akavia et al., and prove that it resists the algebraic attacks that were used by Bogdanov and Rosen (ECCC 2017) to break the original candidate in quasipolynomial time. We give evidence against the possibility of using public parity gates and relate this question to other conjectures.
  
  
  • Between Lapland and Cryptomania. We show that WPRFs in AC0[Mod2] imply a variant of the Learning Parity with Noise (LPN) assumption. We further show that WPRFs in a subclass of AC0[Mod2] that includes a recent WPRF candidate by Boyle et al. (FOCS 2020) imply, under a seemingly weak additional conjecture, public-key encryption.

  Elette Boyle, Ran Cohen, and Aarushi Goel
  Breaking the O(sqrt n)-Bit Barrier: Byzantine Agreement with Polylog Bits Per-Party
  PODC 2021 - ACM Symposium on Principles of Distributed Computing.
  [Abstract] [PDF]

  Byzantine agreement (BA), the task of n parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is O~(1) bits per party, but some parties must send Omega(n) bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating O~(sqrt n).
  
  In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only O~(1) bits? Our contributions in this line are as follows:
  
  

  • We define a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing O~(1) balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions.
  • The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends o(n) messages.
  • We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product).

  
  Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with O~(1) balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

  Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee
  Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation
  Advances in Cryptology - EUROCRYPT 2021.
  [Abstract] [PDF]

  Recently Boyle et al. (TCC 2019) proposed a new approach for secure computation in the preprocessing model building on function secret sharing (FSS). This approach can be used to realize any circuit containing gates that admit efficient FSS schemes. In this work, we make the following three technical contributions:
  
  Improved Key Size. The complexity of the preprocessing phase directly depends on the FSS key size. We improve the size of FSS keys for several existing FSS constructions through two important steps. First, we present a roughly 4x reduction in FSS key size for the Distributed Comparison Function (DCF), i.e. (f_a(x) = b for all x < a and 0, otherwise). Second, prior FSS schemes for many important function classes are obtained via reductions to multiple instances of DCF; for example, 2 instances for interval containment and 2m for splines with m pieces. We significantly improve these reductions for public intervals and obtain optimal FSS schemes, i.e., through a single instance of DCF, thereby reducing the key sizes by up to 6-22x for commonly used functions in mixed-mode secure computation such as ReLU and sigmoid.
  
  FSS for New Function Families. We present the first constructions of FSS schemes for arithmetic and logical right shift, as well as for bit- decomposition, where the output bits must be secret shared in a larger ring. These functions are crucial for many applications such as fixed-point arithmetic and machine learning.
  
  FSS for Fixed-Point Arithmetic and Barrier. One of the important functions in the realization of secure fixed-point arithmetic is that of multiply-then-truncate. While our work shows how to obtain a construction for this function in 2 rounds using sequential calls to FSS schemes for multiply and shift, we demonstrate a barrier towards improving this via FSS beyond what we achieve. Specifically, we show that a 1-round solution would require settling a major open problem in the area of FSS: namely, building an FSS for the class of bit-conjunction functions based on only symmetric-key cryptographic assumptions.

  Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai
  Lightweight Techniques for Private Heavy Hitters
  Oakland 2021 - IEEE Symposium on Security and Privacy.
  [Abstract] [PDF]

  This paper presents a new protocol for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client's string. A web-browser vendor, for instance, can use our protocol to figure out which homepages are popular, without learning any user's homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients.
  
  Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.
  
  In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.

  Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, and Tal Moran
  Topology-Hiding Communication from Minimal Assumptions
  TCC 2020 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation (THC) (Moran et al. TCC'15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party.
  
  In this work we investigate the minimal assumptions required for topology-hiding communication--both Broadcast or Anonymous Broadcast (where the broadcaster's identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility may depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or neighbors' distance to the broadcaster.
  
  An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof
  Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs
  Asiacrypt 2020 - International Conference on the Theory and Applications of Cryptology and Information Security.
  [Abstract] [PDF]

  Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output. Protocols with full security (also known as guaranteed output delivery) in particular protect against denial-of-service attacks, guaranteeing that honest parties receive a correct output. This feature can be realized in the presence of an honest majority, and significant research effort has gone toward attaining full security with good asymptotic and concrete efficiency.
  
  We present an efficient protocol for any constant number of parties n, with full security against t < n/2 corrupted parties, that makes a black-box use of a pseudorandom generator. Our protocol evaluates an arithmetic circuit C over a finite ring R (either a finite field or R = Z_{2^k}) with communication complexity of 3t S + o(S) R-elements per party, where S is the 2t+1 number of multiplication gates in C (namely, < 1.5 elements per party per gate). This matches the best known protocols for the semi-honest model up to the sublinear additive term. For a small number of parties n, this improves over a recent protocol of Goyal et al. (ePrint 2020) by a constant factor for circuits over large fields, and by at least an Omega(log n) factor for Boolean circuits or circuits over rings.
  
  Our protocol provides new methods for applying the sublinear-communication distributed zero-knowledge proofs of Boneh et al. (Crypto 2019) for compiling semi-honest protocols into fully secure ones, in the more challenging case of t > 1 corrupted parties. Our protocol relies on replicated secret sharing to minimize communication and simplify the mechanism for achieving full security. This results in computational cost that scales exponentially with n.
  
  Our main protocol builds on a new honest-majority protocol for verifying the correctness of multiplication triples by making a general use of distributed zero-knowledge proofs. While the protocol only achieves the weaker notion of security with abort, it applies to any linear secret-sharing scheme and provides a conceptually simpler, more general, and more efficient alternative to previous protocols from the literature. In particular, it can be combined with the Fiat-Shamir heuristic to simultaneously achieve logarithmic communication complexity and constant round complexity.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl
  Correlated Pseudorandom Functions from Variable-Density LPN
  FOCS 2020 - IEEE Symposium on Foundations of Computer Science.
  [Abstract] [PDF]

  Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function fk such that for a suitable joint key distribution (k0, k1), the outputs (fk0(x), fk1(x)) are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability holds not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys.
  
  We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VD-LPN). We also present several cryptographic applications that motivate our efficient PCF constructions.
  
  The VD-LPN assumption we introduce is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in (depth-2) AC0[⊕] that can be conjectured to have sub-exponential, or even fully exponential, security. This is contrasted with the quasi-polynomial security of previous (higher-depth) AC0[⊕] candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VD-LPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl
  Efficient Pseudorandom Correlation Generators from Ring-LPN
  CRYPTO 2020 - International Conference on Cryptology.
  [Abstract] [PDF]

  Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better asymptotic and concrete efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated very efficiently using a cheap, one-time interaction, followed by only ``silent'' local computation. This is achieved via a pseudorandom correlation generator (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for useful correlations, such as random oblivious transfer and vector-OLE, together with efficient protocol to distribute the PCG seed generation, from the LPN assumption. Similar constructions for other useful correlations had poor asymptotic and concrete efficiency.
  
  In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Concretely, our PCGs can generate OLE correlations, authenticated Beaver triples, matrix product correlations, and other types of useful correlations over large fields. Our PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.

  Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Desphande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Vasudevan
  Cryptography from Information Loss
  ITCS 2020 - Innovations in Theoretical Computer Science.
  [Abstract] [PDF]

  Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is "lossy" reductions, where the reduction loses some information about the input instance. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into "useful" hardness, namely cryptography.
  
  Our first, conceptual, contribution is a definition of lossy reductions in the language of mutual information. Roughly speaking, our definition says that a reduction C is t-lossy if, for any distribution X over its inputs, the mutual information I(X;C(X)) <= t. Our treatment generalizes a variety of seemingly related but distinct notions such as worst-case to average-case reductions, randomized encodings (Ishai and Kushilevitz, FOCS 2000), homomorphic computations (Gentry, STOC 2009), and instance compression (Harnik and Naor, FOCS 2006). We then proceed to show several consequences of lossy reductions:
  
  1. We say that a language L has an f-reduction to a language L' for a Boolean function f if there is a (randomized) polynomial-time algorithm C that takes an m-tuple of strings X = (x1,...,xm), with each xi \in {0,1}^n, and outputs a string z such that with high probability, L'(z) = f(L(x1), L(x2), . . . , L(xm)). Suppose a language L has an f-reduction C to L' that is t-lossy. Our first result is that one-way functions exist if L is worst-case hard and one of the following conditions holds:

  • f is the OR function, t <= m/100, and L' is the same as L
  • f is the Majority function, and t <= m/100
  • f is the OR function, t <= O(m log n), and the reduction has no error

  This improves on the implications that follow from combining (Drucker, FOCS 2012) with (Ostrovsky and Wigderson, ISTCS 1993) that result in auxiliary-input one-way functions.
  
  2. Our second result is about the stronger notion of t-compressing f-reductions -- reductions that only output t bits. We show that if there is an average-case hard language L that has a t-compressing Majority reduction to some language for t = m/100, then there exist collision-resistant hash functions. This improves on the result of (Harnik and Naor, STOC 2006), whose starting point is a cryptographic primitive (namely, one-way functions) rather than average-case hardness, and whose assumption is a compressing OR-reduction of SAT (which is now known to be false unless the polynomial hierarchy collapses).
  
  Along the way, we define a non-standard one-sided notion of average-case hardness, which is the notion of hardness used in the second result above, that may be of independent interest.

  Elette Boyle, Justin Holmgren, and Mor Weiss
  Permuted Puzzles and Cryptographic Hardness
  TCC 2019 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  A permuted puzzle problem is defined by a pair of distributions D0, D1 over \Sigma^n. The problem is to distinguish samples from D0, D1, where the symbols of each sample are permuted by a single secret permutation \pi of [n].
  
  The conjectured hardness of specific instances of permuted puzzle problems was recently used to obtain the first candidate constructions of Doubly Efficient Private Information Retrieval (DE-PIR) (Boyle et al. & Canetti et al., TCC'17). Roughly, in these works the distributions D0, D1 over \mathbb{F}^n are evaluations of either a moderately low-degree polynomial or a random function. This new conjecture seems to be quite powerful, and is the foundation for the first DE-PIR candidates, almost two decades after the question was first posed by Beimel et al. (CRYPTO'00). While permuted puzzles are a natural and general class of problems, their hardness is still poorly understood.
  
  We initiate a formal investigation of the cryptographic hardness of permuted puzzle problems. Our contributions lie in three main directions:
  
  

  • Rigorous formalization. We formalize a notion of permuted puzzle distinguishing problems, extending and generalizing the proposed permuted puzzle framework of Boyle et al. (TCC'17).
  
  
  • Identifying hard permuted puzzles. We identify natural examples in which a one-time permutation provably creates cryptographic hardness, based on "standard" assumptions. In these examples, the original distributions D0, D1 are easily distinguishable, but the permuted puzzle distinguishing problem is computationally hard. We provide such constructions in the random oracle model, and in the plain model under the Decisional Diffie-Hellman (DDH) assumption. We additionally observe that the Learning Parity with Noise (LPN) assumption itself can be cast as a permuted puzzle.
  
  
  • Partial lower bound for the DE-PIR problem. We make progress towards better understand- ing the permuted puzzles underlying the DE-PIR constructions, by showing that a toy version of the problem, introduced by Boyle et al. (TCC'17), withstands a rich class of attacks, namely those that distinguish solely via statistical queries.

  Elette Boyle, Niv Gilboa, and Yuval Ishai
  Secure Computation with Preprocessing via Function Secret Sharing
  TCC 2019 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al. (Crypto 2017), where our generalized variant uses FSS to achieve exponential efficiency improvement for useful types of gates.
  
  By instantiating this general approach with efficient PRG-based FSS schemes of Boyle et al. (Eurocrypt 2015, CCS 2016), we can implement useful nonlinear gates for equality tests, integer comparison, bit-decomposition and more with optimal online communication and with a relatively small amount of correlated randomness. We also provide a unified and simplified view of several existing protocols in the preprocessing model via the FSS framework.
  
  Our positive results provide a useful tool for secure computation tasks that involve secure integer comparisons or conversions between arithmetic and binary representations. These arise in the contexts of approximating real-valued functions, machine-learning classification, and more.
  
  Finally, we study the necessity of the FSS machinery we employ in the simple context of secure string equality testing. First, we show that any "online-optimal" secure equality protocol implies an FSS scheme for point functions, which in turn implies one-way functions. Then, we show that information-theoretic secure equality protocols with relaxed optimality requirements would follow from the existence of big families of "matching vectors." This suggests that proving strong lower bounds on the efficiency of such protocols would be difficult.

  Marshall Ball, Elette Boyle, Ran Cohen, Tal Malkin, and Tal Moran
  Is Information-Theoretic Topology-Hiding Computation Possible?
  TCC 2019 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. Existing THC protocols consider an adversary that may corrupt an arbitrary number of parties, and rely on cryptographic assumptions such as DDH.
  
  In this paper we address the question of whether information-theoretic THC can be achieved by taking advantage of an honest majority. In contrast to the standard MPC setting, this problem has remained open in the topology-hiding realm, even for simple "privacy-free" functions like broadcast and even when considering only semi-honest corruptions.
  
  We uncover a rich landscape of both positive and negative answers to the above question, showing that what types of graphs are used and how they are selected is an important factor in determining the feasibility of hiding topology information theoretically. In particular, our results include the following.

  • We show that topology-hiding broadcast (THB) on a line with four nodes, secure against a single semi-honest corruption, implies key agreement. This result extends to broader classes of graphs, e.g., THB on a cycle with two semi-honest corruptions.
  • On the other hand, we provide the first feasibility result for information-theoretic THC: for the class of cycle graphs, with a single semi-honest corruption.

  Given the strong impossibilities, we put forth a weaker definition of distributional-THC, where the graph is selected from some distribution (as opposed to worst-case).

  • We present a formal separation between the definitions, by showing a distribution for which information theoretic distributional-THC is possible, but even topology-hiding broadcast is not possible information-theoretically with the standard definition.
  • We demonstrate the power of our new definition via a new connection to adaptively secure low-locality MPC, where distributional-THC enables parties to "reuse" a secret low-degree communication graph even in the face adaptive corruptions.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl
  Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation
  CCS 2019 - ACM Conference on Computer and Communications Security.
  [Abstract] [PDF]

  We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known.
  
  Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base" oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions:

  • Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature.
  • Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds.
  • Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.

  Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof
  Practical Fully Secure Three-Party Computation via Sublinear Distributed Zero-Knowledge Proofs
  CCS 2019 - ACM Conference on Computer and Communications Security.
  [Abstract] [PDF]

  Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard set- tings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest adversary; however, a significant gap remains between these and protocols with stronger security against a malicious adversary.
  
  In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions:

  • Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits.
    Our protocol builds on recent techniques of Boneh et al. (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016).
    We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (non-linear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication for the entire circuit, while the computational overhead is dominated by roughly 30 multiplications per gate in the field F_{2^47}. In addition, we implemented and benchmarked the protocol for varied circuit sizes.
  • Full Security. We augment the 3PC protocol to further provide full security (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl
  Efficient Pseudorandom Correlation Generators: Silent OT Extension and More
  CRYPTO 2019 - International Conference on Cryptology.
  [Abstract] [PDF]

  Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight "non-cryptographic"' online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage.
  
  A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness.
  
  A concretely efficient PCG for Vector-OLE correlations was recently obtained by Boyle et al. (CCS 2018) based on variants of the learning parity with noise (LPN) assumption over large fields. In this work, we initiate a systematic study of PCGs and present concretely efficient constructions for several types of useful MPC correlations. We obtain the following main contributions:

  • PCG foundations. We give a general security definition for PCGs. Our definition suffices for any MPC protocol satisfying a stronger security requirement that is met by existing protocols. We prove that a stronger security requirement is indeed necessary, and justify our PCG definition by ruling out a stronger and more natural definition.
  • Silent OT extension. We present the first concretely efficient PCG for oblivious transfer correlations. Its security is based on a variant of the binary LPN assumption and any correlation-robust hash function. We expect it to provide a faster alternative to the IKNP OT extension protocol (Crypto '03) when communication is a bottleneck. We present several applications, including protocols for non-interactive zero-knowledge with bounded-reusable preprocessing from binary LPN, and concretely efficient related-key oblivious pseudorandom functions.
  • PCGs for simple 2-party correlations. We obtain PCGs for several other types of useful 2-party correlations, including (authenticated) one-time truth-tables and Beaver triples. While the latter PCGs are slower than our PCG for OT, they are still practically feasible. These PCGs are based on a host of assumptions and techniques, including specialized homomorphic secret sharing schemes and pseudorandom generators tailored to their structure.
  • Multiparty correlations. We obtain PCGs for multiparty correlations that can be used to make the online communication of MPC protocols scale linearly (instead of quadratically) with the number of parties.

  Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai
  Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs
  CRYPTO 2019 - International Conference on Cryptology.
  [Abstract] [PDF]

  We introduce and study the notion of fully linear probabilistically checkable proof systems. In such a proof system, the verifier can make a small number of linear queries that apply jointly to the input and a proof vector.
  
  Our new type of proof system is motivated by applications in which the input statement is not fully available to any single verifier, but can still be efficiently accessed via linear queries. This situation arises in scenarios where the input is partitioned or secret-shared between two or more parties, or alternatively is encoded using an additively homomorphic encryption or commitment scheme. This setting appears in the context of secure messaging platforms, verifiable outsourced computation, PIR writing, private computation of aggregate statistics, and secure multiparty computation (MPC). In all these applications, there is a need for fully linear proof systems with short proofs.
  
  While several efficient constructions of fully linear proof systems are implicit in the interactive proofs literature, many questions about their complexity are open. We present several new constructions of fully linear zero-knowledge proof systems with sublinear proof size for "simple" or "structured" languages. For example, in the non-interactive setting of fully linear PCPs, we show how to prove that an input vector x in F^n satisfies a single degree-2 equation with a proof of size O(sqrt{n}) and O(sqrt{n}) linear queries, which we show to be optimal. More generally, for languages that can be recognized by systems of constant-degree equations, we can reduce the proof size to O(log n) at the cost of O(log n) rounds of interaction.
  
  We use our new proof systems to construct new short zero-knowledge proofs on distributed and secret-shared data. These proofs can be used to improve the performance of many of the example systems mentioned above.
  
  Finally, we observe that zero-knowledge proofs on distributed data provide a general-purpose tool for protecting protocols for secure multiparty computation (MPC) against malicious parties. Applying our short fully linear PCPs to "natural" MPC protocols in the honest-majority setting, we can achieve unconditional protection against malicious parties with sublinear additive communication cost. We use this to improve the communication complexity of recent honest-majority MPC protocols. For instance, using any pseudorandom generator, we obtain a 3-party protocol for Boolean circuits in which the amortized communication cost is only one bit per AND gate per party (compared to 10 bits in the best previous protocol), matching the best known protocols for semi-honest adversaries.

  Elette Boyle, Lisa Kohl, and Peter Scholl
  Homomorphic Secret Sharing from Lattices Without FHE
  Advances in Cryptology - EUROCRYPT 2019.
  [Abstract] [PDF]

  Homomorphic secret sharing (HSS) is an analog of somewhat- or fully homomorphic encryption (S/FHE) to the setting of secret sharing, with applications including succinct secure computation, private manipulation of remote databases, and more. While HSS can be viewed as a relaxation of S/FHE, the only constructions from lattice-based assumptions to date build atop specific forms of threshold or multi-key S/FHE.
  
  In this work, we present new techniques directly yielding efficient 2-party HSS for polynomial-size branching programs from a range of lattice-based encryption schemes, without S/FHE. More concretely, we avoid the costly key-switching and modulus-reduction steps used in S/FHE ciphertext multiplication, replacing them with a new distributed decryption procedure for performing "restricted" multiplications of an input with a partial computation value. Doing so requires new methods for handling the blowup of "noise" in ciphertexts in a distributed setting, and leverages several properties of lattice-based encryption schemes together with new tricks in share conversion.
  
  The resulting schemes support a superpolynomial-size plaintext space and negligible correctness error, with share sizes comparable to SHE ciphertexts, but cost of homomorphic multiplication roughly one order of magnitude faster. Over certain rings, our HSS can further support some level of packed SIMD homomorphic operations. We demonstrate the practical efficiency of our scheme within two application settings, where we compare favorably with current best approaches: 2-server private database pattern-match queries, and secure 2-party computation of low-degree polynomials.

  Elette Boyle, Rio LaVigne, and Vinod Vaikuntanathan
  Adversarially Robust Property-Preserving Hash Functions
  ITCS 2019 - Innovations in Theoretical Computer Science.
  [Abstract] [PDF]

  Property-preserving hashing is a method of compressing a large input x into a short hash h(x) in such a way that given h(x) and h(y), one can compute a property P (x, y) of the original inputs. The idea of property-preserving hash functions underlies sketching, compressed sensing and locality-sensitive hashing.
  
  Property-preserving hash functions are usually probabilistic: they use the random choice of a hash function from a family to achieve compression, and as a consequence, err on some inputs. Traditionally, the notion of correctness for these hash functions requires that for every two inputs x and y, the probability that h(x) and h(y) mislead us into a wrong prediction of P (x, y) is negligible. As observed in many recent works (incl. Mironov, Naor and Segev, STOC 2008; Hardt and Woodruff, STOC 2013; Naor and Yogev, CRYPTO 2015), such a correctness guarantee assumes that the adversary (who produces the offending inputs) has no information about the hash function, and is too weak in many scenarios.
  
  We initiate the study of adversarial robustness for property-preserving hash functions, provide definitions, derive broad lower bounds due to a simple connection with communication complexity, and show the necessity of computational assumptions to construct such functions. Our main positive results are two candidate constructions of property-preserving hash functions (achieving different parameters) for the (promise) gap-Hamming property which checks if x and y are "too far" or "too close." Our first construction relies on generic collision-resistant hash functions, and our second on a variant of the syndrome decoding assumption on low-density parity check codes.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai
  Compressing Vector OLE
  CCS 2018 - ACM Conference on Computer and Communications Security.
  [Abstract] [PDF]

  Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits.
  
  A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a small number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE.
  
  We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and useful cryptographic correlation with good concrete efficiency. Our VOLE generator can be used as a general-purpose tool to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing.
  
  Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and noisy linear codes. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields, which resist known attacks with good concrete parameters. We provide several different constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

  Elette Boyle, Ran Cohen, Deepesh Data, and Pavel Hubáček
  Must the Communication Graph of MPC Protocols be an Expander?
  CRYPTO 2018 - International Conference on Cryptology.
  [Abstract] [PDF]

  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.

  Elette Boyle, Yuval Ishai, and Antigoni Polychroniadou
  Limits of Practical Sublinear Secure Computation
  CRYPTO 2018 - International Conference on Cryptology.
  [Abstract] [PDF]

  Secure computations on big data call for protocols that have sublinear communication complexity in the input length. While fully homomorphic encryption (FHE) provides a general solution to the problem, employing it on a large scale is currently quite far from being practical. This is also the case for secure computation tasks that reduce to weaker forms of FHE such as "somewhat homomorphic encryption" or single-server private information retrieval (PIR).
  
  Quite unexpectedly, Aggarwal, Mishra, and Pinkas (Eurocrypt 2004), Brickell and Shmatikov (Asiacrypt 2005), and shelat and Venkitasubramaniam (Asiacrypt 2015) have shown that in several natural instances of secure computation on big data, there are practical sublinear communication protocols that only require sublinear local computation and minimize the use of expensive public-key operations. This raises the question of whether similar protocols exist for other natural problems.
  
  In this paper we put forward a framework for separating "practical" sublinear protocols from "impractical" ones, and establish a methodology for identifying "provably hard" big-data problems that do not admit practical protocols. This is akin to the use of NP-completeness to separate hard algorithmic problems from easy ones. We show that while the previous protocols of Aggarwal et al., Brickell and Shmatikov, and shelat and Venkitasubramaniam are indeed classified as being "practical" in this framework, slight variations of the problems they solve and other natural computational problems on big data are hard.
  
  Our negative results are established by showing that the problem at hand is "PIR-hard" in the sense that any secure protocol for the problem implies PIR on a large database. This imposes a barrier on the local computational cost of secure protocols for the problem. We also identify a new natural relaxation of PIR that we call semi-PIR, which is useful for establishing "intermediate hardness" of several practically motivated secure computation tasks. We show that semi-PIR implies slightly sublinear PIR via an adaptive black-box reduction and that ruling out a stronger black-box reduction would imply a major breakthrough in complexity theory. We also establish information-theoretic separations between semi-PIR and PIR, showing that some problems that we prove to be semi-PIR-hard are not PIR-hard.

  Elette Boyle, Saleet Klein, Alon Rosen, and Gil Segev
  Securing Abe's Mix-net Against Malicious Verifiers via Witness Indistinguishability
  SCN 2018 - Conference on Security and Cryptography for Networks.
  [Abstract] [PDF]

  We show that the simple and appealing unconditionally sound mix-net due to Abe (Asiacrypt'99) can be augmented to further guarantee anonymity against malicious verifiers. This additional guarantee implies, in particular, that when applying the Fiat-Shamir transform to the mix-net's underlying sub-protocols, anonymity is provably guaranteed for {\em any} hash function.
  
  As our main contribution, we demonstrate how anonymity can be attained, even if most sub-protocols of a mix-net are merely witness indistinguishable (WI). We instantiate our framework with two variants of Abe's mix-net. In the first variant, ElGamal ciphertexts are replaced by an alternative, yet equally efficient, "lossy" encryption scheme. In the second variant, new "dummy" vote ciphertexts are injected prior to the mixing process, and then removed.
  
  Our techniques center on new methods to introduce additional witnesses to the sub-protocols within the proof of security. This, in turn, enables us to leverage the WI guarantees against malicious verifiers. In our first instantiation, these witnesses follow somewhat naturally from the lossiness of the encryption scheme, whereas in our second instantiation they follow from leveraging combinatorial properties of the Benes-network. These approaches may be of independent interest.
  
  Finally, we demonstrate cases in Abe's original mix-net (without modification) where only one witness exists, such that if the WI proof leaks information on the (single) witness in these cases, then the system will not be anonymous against malicious verifiers.

  Elette Boyle, Abhishek Jain, Manoj Prabhakaran, and Ching-Hua Yu
  The Bottleneck Complexity of Secure Multiparty Computation
  ICALP 2018 - International Colloquium on Automata, Languages, and Programming.
  [Abstract] [PDF]

  In this work, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution.
  
  We observe that even without security, bottleneck communication complexity is an interesting measure of communication complexity for (distributed) functions and propose it as a fundamental area to explore. While achieving O(n) bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have o(n) bottleneck complexity, when no security is required.
  
  Our main positive result is a compiler that transforms any (possibly insecure) efficient protocol with fixed communication-pattern for computing any functionality into a secure MPC protocol while pre- serving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function f with sublinear bottleneck complexity can be trans- formed into an MPC protocol for f with the same bottleneck complexity.
  
  Along the way, we build cryptographic primitives -- incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution -- that may be of independent interest.

  Marshall Ball, Elette Boyle, Tal Malkin, and Tal Moran
  Exploring the Boundaries of Topology-Hiding Computation
  Advances in Cryptology - EUROCRYPT 2018.
  [Abstract] [PDF]

  Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. In a line of recent works [Moran, Orlov & Richelson, TCC'15, Hirt et al. CRYPTO'16, Akavia & Moran EUROCRYPT'17, Akavia et al. CRYPTO'17], THC protocols for securely computing any function in the semi-honest setting have been constructed. In addition, it was shown by Moran et al. that in the fail-stop setting THC with negligible leakage on the topology is impossible.
  
  In this paper, we further explore the feasibility boundaries of THC.

  • We show that even against semi-honest adversaries, topology-hiding broadcast on a small (4-node) graph implies oblivious transfer; in contrast, trivial broadcast protocols exist unconditionally if topology can be revealed.
  • We strengthen the lower bound of Moran et al., identifying and extending a relation between the amount of leakage on the underlying graph topology that must be revealed in the fail-stop setting, as a function of the number of parties and communication round complexity: Any n-party protocol leaking delta bits for 0 < delta < 1 must have Omega(n/delta) rounds.

  We then present THC protocols providing close-to-optimal leakage rates, for unrestricted graphs on n nodes against a fail-stop adversary controlling a dishonest majority of the n players. These constitute the first general fail-stop THC protocols. Specifically, for this setting we show:

  • A THC protocol that leaks at most one bit and requires O(n^2)rounds.
  • A THC protocol that leaks at most delta bits for arbitrarily small non-negligible delta, and requires O(n^3/delta) rounds.

  Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Rachel Lin, and Stefano Tessaro
  Foundations of Homomorphic Secret Sharing
  ITCS 2018 - Innovations in Theoretical Computer Science.
  [Abstract] [PDF]

  Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open.
  
  We initiate a systematic study of HSS, making the following contributions.
  
  

  • A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework.
  • Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer.
  • Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine- grained average-case hardness and verifiable computation.

  Elette Boyle
  Recent Advances in Function & Homomorphic Secret Sharing (Invited Talk)
  Indocrypt 2017 - the International Conference on Cryptology in India.
  [Abstract] [PDF]

  Function Secret Sharing (FSS) and Homomorphic Secret Sharing (HSS) are two extensions of standard secret sharing, which support rich forms of homomorphism on secret shared values.
  
  

  • An m-party FSS scheme for a given function family F enables splitting a function f: {0,1}^n -> G from F (for Abelian group G) into m succinctly described functions f_1,...,f_m such that strict subsets of the f_i hide f, and f(x) = f_1(x) + ... + f_m(x) for every input x.
  • An m-party HSS is a dual notion, where an input x is split into shares x^1,...,x^m, such that strict subsets of x^i hide x, and one can recover the evaluation P(x) of a program P on x given homomorphically evaluated share values Eval(x^1,P),...,Eval(x^m,P).

  
  In the last few years, many new constructions and applications of FSS and HSS have been discovered, yielding implications ranging from efficient private database manipulation and secure computation protocols, to worst-case to average-case reductions.
  
  In this treatise, we introduce the reader to the background required to understand these developments, and give a roadmap of recent advances (up to October 2017).

  Elette Boyle, Yuval Ishai, Rafael Pass, and Mary Wootters
  Can We Access a Database Both Locally and Privately?
  TCC 2017 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit x_i by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i.
  
  Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable symmetric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware.
  
  Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

  Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, and Michele Orrù
  Homomorphic Secret Sharing: Optimizations and Applications
  CCS 2017 - ACM Conference on Computer and Communications Security.
  [Abstract] [PDF]

  We continue the study of Homomorphic Secret Sharing (HSS), recently introduced by Boyle et al. (Crypto 2016, Eurocrypt 2017). A (2-party) HSS scheme splits an input x into shares (x0, x1) such that (1) each share computationally hides x, and (2) there exists an efficient homomorphic evaluation algorithm Eval such that for any function (or "program") P from a given class it holds that Eval(x0,P)+Eval(x1,P)=P(x). Boyle et al. show how to construct an HSS scheme for branching programs, with an inverse polynomial error, using discrete-log type assumptions such as DDH.
  
  We make two types of contributions.
  
  

  • Optimizations. We introduce new optimizations that speed up the previous optimized implementation of Boyle et al. by more than a factor of 30, significantly reduce the share size, and reduce the rate of leakage induced by selective failure.
  • Applications. Our optimizations are motivated by the observation that there are natural application scenarios in which HSS is useful even when applied to simple computations on short inputs. We demonstrate the practical feasibility of our HSS implementation in the context of such applications.

  Elette Boyle, Niv Gilboa, and Yuval Ishai
  Group-Based Secure Computation: Optimizing Rounds, Communication, and Computation
  Advances in Cryptology - EUROCRYPT 2017.
  [Abstract] [PDF]

  A recent work of Boyle et al. (Crypto 2016) suggests that "group-based" cryptographic protocols, namely ones that only rely on a cryptographically hard (Abelian) group, can be surprisingly powerful. In particular, they present succinct two-party protocols for securely computing branching programs and NC1 circuits under the DDH assumption, providing the first alternative to fully homomorphic encryption. In this work we further explore the power of group-based secure computation protocols, improving both their asymptotic and concrete efficiency. We obtain the following results.

  • Black-box use of group. We modify the succinct protocols of Boyle et al. so that they only make a black-box use of the underlying group, eliminating an expensive non-black-box setup phase.
  • Round complexity. For any constant number of parties, we obtain 2-round MPC protocols based on a PKI setup under the DDH assumption. Prior to our work, such protocols were only known using fully homomorphic encryption or indistinguishability obfuscation.
  • Communication complexity. Under DDH, we present a secure 2-party protocol for any NC1 or log-space computation with n input bits and m output bits using n + (1 + o(1))m + poly(\lambda) bits of communication, where \lambda is a security parameter. In particular, our protocol can generate n instances of bit-oblivious-transfer using (4 + o(1))n bits of communication. This gives the first constant-rate OT protocol under DDH.
  • Computation complexity. We present several techniques for improving the computational cost of the share conversion procedure of Boyle et al., improving the concrete efficiency of group-based protocols by several orders of magnitude.
  
  

  Elette Boyle, Niv Gilboa, and Yuval Ishai
  Function Secret Sharing: Improvements and Extensions
  CCS 2016 - ACM Conference on Computer and Communications Security.
  [Abstract] [PDF]

  Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family F. More concretely, an m-party FSS scheme splits a function $f : {0,1}^n \to G, for some abelian group G, into functions f_1,...,f_m, described by keys k_1,...,k_m, such that f = f_1 + ... + f_m and every strict subset of the keys hides f. A Distributed Point Function (DPF) is a special case where F is the family of point functions, namely functions f_{a,b} that evaluate to b on the input a and to 0 on all other inputs.
  
  FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging.
  
  We improve and extend previous results in several ways:

  • Simplified FSS constructions. We introduce a tensoring operation for FSS which is used to obtain a conceptually simpler derivation of previous constructions and present our new constructions.
  • Improved 2-party DPF. We reduce the key size of the PRG-based DPF scheme of Boyle et al. roughly by a factor of 4 and optimize its computational cost. The optimized DPF significantly improves the concrete costs of 2-server PIR and related primitives.
  FSS for new function families. We present an efficient PRG-based 2-party FSS scheme for the family of decision trees, leaking only the topology of the tree and the internal node labels. We apply this towards FSS for multi-dimensional intervals. We also present a general technique for extending FSS schemes by in- creasing the number of parties.
  • Verifiable FSS. We present efficient protocols for verifying that keys (k_1,...,k_m), obtained from a potentially malicious user, are consistent with some f \in F. Such a verification may be critical for applications that involve private writing or voting by many users.

  
  

  Elette Boyle, Niv Gilboa, and Yuval Ishai
  Breaking the Circuit-Size Barrier for Secure Computation Under DDH
  CRYPTO 2016 - International Conference on Cryptology.
  Best Paper Award
  [Abstract] [PDF]

  Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. More concretely, there is an evaluation algorithm \Eval with a single bit of output, such that if an input $w \in {0,1}^n$ is shared into $(w^0,w^1)$, then for any deterministic branching program P of size S we have that \Eval(P,w0) \xor \Eval(P,w1)=P(w), except with at most \delta failure probability. The running time of the sharing algorithm is polynomial in n and the security parameter \lambda, and that of \Eval is polynomial in S, \lambda, and 1/\delta. This applies as a special case to boolean formulas of size S or boolean circuits of depth log S. We also present a public-key variant that enables homomorphic computation on inputs contributed by multiple clients. The above result implies the following DDH-based applications:
  
  - A secure 2-party computation protocol for evaluating any branching program of size S, where the communication complexity is linear in the input size and only the running time grows with S.
  
  - A secure 2-party computation protocol for evaluating any layered boolean circuit of size S and m outputs with communication complexity O(S/logS)+m*poly(\lambda).
  
  -A 2-party {\em function secret sharing} scheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability).
  
  - A 1-round 2-server {\em private information retrieval} scheme supporting general searches expressed by branching programs.

  Elette Boyle and Moni Naor
  Is There an Oblivious RAM Lower Bound?
  ITCS 2016 - Innovations in Theoretical Computer Science.
  [Abstract] [PDF]

  An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of obtaining the smallest overhead possible.
  
  We revisit the lower bound on the overhead required to obliviously simulate programs, due to Goldreich and Ostrovsky. While the lower bound is fairly general, including the offline case, when the simulator is given the reads and writes ahead of time, it does assume that the simulator behaves in a ?balls and bins? fashion. That is, the simulator must act by shuffling data items around, and is not allowed to have sophisticated encoding of the data.
  
  We prove that for the offline case, showing a lower bound without the above restriction is related to the size of the circuits for sorting. Our proof is constructive, and uses a bit-slicing approach which manipulates the bit representations of data in the simulation. This implies that without obtaining yet unknown superlinear lower bounds on the size of such circuits, we cannot hope to get lower bounds on offline (unrestricted) ORAMs.

  Elette Boyle, Kai-Min Chung, and Rafael Pass
  Oblivious Parallel RAM
  TCC 2016 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  A machine is said to be {\em oblivious} if the sequences of memory accesses made by the machine for two inputs of the same running time are identically (or close to identically) distributed. Oblivious RAM (ORAM) compilers -- compilers that turn any RAM program $\Pi$ into an oblivious RAM $\Pi'$, while only incurring a "small", polylogarithmic slowdown -- have been extensively studied since the work of Goldreich and Ostrovsky (J.ACM'96) and have numerous fundamental applications. These compilers, however, do not level parallelism: even if $\Pi$ can be highly parallelized, $\Pi'$ will be inherently sequential.
  
  In this work we present the first {\em Oblivious Parallel RAM (OPRAM)} compiler, which compiles any PRAM into an oblivious PRAM while only incurring a polylogarithmic slowdown.

  Elette Boyle, Niv Gilboa, Yuval Ishai
  Function Secret Sharing
  Advances in Cryptology - EUROCRYPT 2015.
  [Abstract] [PDF]

  Motivated by the goal of securely searching and pdating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer $p \ge 2$ and a class $\mathcal{F}$ of functions $f: \{0,1\}^n \to \mathbb{G}$ where $\mathbb{G}$ is an Abelian group, a $p$-party FSS scheme for $\mathcal{F}$ allows one to split each $f \in \mathcal{F}$ into $p$ succinctly described functions $f_i: \{0,1\}^n \to \mathbb{G}$, $1 \le i \le p$, such that: (1) $\sum_{i1=}^p f_i = f$, and (2) any strict subset of the $f_i$ hides $f$. Thus, an FSS for $\mathcal{F}$ can be thought of as a method for succinctly performing an "additive secret sharing" of functions from $\mathcal{F}$.The original definition of DPF coincides with a two-party FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input.
  
  We present two types of results. First, we obtain efficiency improvements and extensions of the original DPF construction. Then, we initiate a systematic study of general FSS, providing some constructions and establishing relations with other cryptographic primitives. More concretely, we obtain the following main results:
  
  1. Improved DPF. We present an improved (two-party) DPF construction from a pseudorandom generator (PRG), reducing the length of the key describing each $f_i$ from $O(\lambda \cdot n^{\log_2(3)})$ to $O(\lambda n)$, where $\lambda$ is the PRG seed length.
  
  2. Multi-party DPF. We present the first nontrivial construction of a $p$-party DPF for $p \ge 3$, obtaining a near-quadratic improvement over a naive construction that additively shares the truth-table of $f$. This construction too can be based on any PRG.
  
  3. FSS for simple functions. We present efficient PRG-based FSS constructions for natural function classes that extend point functions, including interval functions and partial matching functions.
  
  4. A study of general FSS. We show several relations between general FSS and other cryptographic primitives. These include a construction of general FSS via obfuscation, an indication for the implausibility of constructing general FSS from weak cryptographic assumptions such as the existence of one-way functions, a completeness result, and a relation with pseudorandom functions.

  Elette Boyle, Kai-Min Chung, and Rafael Pass
  Large-Scale Secure Computation
  CRYPTO 2015 - International Conference on Cryptology.
  [Abstract] [PDF]

  We are interested in secure computation protocols in settings where the number of parties is huge and their data even larger. Assuming the existence of a single-use broadcast channel (per player), we demonstrate statistically secure computation protocols for computing (multiple) arbitrary dynamic RAM programs over parties' inputs, handling (1/3-eps) fraction static corruptions, while preserving up to polylogarithmic factors the computation and memory complexities of the RAM program. Additionally, our protocol is load balanced and has polylogarithmic communication locality.

  Elette Boyle and Rafael Pass
  Limits of Extractability Assumptions with Distributional Auxiliary Input
  Asiacrypt 2015 - International Conference on the Theory and Applications of Cryptology and Information Security.
  [Abstract] [PDF]

  Extractability, or "knowledge," assumptions have recently gained popularity in the cryptographic community, leading to the study of primitives such as extractable one-way functions, extractable hash functions, succinct non-interactive arguments of knowledge (SNARKs), and (public-coin) differing-inputs obfuscation ((PC-)diO), and spurring the development of a wide spectrum of new applications relying on these primitives. For most of these applications, it is required that the extractability assumption holds even in the presence of attackers receiving some auxiliary information that is sampled from some fixed efficiently computable distribution Z.
  
  We show that, assuming the existence of public-coin collision-resistant hash functions, there exists an efficient distributions Z such that either

  • PC-diO for Turing machines does not exist, or
  • extractable one-way functions w.r.t. auxiliary input Z do not exist.

  
  A corollary of this result shows that additionally assuming existence of fully homomorphic encryption with decryption in NC1, there exists an efficient distribution Z such that either

  • SNARKs for NP w.r.t. auxiliary input Z do not exist, or
  • PC-diO for NC1 circuits does not exist.

  
  To achieve our results, we develop a ?succinct punctured program? technique, mirroring the powerful punctured program technique of Sahai and Waters (STOC'14), and present several other applications of this new technique. In particular, we construct succinct perfect zero knowledge SNARGs and give a universal instantiation of random oracles in full-domain hash applications, based on PC-diO.
  
  As a final contribution, we demonstrate that even in the absence of auxiliary input, care must be taken when making use of extractability assumptions. We show that (standard) diO w.r.t. any distribution D over programs and bounded-length auxiliary input is directly implied by any obfuscator that satisfies the weaker indistinguishability obfuscation (iO) security notion and diO for a slightly modified distribution D' of programs (of slightly greater size) and no auxiliary input. As a consequence, we directly obtain negative results for (standard) diO in the absence of auxiliary input.

  Elette Boyle, Kai-Min Chung, and Rafael Pass
  On Extractability (a.k.a. Differing-Inputs) Obfuscation
  TCC 2014 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  We initiate the study of extractability obfuscation, a notion first suggested by Barak et al. (JACM 2012): An extractability obfuscator eO for a class of algorithms M guarantees that if an efficient attacker A can distinguish between obfuscations eO(M_1), eO(M_2) of two algorithms M_1,M_2 \in M, then A can efficiently recover (given M_1 and M_2) an input on which M_1 and M_2 provide different outputs.

  • We rely on the recent candidate virtual black-box obfuscation constructions to provide candidate constructions of extractability obfuscators for NC^1; next, following the blueprint of Garg et~al. (FOCS 2013), we show how to bootstrap the obfuscator for NC^1 to an obfuscator for all non-uniform polynomial-time Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC^1, our construction enables succinctly obfuscating non-uniform Turing machines (as opposed to circuits), without turning running-time into description size.
  • We introduce a new notion of functional witness encryption, which enables encrypting a message m with respect to an instance x, language L, and function f, such that anyone (and only those) who holds a witness w for x \in L can compute f(m,w) on the message and particular known witness. We show that functional witness encryption is, in fact, equivalent to extractability obfuscation.
  • We demonstrate other applications of extractability extraction, including the first construction of fully (adaptive-message) indistinguishability-secure functional encryption for an unbounded number of key queries and unbounded message spaces.
  • We finally relate indistinguishability obfuscation and extractability obfuscation and show special cases when indistinguishability obfuscation can be turned into extractability obfuscation.

  Elette Boyle, Shafi Goldwasser, and Ioana Ivan
  Functional Signatures and Pseudorandom Functions
  PKC 2014 - International Conference on Practice and Theory of Public-Key Cryptography.
  [Abstract] [PDF]

  In this paper, we introduce two new cryptographic primitives: functional digital signatures and functional pseudorandom functions.
  
  In a functional signature scheme, in addition to a master signing key that can be used to sign any message, there are signing keys for a function f, which allow one to sign any message in the range of f. As a special case, this implies the ability to generate keys for predicates P, which allow one to sign any message m, for which P(m) = 1.
  
  We show applications of functional signatures to constructing succinct non-interactive arguments and delegation schemes. We give several general constructions for this primitive based on different computational hardness assumptions, and describe the trade-offs between them in terms of the assumptions they require and the size of the signatures.
  
  In a functional pseudorandom function, in addition to a master secret key that can be used to evaluate the pseudorandom function F on any point in the domain, there are additional secret keys for a function f, which allow one to evaluate F on any y for which there exists an x such that f(x)=y. As a special case, this implies pseudorandom functions with selective access, where one can delegate the ability to evaluate the pseudorandom function on inputs y for which a predicate P(y)=1 holds. We define and provide a sample construction of a functional pseudorandom function family for prefix-fixing functions.

  Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, and Amit Sahai
  Secure Computation Against Adaptive Auxiliary Information
  CRYPTO 2013 - International Conference on Cryptology.
  [Abstract] [PDF]

  We study the problem of secure two-party and multiparty computation (MPC) in a setting where a cheating polynomial-time adversary can corrupt an arbitrary subset of parties and, in addition, learn arbitrary auxiliary information on the entire states of all honest parties (including their inputs and random coins), in an adaptive manner, throughout the protocol execution. We formalize a definition of multiparty computation secure against adaptive auxiliary information (AAI-MPC), that intuitively guarantees that such an adversary learns no more than the function output and the adaptive auxiliary information. In particular, if the auxiliary information contains only partial, "noisy," or computationally invertible information on secret inputs, then only such information should be revealed.
  
  We construct a universally composable AAI two-party and multiparty computation protocol that realizes any (efficiently computable) functionality against malicious adversaries in the common reference string model, based on the linear assumption over bilinear groups and the n-th residuosity assumption. Apart from theoretical interest, our result has interesting applications to the regime of leakage-resilient cryptography.
  
  At the heart of our construction is a new two-round oblivious transfer protocol secure against malicious adversaries who may receive adaptive auxiliary information. This may be of independent interest.

  Elette Boyle, Shafi Goldwasser, and Stefano Tessaro
  Communication Locality in Secure Multi-party Computation:
  How to Run Sublinear Algorithms in a Distributed Setting
  TCC 2013 - Theory of Cryptography Conference.
  [Abstract] [PDF]

  We devise multi-party computation protocols for general secure function evaluation with the property that each party is only required to communicate with a small number of dynamically chosen parties. More explicitly, starting with n parties connected via a complete and synchronous network, our protocol requires each party to send messages to (and process messages from) at most polylog(n) other parties using polylog(n) rounds. It achieves secure computation of any polynomial-time computable randomized function f under cryptographic assumptions, and tolerates up to (1/3 - \eps)n statically scheduled Byzantine faults.
  
  We then focus on the particularly interesting setting in which the function to be computed is a sublinear algorithm: An evaluation of f depends on the inputs of at most q = o(n) of the parties, where the identity of these parties can be chosen randomly and possibly adaptively. Typically, q = polylog(n). While the sublinear query complexity of f makes it pos- sible in principle to dramatically reduce the communication complexity of our general protocol, the challenge is to achieve this while maintaining security: in particular, while keeping the identities of the selected inputs completely hidden. We solve this challenge, and we provide a protocol for securely computing such sublinear f that runs in polylog(n) + O(q) rounds, has each party communicating with at most q*polylog(n) other parties, and supports message sizes polylog(n) (l + n), where l is the parties' input size.
  
  Our optimized protocols rely on a multi-signature scheme, fully homomorphic encryption (FHE), and simulation-sound adaptive NIZK arguments. However, we remark that multi-signatures and FHE are used to obtain our bounds on message size and round complexity. Assuming only standard digital signatures and public-key encryption, one can still obtain the property that each party only communicates with polylog(n) other parties. We emphasize that the scheduling of faults can depend on the initial PKI setup of digital signatures and the NIZK parameters

  Elette Boyle, Shafi Goldwasser, Abhishek Jain, and Yael Tauman Kalai
  Multi-Party Computation Secure Against Continual Memory Leakage
  STOC 2012 - ACM Symposium on Theory of Computing.
  [Abstract] [PDF]

  We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary, in addition to corrupting 1-\eps fraction of all parties for an arbitrarily small constant \eps > 0, can leak information about the secret state of each honest party. This leakage can be continuous for an unbounded number of executions of the MPC protocol, computing different functions on the same or different set of inputs. We assume a (necessary) "leak-free" preprocessing stage.
  
  We emphasize that we achieve leakage resilience without weakening the security guarantee of classical MPC. Namely, an adversary who is given leakage on honest parties' states, is guaranteed to learn nothing beyond the input and output values of corrupted parties. This is in contrast with previous works on leakage in the multi-party protocol setting, which weaken the security notion, and only guarantee that a protocol which leaks l bits about the parties' secret states, yields at most l bits of leakage on the parties' private inputs. For some functions, such as voting, such leakage can be detrimental.
  
  Our result relies on standard cryptographic assumptions, and our security parameter is polynomially related to the number of parties.

  Elette Boyle, Shafi Goldwasser, and Yael Tauman Kalai
  Leakage-Resilient Coin Tossing
  DISC 2011 - The International Symposium on Distributed Computing.
  Invited to Distributed Computing journal.
  [Abstract] [PDF]

  The ability to collectively toss a common coin among n parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than 1/r bias in O(r) rounds (Cleve STOC '86). In the case of honest majority, in contrast, unconditionally secure O(1)-round protocols for generating common perfectly unbiased coins follow from general completeness theorems on multi-party secure protocols in the perfectly secure channels model (e.g., BGW, CCD STOC '88).
  
  However, in the multi-party protocols with faulty minority, parties need to generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.
  
  In this work, we present an O(1)-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t <= (1/3 - \eps) n computationally-unbounded Byzantine faults and in addition a \Omega(1)-fraction leakage on each (honest) party's secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan '08) adapted to the distributed setting.
  
  Another contribution of our work is a tool we use to achieve collective coin flipping -- leakage-resilient verifiable secret sharing. Informally, this is a variant of ordinary VSS in which secrecy guarantees are maintained even if information is leaked on individual shares of the secret.

  Elette Boyle, Gil Segev, and Daniel Wichs
  Fully Leakage-Resilient Signatures
  Advances in Cryptology - EUROCRYPT 2011.
  Invited to Journal of Cryptology.
  [Abstract] [PDF]

  A signature scheme is fully leakage resilient (Katz and Vaikuntanathan, ASIACRYPT '09) if it is existentially unforgeable under an adaptive chosen-message attack even in a setting where an adversary may obtain bounded (yet arbitrary) leakage information on all intermediate values that are used throughout the lifetime of the system. This is a strong and meaningful notion of security that captures a significantly wide range of side-channel attacks.
  
  One of the main challenges in constructing fully leakage-resilient signature schemes is dealing with leakage that may depend on the random bits used by the signing algorithm, and constructions of such schemes are known only in the random-oracle model. Moreover, even in the random-oracle model, known schemes are only resilient to leakage of less than half the length of their signing key.
  
  In this paper we construct the first fully leakage-resilient signature schemes without random oracles. We present a scheme that is resilient to any leakage of length (1-o(1))L bits, where L is the length of the signing key. Our approach relies on generic cryptographic primitives, and at the same time admits rather efficient instantiations based on specific number-theoretic assumptions. In addition, we show that our approach extends to the continual-leakage model, recently introduced by Dodis, Haralambiev, Lopez-Alt and Wichs (FOCS '10), and by Brakerski, Tauman Kalai, Katz and Vaikuntanathan (FOCS '10). In this model the signing key is allowed to be refreshed, while its corresponding verification key remains fixed, and the amount of leakage is assumed to be bounded only in between any two successive key refreshes.

  Elette Boyle and Federico Echenique
  Sequential Entry in Many-to-One Matching Markets
  Social Choice and Welfare, Springer, Vol 33(1), June 2009: pp 87-99.
  [Abstract] [PDF]

  We study sequential bargaining in many-to-one matching markets. We show that there is an advantage to entering late in the market, and that the last agent to enter the market will receive his or her best partner in a stable matching, extending the results of Blum and Rothblum (J Econ Theory 103(2):429-443, 2002) and Cechlárová (Randomized matching mechanism revisited. Mimeo, Safarik University, 2002) for the marriage model. We also discuss the relation between sequential bargaining and a possible alternative formulation based on the NTU Shapley value.

  Elette Boyle and Robert McEliece
  Asymptotic Weight Enumerators of Randomly Punctured, Expurgated, and Shortened Code Ensembles
  46th Annual Allerton Conference on Communication, Control, and Computing, 2008.
  [Abstract] [PDF]

  In this paper, we examine the effect of random puncturing, expurgating, and shortening on the asymptotic weight enumerator of certain linear code ensembles. We begin by discussing the actions of the three alteration methods on individual codes. We derive expressions for the average resulting code weight enumerator under each alteration. We then extend these results to the spectral shape of linear code ensembles whose original spectral shape is known, and demonstrate our findings on two specific code ensembles: the Shannon ensemble and the regular (j, k) Gallager ensemble.

  Elette Boyle
  Navigation on Mars: Validation of the Mars Science Laboratory Rover Hazard Avoidance Algorithm
  Caltech Undergraduate Research Journal Vol 5, 2006: pp 21-25.
  [Abstract]

  The Mars Science Laboratory (MSL) is a long-range, long-duration roving laboratory planned for launch in 2009. While humans can issue commands to the rover on Mars, the delay in transmission means navigation functions requiring immediate action, such as recognizing hazards and locating pathways of safety, must be controlled autonomously. The autonomous navigation software currently used in Mars rovers is designed for use in terrains with minimal inclines and few obstacles. However, for MSL, NASA is developing a more advanced version of the Mars Exploration Rover (MER) GESTALT hazard detection and avoidance software. Ensuring that GESTALT functions correctly and effectively is a crucial task, since a malfunction could result in failure of the entire mission. Before use on Mars, GESTALT performance must be verified in a cross-section of potential terrains, including regions with rocks, craters, and slopes. The purpose of the summer research project was to test GESTALT in terrains of a range of rock hazard densities.

Program Committees

• NeurIPS 2022 Workshop on Algorithmic Fairness through the Lens of Causality and Privacy (AFCP).

• CRYPTO 2022 - International Conference on Cryptology.

• AAAI Workshop on Privacy-Preserving Artificial Intelligence (PPAI) 2022.

• Theory of Cryptography Conference (TCC) 2021.

• Innovations in Theoretical Computer Science (ITCS) 2021.

• PrivateNLP Workshop II (colocated EMNLP 2020).

• AAAI Workshop on Privacy-Preserving Artificial Intelligence (PPAI) 2020.

• PrivateNLP Workshop (colocated WSDM 2020).

• EUROCRYPT 2020.

• ACM CCS 2019 Workshop on Privacy-Preserving Machine Learning.

• Symposium on Foundations of Computer Science (FOCS) 2018.

• ACM Conference on Computer and Communications Security (ACM CCS) 2017.

• Theory of Cryptography Conference (TCC) 2017.

• CRYPTO 2017 - International Conference on Cryptology.

• Innovations in Theoretical Computer Science (ITCS) 2017.

• Theory of Cryptography Conference (TCC) 2016B.

• EUROCRYPT 2016.

• Theory of Cryptography Conference (TCC) 2015.

• Conference on Security and Cryptography for Networks (SCN) 2014.

Internships and Visits

• Microsoft Research Silicon Valley
  Research Internship, Summer 2011

• Weizmann Institute of Science
  Visiting Student, Spring and Summer 2010

• US Department of Defense
  Research Internship, Director's Summer Program, Summer 2007

• NASA Jet Propulsion Laboratory
  Research Internship, Robotic Software Systems Group, Summer 2005
  Mars Science Laboratory (Curiosity Rover) Mission.