International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Daniel Escudero

Publications

Year
Venue
Title
2021
CRYPTO
Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings 📺
Daniel Escudero Eduardo Soria-Vazquez
We construct the first efficient MPC protocol that only requires black-box access to a non-commutative ring $R$. Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir's secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (\textit{IEEE Transactions on Information Theory, 2013}). When the center of the ring contains a set $A = \{\alpha_0, \ldots, \alpha_n\}$ such that $\forall i \neq j, \alpha_i - \alpha_j \in R^*$, the resulting secret sharing scheme is strongly multiplicative and we can generalize existing constructions over finite fields without much trouble. Most of our work is devoted to the case where the elements of $A$ do not commute with all of $R$, but they just commute with each other. For such rings, the secret sharing scheme cannot be linear ``on both sides" and furthermore it is not multiplicative. Nevertheless, we are still able to build MPC protocols with a concretely efficient online phase and black-box access to $R$. As an example we consider the ring $\mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z})$, for which when $m > \log(n+1)$, \enote{maybe adapt/simplify the following claim as the comparison requires some nuances} we obtain protocols that require around $\lceil\log(n+1)\rceil/2$ less communication and $2\lceil\log(n+1)\rceil$ less computation than the state of the art protocol based on Circuit Amortization Friendly Encodings (Dalskov, Lee and Soria-Vazquez, \textit{ASIACRYPT 2020}). In this setting with a ``less commutative" $A$, our black-box preprocessing phase has a less practical complexity of $\poly(n)$. Due to this, we additionally provide specialized, concretely efficient preprocessing protocols for $R = \mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z})$ that exploit the structure of the matrix ring.
2021
ASIACRYPT
Improved single-round secure multiplication using regenerating codes
In 2016, Guruswami and Wootters showed Shamir's secret-sharing scheme defined over an extension field has a regenerating property. Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares. Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been published. We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds. Concretely, we present a protocol that obliviously evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds, in the amortized setting of parallel evaluations, with $o(n^2)$ ring elements communicated per multiplication. Our protocol makes use of function-dependent preprocessing, and is secure against the maximal adversary corrupting $t < n/2$ parties. All existing approaches in this setting have complexity $\Omega(n^2)$. Moreover, we extend some of the theory on regenerating codes to Galois rings. It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code. We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir's scheme over Galois rings.
2021
TCC
Information-Theoretically Secure MPC against Mixed Dynamic Adversaries
Ivan Damgård Daniel Escudero Divya Ravi
In this work we consider information-theoretically secure MPC against an \emph{mixed} adversary who can corrupt $t_p$ parties passively, $t_a$ parties actively, and can make $t_f$ parties fail-stop. With perfect security, it is known that every function can be computed securely if and only if $3t_a + 2t_p + t_f < n$, for statistical security the bound is $2t_a + 2t_p + t_f < n$. These results say that for each given set of parameters $(t_a, t_p, t_f)$ respecting the inequality, there exists a protocol secure against this particular choice of corruption thresholds. In this work we consider a \emph{dynamic} adversary. Here, the goal is a \emph{single} protocol that is secure, no matter which set of corruption thresholds $(t_a, t_p, t_f)$ from a certain class is chosen by the adversary. A dynamic adversary can choose a corruption strategy after seeing the protocol and so is much stronger than a standard adversary. Dynamically secure protocols have been considered before for computational security. Also the information theoretic case has been studied, but only considering non-threshold adversaries, leading to inefficient protocols. We consider threshold dynamic adversaries and information theoretic security. For statistical security we show that efficient dynamic secure function evaluation (SFE) is possible if and only if $2t_a + 2t_p + t_f < n$, but any dynamically secure protocol must use $\Omega(n)$ rounds, even if only fairness is required. Further, general reactive MPC is possible if we assume in addition that $2t_a+2t_f \leq n$, but fair reactive MPC only requires $2t_a + 2t_p + t_f < n$. For perfect security we show that both dynamic SFE and verifiable secret sharing (VSS) are impossible if we only assume $3t_a + 2t_p + t_f < n$ and remain impossible even if we also assume $t_f=0$. In fact even SFE with security with abort is impossible in this case. On the other hand, perfect dynamic SFE with guaranteed output delivery (G.O.D.) is possible when either $t_p = 0$ or $t_a = 0$ i.e. if instead we assume $3t_a+t_f < n$ or $2t_p +t_f < n$. Further, perfect dynamic VSS with G.O.D. is possible under the stronger conditions $3t_a + 3/2t_f \leq n$ or $2t_p + 2t_f \leq n$. These conditions are also sufficient for perfect reactive MPC. On the other hand, because perfect fair VSS only requires $3t_a+2t_p+t_f< n$, perfect reactive MPC is possible whenever perfect SFE is.
2020
CRYPTO
Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits 📺
This work introduces novel techniques to improve the translation between arithmetic and binary data types in multi-party computation. To this end, we introduce a new approach to performing these conversions, using what we call \emph{extended doubly-authenticated bits} (edaBits), which correspond to shared integers in the arithmetic domain whose bit decomposition is shared in the binary domain. These can be used to considerably increase the efficiency of non-linear operations such as truncation, secure comparison and bit-decomposition. Our eDaBits are similar to the \emph{daBits} technique introduced by Rotaru et al.~(Indocrypt 2019). However, our main observations are that (1) applications that benefit from daBits can also benefit from edaBits in the same way, and (2) we can generate edaBits directly in a much more efficeint way than computing them directly from a set of DaBits. Technically, the second contribution is much more challenging, and involves a novel cut and choose technique that may be of independent interest, and requires taking advantage of natural tamper-resilient properties of binary circuits that occur in our construction to obtain the best level of efficiency. Finally, we show how our eDaBits can be applied to efficiently implement various non-linear protocols of interest, and we thoroughly analyze their correctness for both signed and unsigned integers. The results of this work can be applied to any corruption threshold, although they seem best suited to dishonest majority protocols such as SPDZ. We implement and benchmark our constructions, and experimentally verify that our technique yield a substantial increase in effiency. Our eDaBits save in communication by a factor that lies between $2$ and $170$ for secure comparisons with respect to a purely arithmetic approach, and between $2$ and $60$ with respect to using daBits. Improvements in throughput per second are more subdued but still as high as a factor of $47$. We also apply our novel machinery to the tasks of biometric matching and convolutional neural networks, obtaining a noticeable improvement as well.
2020
ASIACRYPT
Asymptotically Good Multiplicative LSSS over Galois Rings and Applications to MPC over Z/p^k Z 📺
We study information-theoretic multiparty computation (MPC) protocols over rings Z/p^k Z that have good asymptotic communication complexity for a large number of players. An important ingredient for such protocols is arithmetic secret sharing, i.e., linear secret-sharing schemes with multiplicative properties. The standard way to obtain these over fields is with a family of linear codes C, such that C, $C^\perp$ and C^2 are asymptotically good (strongly multiplicative). For our purposes here it suffices if the square code C^2 is not the whole space, i.e., has codimension at least 1 (multiplicative). Our approach is to lift such a family of codes defined over a finite field F to a Galois ring, which is a local ring that has F as its residue field and that contains Z/p^k Z as a subring, and thus enables arithmetic that is compatible with both structures. Although arbitrary lifts preserve the distance and dual distance of a code, as we demonstrate with a counterexample, the multiplicative property is not preserved. We work around this issue by showing a dedicated lift that preserves \emph{self-orthogonality} (as well as distance and dual distance), for p > 2. Self-orthogonal codes are multiplicative, therefore we can use existing results of asymptotically good self-dual codes over fields to obtain arithmetic secret sharing over Galois rings. For p = 2 we obtain multiplicativity by using existing techniques of secret-sharing using both C and $C^\perp$, incurring a constant overhead. As a result, we obtain asymptotically good arithmetic secret-sharing schemes over Galois rings. With these schemes in hand, we extend existing field-based MPC protocols to obtain MPC over Z/p^k Z, in the setting of a submaximal adversary corrupting less than a fraction 1/2 - \varepsilon of the players, where \varepsilon > 0 is arbitrarily small. We consider 3 different corruption models, and obtain O(n) bits communicated per multiplication for both passive security and active security with abort. For full security with guaranteed output delivery we use a preprocessing model and get O(n) bits per multiplication in the online phase and O(n log n) bits per multiplication in the offline phase. Thus, we obtain true linear bit complexities, without the common assumption that the ring size depends on the number of players.
2019
TCC
Efficient Information-Theoretic Secure Multiparty Computation over $\mathbb {Z}/p^k\mathbb {Z}$ via Galois Rings
At CRYPTO 2018, Cramer et al. introduced a secret-sharing based protocol called SPD$$\mathbb {Z}_{2^k}$$ that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo $$2^k$$, thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust Secure Multiparty Computation over $$\mathbb {Z}/p^{k}\mathbb {Z}$$ (for any prime p and positive integer k) that is perfectly secure against active adversaries corrupting a fraction of at most 1/3 players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most 1/2 players.
2018
CRYPTO
SPD$\mathbb {Z}_{2^k}$: Efficient MPC mod $2^k$ for Dishonest Majority 📺
Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo $$2^{k}$$, which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest.We present a new scheme for information-theoretic MACs that are homomorphic modulo $$2^k$$, and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo $$2^k$$ instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.