## CryptoDB

### Benny Applebaum

#### Affiliation: Tel Aviv University

#### Publications

**Year**

**Venue**

**Title**

2020

TCC

The Resiliency of MPC with Low Interaction: The Benefit of Making Errors
📺
Abstract

We study information-theoretic secure multiparty protocols that achieve full security, including guaranteed output delivery, at the presence of an active adversary that corrupts a constant fraction of the parties. It is known that 2 rounds are insufficient for such protocols even when the adversary corrupts only two parties (Gennaro, Ishai, Kushilevitz, and Rabin; Crypto 2002), and that perfect protocols can be implemented in three rounds as long as the adversary corrupts less than a quarter of the parties (Applebaum , Brakerski, and Tsabary; Eurocrypt, 2019). Furthermore, it was recently shown that the quarter threshold is tight for any 3-round \emph{perfectly-secure} protocol (Applebaum, Kachlon, and Patra; FOCS 2020). Nevertheless, one may still hope to achieve a better-than-quarter threshold at the expense of allowing some negligible correctness errors and/or statistical deviations in the security.
Our main results show that this is indeed the case. Every function can be computed by 3-round protocols with \emph{statistical} security as long as the adversary corrupts less than third of the parties. Moreover, we show that any better resiliency threshold requires four rounds. Our protocol is computationally inefficient and has an exponential dependency in the circuit's depth $d$ and in the number of parties $n$. We show that this overhead can be avoided by relaxing security to computational, assuming the existence of a non-interactive commitment (NICOM). Previous 3-round computational protocols were based on stronger public-key assumptions. When instantiated with statistically-hiding NICOM, our protocol provides \emph{everlasting statistical} security, i.e., it is secure against adversaries that are computationally unlimited \emph{after} the protocol execution.
To prove these results, we introduce a new hybrid model that allows for 2-round protocols with linear resliency threshold. Here too we prove that, for perfect protocols, the best achievable resiliency is $n/4$, whereas statistical protocols can achieve a threshold of $n/3$. We also construct the first 2-round $n/3$-statistical verifiable secret sharing that supports second-level sharing and prove a matching lower-bound, extending the results of Patra, Choudhary, Rabin, and Rangan (Crypto 2009). Overall, our results refines the differences between statistical and perfect models of security, and show that there are efficiency gaps even in the regime of realizable thresholds.

2019

EUROCRYPT

Degree 2 is Complete for the Round-Complexity of Malicious MPC
📺
Abstract

We show, via a non-interactive reduction, that the existence of a secure multi-party computation (MPC) protocol for degree-2 functions implies the existence of a protocol with the same round complexity for general functions. Thus showing that when considering the round complexity of MPC, it is sufficient to consider very simple functions.Our completeness theorem applies in various settings: information theoretic and computational, fully malicious and malicious with various types of aborts. In fact, we give a master theorem from which all individual settings follow as direct corollaries. Our basic transformation does not require any additional assumptions and incurs communication and computation blow-up which is polynomial in the number of players and in $$S,2^D$$S,2D, where S, D are the circuit size and depth of the function to be computed. Using one-way functions as an additional assumption, the exponential dependence on the depth can be removed.As a consequence, we are able to push the envelope on the state of the art in various settings of MPC, including the following cases.
3-round perfectly-secure protocol (with guaranteed output delivery) against an active adversary that corrupts less than 1/4 of the parties.2-round statistically-secure protocol that achieves security with “selective abort” against an active adversary that corrupts less than half of the parties.Assuming one-way functions, 2-round computationally-secure protocol that achieves security with (standard) abort against an active adversary that corrupts less than half of the parties. This gives a new and conceptually simpler proof to the recent result of Ananth et al. (Crypto 2018).
Technically, our non-interactive reduction draws from the encoding method of Applebaum, Brakerski and Tsabary (TCC 2018). We extend these methods to ones that can be meaningfully analyzed even in the presence of malicious adversaries.

2019

EUROCRYPT

Secret-Sharing Schemes for General and Uniform Access Structures
📺
Abstract

A secret-sharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $$2^{n-o(n)}$$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $$O(2^{0.994n})$$. Our first contribution is improving the exponent of secret sharing down to 0.892. For the special case of linear secret-sharing schemes, we get an exponent of 0.942 (compared to 0.999 of Liu and Vaikuntanathan).Motivated by the construction of Liu and Vaikuntanathan, we study secret-sharing schemes for uniform access structures. An access structure is k-uniform if all sets of size larger than k are authorized, all sets of size smaller than k are unauthorized, and each set of size k can be either authorized or unauthorized. The construction of Liu and Vaikuntanathan starts from protocols for conditional disclosure of secrets, constructs secret-sharing schemes for uniform access structures from them, and combines these schemes in order to obtain secret-sharing schemes for general access structures. Our second contribution in this paper is constructions of secret-sharing schemes for uniform access structures. We achieve the following results:A secret-sharing scheme for k-uniform access structures for large secrets in which the share size is $$O(k^2)$$ times the size of the secret.A linear secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$\tilde{O}(2^{h(k/n)n/2})$$ (where h is the binary entropy function). By counting arguments, this construction is optimal (up to polynomial factors).A secret-sharing scheme for k-uniform access structures for a binary secret in which the share size is $$2^{\tilde{O}(\sqrt{k \log n})}$$.
Our third contribution is a construction of ad-hoc PSM protocols, i.e., PSM protocols in which only a subset of the parties will compute a function on their inputs. This result is based on ideas we used in the construction of secret-sharing schemes for k-uniform access structures for a binary secret.

