Search

Secure aggregation of high-dimensional vectors is a fundamental primitive in federated statistics and learning. A two-server system such as PRIO allows for scalable aggregation of secret-shared vectors. Adversarial clients might try to manipulate the aggregate, so it is important to ensure that each (secret-shared) contribution is well-formed. In this work, we focus on the important and well-studied goal of ensuring that each contribution vector has bounded Euclidean norm. Existing protocols for ensuring bounded-norm contributions either incur a large communication overhead, or only allow for approximate verification of the norm bound. We propose Private Inexpensive Norm Enforcement (PINE): a new protocol that allows exact norm verification with little communication overhead. For high-dimensional vectors, our approach has a communication overhead of a few percent, compared to the 16-32x overhead of previous approaches.

In this work, we introduce the Gulliver multi-party computation model (GMPC). The GMPC model considers a single highly powerful party, called the server or Gulliver, that is connected to $n$ users over a star topology network (alternatively formulated as a full network, where the server can block any message). The users are significantly less powerful than the server, and, in particular, should have both computation and communication complexities that are polylogarithmic in $n$. Protocols in the GMPC model should be secure against malicious adversaries that may corrupt a subset of the users and/or the server. Designing protocols in the GMPC model is a delicate task, since users can only hold information about polylog(n) other users (and, in particular, can only communicate with polylog(n) other users). In addition, the server can block any message between any pair of honest parties. Thus, reaching an agreement becomes a challenging task. Nevertheless, we design generic protocols in the GMPC model, assuming that at most $\alpha<1/6$ fraction of the users may be corrupted (in addition to the server). Our main contribution is a variant of Feige's committee election protocol [FOCS 1999] that is secure in the GMPC model. Given this tool we show: 1. Assuming fully homomorphic encryption (FHE), any computationally efficient function with $O\left(n\cdot polylog(n)\right)$-size output can be securely computed in the GMPC model. 2. Any function that can be computed by a circuit of $O(polylog(n))$ depth, $O\left(n\cdot polylog(n)\right)$ size, and bounded fan-in and fan-out can be securely computed in the GMPC model without assuming FHE. 3. In particular, sorting can be securely computed in the GMPC model without assuming FHE. This has important applications for the shuffle model of differential privacy, and resolves an open question of Bell et al. [CCS 2020].

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called \emph{fully secure} if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called \emph{fair} if an adversary can prematurely abort the computation, however, only before learning any new information. We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., $1\%$ of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to chosen random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply "listen" to the computation over a broadcast channel., Comment: Preliminary version appeared in Conference on Security and Cryptography for Networks, SCN 2018

