## CryptoDB

### Elette Boyle

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation
📺
Abstract

Recently Boyle et al. (TCC 2019) proposed a new approach for secure computation in the {\em preprocessing model} building on {\em 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:
{\bf 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 $4\times$ reduction in FSS key size for the Distributed Comparison Function (DCF), i.e. ($f_\alpha(x) = \beta$ for all $x < \alpha$ 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 {\em optimal} FSS schemes, i.e., through a {\em single instance of DCF}, thereby reducing the key sizes by up to $6-22\times$ for commonly used functions in mixed-mode secure computation such as ReLU and sigmoid.
{\bf 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.
{\bf 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.

2021

CRYPTO

Low-Complexity Weak Pseudorandom Functions in AC0[MOD2]
📺
Abstract

A *weak pseudorandom function* (WPRF) is a keyed function $f_k:\{0,1\}^n\to\{0,1\}$ such that, for a random key $k$, a collection of samples $(x, f_k(x))$, for {\em 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.
- *Between Lapland and Cryptomania.* We show that WPRFs in AC0[MOD2] imply a variant of the Learning Parity with Noise (LPN) assumption. This gives an unconditional version of an earlier conditional result of Akavia et al. (ITCS 2014). We further show that WPRFs in a subclass of AC0[mod 2] that includes a recent WPRF candidate by Boyle et al. (FOCS 2020) imply, under a seemingly weak additional conjecture, public-key encryption.
- *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 \emph{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 {\em public} parity gates and relate this question to other conjectures.

2021

CRYPTO

Sublinear GMW-Style Compiler for MPC with Preprocessing
📺
Abstract

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 {\em 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 {\em 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 almost all standard protocols with semi-honest security, the extra {\em additive} storage and online communication costs are both {\em 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 {\em honest-majority} MPC.

2021

TCC

Generalized Pseudorandom Secret Sharing and Efficient Straggler-Resilient Secure Computation
📺
Abstract

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 \ge 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 {\em 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.
\begin{itemize}[leftmargin=*]
\item {\bf 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 2015) 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.
\item {\bf 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.
\end{itemize}
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.

2020

CRYPTO

Efficient Pseudorandom Correlation Generators from Ring-LPN
📺
Abstract

Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better 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 using a cheap, one-time interaction, followed by only ``silent'' local computation. This is achieved via a \emph{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 simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs 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 {\em ring-LPN} assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These 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.

2020

TCC

Topology-Hiding Communication from Minimal Assumptions.
📺
Abstract

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 can 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 distance-of-neighbors 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.

2020

ASIACRYPT

Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs
📺
Abstract

Secure computation protocols enable mutually distrusting parties to compute a function of their private inputs while revealing nothing but the output.
Protocols with {\em full security} (also known as {\em 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 a fully secure protocol for {\em any constant} number of parties $n$ and $t<n/2$ corruptions that achieves full security with the {\em same amortized communication} as for semi-honest security: $\frac{3t}{2t+1}|C| + o(|C|)$ $R$-elements per party ($\approx 1.5$ $R$-elements), for a circuit with $|C|$ multiplication gates over either a finite field $R=\FF$ or over the ring $R=\Z_{2^k}$.
Our techniques include new methods for utilizing the distributed zero-knowledge proofs of Boneh {\em et al.} (CRYPTO 2019) for both distributed verifiers {\em and} provers. As a secondary contribution, we show that similar techniques can be used to compile the best known honest-majority protocols for an arbitrary (super-constant) number of semi-honest parties into ones that achieve {\em security with abort} against malicious parties, with sublinear additive cost.
We present an efficient protocol for {\em 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 $\frac{3t}{2t+1}S + o(S)$ $R$-elements per party, where $S$ is the 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 {\em et al.} (Crypto 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 distributed zero-knowledge proofs of Boneh {\em et al.}~(Crypto 2019), which only require logarithmic communication, for compiling semi-honest protocols into fully secure ones in the more challenging case of $t>1$ corrupted parties.
%Similarly to the recent fully secure 3-party protocol of Boyle {\em et al.} (CCS 2019), our protocol builds on the sublinear-communication distributed zero-knowledge proofs of Boneh {\em et al.} (Crypto 2019) to compile any ``natural'' semi-honest protocol into a fully secure protocol. However, applying this tool with $t>1$ corrupted parties introduces several nontrivial challenges that we overcome in this work.
Our protocol relies on {\em 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 {\em general} use of distributed zero-knowledge proofs. While the protocol only achieves the weaker notion of {\em 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.

2019

EUROCRYPT

Homomorphic Secret Sharing from Lattices Without FHE
📺
Abstract

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 schemes 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.

2019

CRYPTO

Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs
📺
Abstract

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 {\mathbb {F}}^n$$, for a finite field $${\mathbb {F}}$$, 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 the example systems mentioned above.Finally, we observe that zero-knowledge proofs on distributed data provide a general-purpose tool for protecting MPC protocols 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 parties.

2019

CRYPTO

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More
📺
Abstract

Secure multiparty computation (MPC) often relies on 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 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 2003) when communication is the 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 (input-dependent) online communication of MPC protocols scale linearly with the number of parties, instead of quadratically.

2019

TCC

Secure Computation with Preprocessing via Function Secret Sharing
Abstract

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 Damgård 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 that 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.

2019

TCC

Is Information-Theoretic Topology-Hiding Computation Possible?
Abstract

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 of adaptive corruptions.

2019

TCC

Permuted Puzzles and Cryptographic Hardness
Abstract

A permuted puzzle problem is defined by a pair of distributions
$$\mathcal{D}_0,\mathcal{D}_1$$
over
$$\varSigma ^n$$
. The problem is to distinguish samples from
$$\mathcal{D}_0,\mathcal{D}_1$$
, 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
$$\mathcal{D}_0,\mathcal{D}_1$$
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). However, 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
$$\mathcal{D}_0,\mathcal{D}_1$$
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 understanding 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.

2018

CRYPTO

Limits of Practical Sublinear Secure Computation
📺
Abstract

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.

2018

CRYPTO

Must the Communication Graph of MPC Protocols be an Expander?
📺
Abstract

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:Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expanders, within a wide range of settings (computational, information theoretic, 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.

2013

JOFC

Fully Leakage-Resilient Signatures
Abstract

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 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.

#### Program Committees

- Eurocrypt 2020
- Crypto 2017
- TCC 2017
- Eurocrypt 2016
- TCC 2015

#### Coauthors

- N. Nalla Anandakumar (1)
- Marshall Ball (3)
- Fabrice Benhamouda (1)
- Dan Boneh (1)
- Nishanth Chandran (1)
- Kai-Min Chung (3)
- Ran Cohen (3)
- Henry Corrigan-Gibbs (1)
- Geoffroy Couteau (3)
- Deepesh Data (1)
- Sanjam Garg (1)
- Niv Gilboa (12)
- Shafi Goldwasser (2)
- Divya Gupta (1)
- Shai Halevi (1)
- Justin Holmgren (1)
- Pavel Hubáček (1)
- Yuval Ishai (14)
- Ioana Ivan (1)
- Abhishek Jain (1)
- Yael Tauman Kalai (1)
- Lisa Kohl (5)
- Tal Malkin (3)
- Pierre Meyer (1)
- Tal Moran (3)
- Ariel Nof (3)
- Rafael Pass (5)
- Antigoni Polychroniadou (1)
- Mayank Rathee (1)
- Amit Sahai (1)
- Peter Scholl (4)
- Gil Segev (2)
- Stefano Tessaro (1)
- Mor Weiss (1)
- Daniel Wichs (2)
- Mary Wootters (1)