2019

JOFC

The Communication Complexity of Private Simultaneous Messages, Revisited
Abstract

Private simultaneous message (PSM) protocols were introduced by Feige, Kilian, and Naor (STOC ’94) as a minimal non-interactive model for information theoretic three-party secure computation. While it is known that every function $$f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$$ f : { 0 , 1 } k × { 0 , 1 } k → { 0 , 1 } admits a PSM protocol with exponential communication of $$2^{k/2}$$ 2 k / 2 (Beimel et al., TCC ’14), the best known (non-explicit) lower-bound is $$3k-O(1)$$ 3 k - O ( 1 ) bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the $$3k-O(1)$$ 3 k - O ( 1 ) lower-bound, and proved that a random function is likely to satisfy the requirements. We revisit the FKN lower-bound and prove the following results: (Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of $$2k+O(1)$$ 2 k + O ( 1 ) bits, revealing a gap in the FKN proof. (PSM lower-bounds) We show that by imposing additional requirements, the FKN argument can be fixed leading to a $$3k-O(\log k)$$ 3 k - O ( log k ) lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran, and Prabhakaran (Crypto ’14, IEEE Information Theory ’16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error. (CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear $$\varOmega (k)$$ Ω ( k ) -bit CDS lower-bounds. As a corollary, we settle the complexity of the inner-product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto ’15).

2018

TCC

On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate
Abstract

Consider the following secret-sharing problem. Your goal is to distribute a long file s between n servers such that
$$(d-1)$$
(d-1)-subsets cannot recover the file,
$$(d+1)$$
(d+1)-subsets can recover the file, and d-subsets should be able to recover s if and only if they appear in some predefined list L. How small can the information ratio (i.e., the number of bits stored on a server per each bit of the secret) be?We advocate the study of such d-uniform access structures as a useful scaled-down version of general access structures. Our main result shows that, for constant d, any d-uniform access structure admits a secret sharing scheme with a constant asymptotic information ratio of
$$c_d$$
cd that does not grow with the number of servers n. This result is based on a new construction of d-party Conditional Disclosure of Secrets (CDS) for arbitrary predicates over n-size domain in which each party communicates at most four bits per secret bit.In both settings, previous results achieved a non-constant information ratio that grows asymptotically with n, even for the simpler (and widely studied) special case of
$$d=2$$
d=2. Moreover, our multiparty CDS construction yields the first example of an access structure whose amortized information ratio is constant, whereas its best-known non-amortized information ratio is sub-exponential, thus providing a unique evidence for the potential power of amortization in the context of secret sharing.Our main result applies to exponentially long secrets, and so it should be mainly viewed as a barrier against amortizable lower-bound techniques. We also show that in some natural simple cases (e.g., low-degree predicates), amortization kicks in even for quasi-polynomially long secrets. Finally, we prove some limited lower-bounds, point out some limitations of existing lower-bound techniques, and describe some applications to the setting of private simultaneous messages.

2018

TCC

Perfect Secure Computation in Two Rounds
Abstract

We show that any multi-party functionality can be evaluated using a two-round protocol with perfect correctness and perfect semi-honest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semi-honest MPC, resolving a longstanding open question (cf. Ishai and Kushilevitz, FOCS 2000). The protocol is efficient for $${\mathrm {NC}}^1$$NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security.Technically, we extend and relax the notion of randomized encoding to specifically address multi-party functionalities. The property of a multi-party randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f.

2017

CRYPTO

2016

CRYPTO

2009

CRYPTO

#### Program Committees

- Eurocrypt 2020
- TCC 2019
- Crypto 2018
- TCC 2017
- TCC 2015
- Crypto 2012
- TCC 2011

#### Coauthors

- Barak Arkis (2)
- Jonathan Avron (1)
- Amos Beimel (1)
- Andrey Bogdanov (1)
- Andrej Bogdanov (1)
- Zvika Brakerski (4)
- Chris Brzuska (1)
- David Cash (1)
- Ivan Damgård (1)
- Oriol Farràs (1)
- Thomas Holenstein (2)
- Yuval Ishai (5)
- Eliran Kachlon (1)
- Eyal Kushilevitz (4)
- Manoj Mishra (2)
- Yoni Moses (2)
- Michael Nielsen (1)
- Oded Nir (1)
- Arpita Patra (1)
- Chris Peikert (1)
- Naty Peter (1)
- Pavel Raykov (6)
- Alon Rosen (2)
- Amit Sahai (1)
- Ofer Shayevitz (2)
- Rotem Tsabary (2)
- Prashant Nalini Vasudevan (1)
- Brent Waters (1)
- Eyal Widder (1)
- Lior Zichron (1)