Publications 
Elette Boyle and Moni Naor Is There an Oblivious RAM Lower Bound?
To appear: ITCS 2016  Innovations in Theoretical Computer Science.
[PDF]
Elette Boyle, Niv Gilboa, Yuval Ishai Function Secret Sharing
Advances in Cryptology  EUROCRYPT 2015.
Elette Boyle,
KaiMin Chung, and Rafael Pass Oblivious Parallel RAM
To appear: 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,
KaiMin Chung, and Rafael Pass LargeScale 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 singleuse broadcast channel (per player), we demonstrate statistically secure computation protocols for computing (multiple) arbitrary dynamic RAM programs over parties' inputs, handling (1/3eps) 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
To appear: Asiacrypt 2015. [Abstract] [PDF]
Extractability, or "knowledge," assumptions (such as the "knowledgeofexponent" assumption) have recently gained popularity in the cryptographic community—leading to the study of primitives such as extractable oneway functions, extractable hash functions, succinct noninteractive arguments of knowledge (SNARKs), and extractable obfuscation, 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 collisionresistant hash functions, there exists a pair of efficient distributions Z, Z'; such that either:
 extractable oneway functions w.r.t. Z do not exist, or
 extractability obfuscations for Turing machines w.r.t. Z do not exist.
A corollary of this result shows that assuming existence of fully homomorphic encryption with decryption in NC1, there exist efficient distributions Z, Z' such that either
 extractability obfuscations for NC1 w.r.t. Z do not exist, or
 SNARKs for NP w.r.t. Z' do not exist.
To achieve our results, we develop a "succinct punctured program" technique, mirroring the powerful "punctured program" technique of Sahai and Waters (ePrint'13), and present several other applications of this new technique.
Elette Boyle,
KaiMin Chung, and Rafael Pass
On Extractability (a.k.a. DifferingInputs) 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 blackbox 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 nonuniform polynomialtime Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC^1, our construction enables succinctly obfuscating nonuniform Turing machines (as opposed to circuits), without turning runningtime 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 (adaptivemessage) indistinguishabilitysecure 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 PublicKey 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 noninteractive arguments and delegation schemes. We give several general constructions for this primitive based on different computational hardness assumptions, and describe the tradeoffs 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 prefixfixing 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 twoparty and multiparty computation (MPC) in a setting where a cheating polynomialtime 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 (AAIMPC), 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 twoparty 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 nth residuosity assumption. Apart from theoretical interest, our result has interesting applications to the regime of leakageresilient cryptography.
At the heart of our construction is a new tworound 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 Multiparty Computation:
How to Run Sublinear Algorithms in a Distributed Setting
TCC 2013  Theory of Cryptography Conference. [Abstract] [PDF]
We devise multiparty 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 polynomialtime 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 multisignature scheme, fully homomorphic encryption (FHE), and simulationsound adaptive NIZK arguments. However, we remark that multisignatures and FHE are used to obtain our bounds on message size and round complexity. Assuming only standard digital signatures and publickey 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
MultiParty 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) "leakfree" 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 multiparty 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
LeakageResilient Coin Tossing
DISC 2011  The International Symposium on Distributed Computing.
Invited to Distributed Computing. [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 multiparty secure protocols in the perfectly secure channels model (e.g., BGW, CCD STOC '88).
However, in the multiparty 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 sidechannel 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 computationallyunbounded 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  leakageresilient 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 LeakageResilient 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 chosenmessage 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 sidechannel attacks.
One of the main challenges in constructing fully leakageresilient 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 randomoracle model. Moreover, even in the randomoracle 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 leakageresilient signature schemes without random oracles. We present a scheme that is resilient to any leakage of length (1o(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 numbertheoretic assumptions. In addition, we show that our approach extends to the continualleakage model, recently introduced by Dodis, Haralambiev, LopezAlt 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 ManytoOne Matching Markets
Social Choice and Welfare, Springer, Vol 33(1), June 2009: pp 8799. [Abstract] [PDF]
We study sequential bargaining in manytoone 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):429443, 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 2125.
[Abstract]
The Mars Science Laboratory (MSL) is a longrange, longduration
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 crosssection 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.
