## CryptoDB

### Daniel Escudero

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

More Efficient Dishonest Majority Secure Computation over $\mathbb{Z}_{2^k}$ via Galois Rings
Abstract

In this work we present a novel actively secure multiparty computation protocol in the dishonest majority setting, where the computation domain is a ring of the type $\mathbb{Z}_{2^k}$.
Instead of considering an ``extension ring'' of the form $\mathbb{Z}_{2^{k+\kappa}}$ as in SPD$\mathbb{Z}_{2^k}$ (Cramer et al, CRYPTO 2018) and its derivatives, we make use of an actual ring extension, or more precisely, a Galois ring extension $\mathbb{Z}_{p^k}[\mathtt{X}]/(h(\mathtt{X}))$ of large enough degree, in order to ensure that the adversary cannot cheat except with negligible probability.
These techniques have been used already in the context of honest majority MPC over $\mathbb{Z}_{p^k}$, and to the best of our knowledge, our work constitutes the first study of the benefits of these tools in the dishonest majority setting.
Making use of Galois ring extensions requires great care in order to avoid paying an extra overhead due to the use of larger rings.
To address this, reverse multiplication-friendly embeddings (RMFEs) have been used in the honest majority setting (e.g.~Cascudo et al, CRYPTO 2018), and more recently in the dishonest majority setting for computation over $\mathbb{Z}_2$ (Cascudo and Gundersen, TCC 2020).
We make use of the recent RMFEs over $\mathbb{Z}_{p^k}$ from (Cramer et al, CRYPTO 2021), together with adaptations of some RMFE optimizations introduced in (Abspoel et al, ASIACRYPT 2021) in the honest majority setting, to achieve an efficient protocol that only requires in its online phase $12.4k(n-1)$ bits of amortized communication complexity and one round of communication for each multiplication gate.
We also instantiate the necessary offline phase using Oblivious Linear Evaluation (OLE) by generalizing the approach based on Oblivious Transfer (OT) proposed in MASCOT (Keller et al, CCS 2016).
To this end, and as an additional contribution of potential independent interest, we present a novel technique using Multiplication-Friendly Embeddings (MFEs) to achieve OLE over Galois ring extensions using black-box access to an OLE protocol over the base ring $\mathbb{Z}_{p^k}$ without paying a quadratic cost in terms of the extension degree.
This generalizes the approach in MASCOT based on Correlated OT Extension.
Finally, along the way we also identify a bug in a central proof in MASCOT, and we implicitly present a fix in our generalized proof.

2022

TCC

Vector Commitments over Rings and Compressed $\Sigma$-Protocols
Abstract

Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) presents an ``alternative'' to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing $\Sigma$-protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of ``plug \& play'' algorithmics.
Unfortunately, their techniques are restricted to arithmetic circuits over \emph{prime} fields, which rules out the possibility of using more machine-friendly moduli such as powers of $2$, which have proven to improve efficiency in applications.
In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo \emph{any} number.
This enables the use of powers of $2$, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications.
In order to achieve this, we first present an instantiation of the main building block of the theory of compressed $\Sigma$-protocols, namely compact vector commitments.
Our construction, which may be of independent interest, is homomorphic modulo \emph{any} positive integer $m$, a result that was not known in the literature before.
Second, we generalize Compressed $\Sigma$-Protocol Theory from finite fields to $\mathbb{Z}_m$.
The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions.
Our techniques have direct application for example to verifiable computation on homomorphically encrypted data.

2021

CRYPTO

Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings
📺
Abstract

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
📺
Abstract

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
📺
Abstract

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
📺
Abstract

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
📺
Abstract

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
Abstract

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
📺
Abstract

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.

#### Coauthors

- Mark Abspoel (3)
- Thomas Attema (1)
- Ignacio Cascudo (1)
- Ronald Cramer (5)
- Ivan Damgård (6)
- Satrajit Ghosh (1)
- Marcel Keller (1)
- Rahul Rachuri (1)
- Matthieu Rambaud (1)
- Divya Ravi (1)
- Peter Scholl (2)
- Eduardo Soria-Vazquez (1)
- Chaoping Xing (4)
- Chen Yuan (3)