A two-party coin-flipping protocol is $\epsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\epsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch, Blum, Chor, Goldwasser, and Micali[Manuscript '85] constructed a $\Theta(1/\sqrt{r})$-fair coin-flipping protocol, assuming the existence of one-way functions. Moran, Naor, and Segev [Journal of Cryptology '16] constructed an $r$-round coin-flipping protocol that is $\Theta(1/r)$-fair (thus matching the aforementioned lower bound of Cleve [STOC '86]), assuming the existence of oblivious transfer. The above gives rise to the intriguing question of whether oblivious transfer, or more generally ``public-key primitives,'' is required for an $o(1/\sqrt r)$-fair coin flipping protocol. We make a different progress towards answering the question by showing that, for any constant $r\in \N$, the existence of an $1/(c\cdot \sqrt{r})$-fair, $r$-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where $c$ denotes some universal constant (independent of $r$). Our reduction is \emph{non} black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner, Nissim, Omri, Shaltiel, and Silbak [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel, Haitner, Makriyannis, and Omri [FOCS '18] on multi-party coin-flipping protocols., Comment: A preliminary version appeared in Theory of Cryptography Conference, TCC 2018

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ "appears" to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions: $\bullet$ We develop new tools to argue about this loose notion and show (modulo some caveats) that for every such protocol $\pi$, there exists an efficient simulator such that the following holds: on input $T_\kappa$, the simulator outputs a pair $(X'_\kappa ,Y'_\kappa)$ such that $(X'_\kappa,Y'_\kappa,T_\kappa)$ is (somewhat) computationally indistinguishable from $(X_\kappa,Y_\kappa,T_\kappa)$. $\bullet$ We use these tools to prove the following dichotomy theorem: every such protocol $\pi$ is: - either uncorrelated -- it is (somewhat) indistinguishable from an efficient protocol whose parties interact to produce $T_\kappa$, but then choose their outputs independently from some product distribution (that is determined in poly-time from $T_\kappa$), - or, the protocol implies a key-agreement protocol (for infinitely many $\kappa$'s). Uncorrelated protocols are uninteresting from a cryptographic viewpoint, as the correlation between outputs is (computationally) trivial. Our dichotomy shows that every protocol is either completely uninteresting or implies key-agreement. $\bullet$ We use the above dichotomy to make progress on open problems on minimal cryptographic assumptions required for differentially private mechanisms for the XOR function. $\bullet$ A subsequent work of Haitner et al. uses the above dichotomy to makes progress on a longstanding open question regarding the complexity of fair two-party coin-flipping protocols., Comment: A preliminary version appeared in FOCS 2018. Published in SIAM Journal on Computing 2020

In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. This lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a $polylog$ factor) by Haitner and Tsfadi [SICOMP '17], and was approached for $n$-party protocols when $n< loglog r$ by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For $n> loglog r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\epsilon >0$, an $r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound, and is only $n=r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al., Comment: A preliminary version appeared in FOCS 18

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a peer-to-peer network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization: 1) A symmetric $n$-party functionality can be securely computed facing $n/3\le t

Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number $\mathfrak v = \mathfrak v(n)$ such that, if $A_1, \ldots, A_n$ are $n$ equivalence relations on a common finite ground set $X$, such that for each $i$ there are at least $\mathfrak v$ elements of $X$ that belong to $A_i$-equivalence classes of size larger than $1$, then $X$ has a rainbow matching---a set of $2n$ distinct elements $a_1, b_1, \ldots, a_n, b_n$, such that $a_i$ is $A_i$-equivalent to $b_i$ for each $i$? Grinblat has shown that $\mathfrak v(n) \le 10n/3 + O(\sqrt{n})$. He asks whether $\mathfrak v(n) = 3n-2$ for all $n\ge 4$. In this paper we improve the upper bound (for all large enough $n$) to $\mathfrak v(n) \le 16n/5 + O(1)$., Comment: Revision taking into account referees' comments. 12 pages, 7 figures

In the classical facility location problem we consider a graph $G$ with fixed weights on the edges of $G$. The goal is then to find an optimal positioning for a set of facilities on the graph with respect to some objective function. We introduce a new framework for facility location problems, where the weights on the graph edges are not fixed, but rather should be assigned. The goal is to find a valid assignment for which the resulting weighted graph optimizes the facility location objective function. We present algorithms for finding the optimal {\em budget allocation} for the center point problem and for the median point problem on trees. Our algorithms run in linear time, both for the case where a candidate vertex is given as part of the input, and for the case where finding a vertex that optimizes the solution is part of the problem. We also present a hardness result for the general graph case of the center point problem, followed by an $O(\log^2(n))$ approximation algorithm on graphs - with general metric spaces.

We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs - secure function evaluation (SFE) and differential privacy. While in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. The general feasibility results for SFE suggest a natural paradigm for implementing differentially private analyses distributively: First choose what to compute, i.e., a differentially private analysis; Then decide how to compute it, i.e., construct an SFE protocol for this analysis. We initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. In particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including binary sum, gap threshold, and approximate median queries. Our results imply that when computing the binary sum of $n$ distributed inputs then: * When we require that the error is $o(\sqrt{n})$ and the number of rounds is constant, there is no benefit in the new paradigm. * When we allow an error of $O(\sqrt{n})$, the new paradigm yields more efficient protocols when we consider protocols that compute symmetric functions. Our results also yield new separations between the local and global models of computations for private data analysis.

A protocol for computing a functionality is secure if an adversary in this protocol cannot cause more harm than in an ideal computation where parties give their inputs to a trusted party which returns the output of the functionality to all parties. In particular, in the ideal model such computation is fair -- all parties get the output. Cleve (STOC 1986) proved that, in general, fairness is not possible without an honest majority. To overcome this impossibility, Gordon and Katz (Eurocrypt 2010) suggested a relaxed definition -- 1/p-secure computation -- which guarantees partial fairness. For two parties, they construct 1/p-secure protocols for functionalities for which the size of either their domain or their range is polynomial (in the security parameter). Gordon and Katz ask whether their results can be extended to multiparty protocols. We study 1/p-secure protocols in the multiparty setting for general functionalities. Our main result is constructions of 1/p-secure protocols when the number of parties is constant provided that less than 2/3 of the parties are corrupt. Our protocols require that either (1) the functionality is deterministic and the size of the domain is polynomial (in the security parameter), or (2) the functionality can be randomized and the size of the range is polynomial. If the size of the domain is constant and the functionality is deterministic, then our protocol is efficient even when the number of parties is O(log log n) (where n is the security parameter). On the negative side, we show that when the number of parties is super-constant, 1/p-secure protocols are not possible when the size of the domain is polynomial.

For a function $g:\N\to \N$, the \emph{$g$-regressive Ramsey number} of $k$ is the least $N$ so that \[N\stackrel \min \longrightarrow (k)_g\] . This symbol means: for every $c:[N]^2\to \N$ that satisfies $c(m,n)\le g(\min\{m,n\})$ there is a \emph{min-homogeneous} $H\su N$ of size $k$, that is, the color $c(m,n)$ of a pair $\{m,n\}\su H$ depends only on $\min\{m,n\}$. It is known (\cite{km,ks}) that $\id$-regressive Ramsey numbers grow in $k$ as fast as $\Ack(k)$, Ackermann's function in $k$. On the other hand, for constant $g$, the $g$-regressive Ramsey numbers grow exponentially in $k$, and are therefore primitive recursive in $k$. We compute below the threshold in which $g$-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian, by proving: Suppose $g:\N\to \N$ is weakly increasing. Then the $g$-regressive Ramsey numbers are primitive recursive if an only if for every $t>0$ there is some $M_t$ so that for all $n\ge M_t$ it holds that $g(m)