International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Chen Yuan

Publications

Year
Venue
Title
2020
TCC
Robust Secret Sharing with Almost Optimal Share Size and Security Against Rushing Adversaries 📺
Serge Fehr Chen Yuan
We show a robust secret sharing scheme for a maximal threshold $t < n/2$ that features an optimal overhead in share size, offers security against a rushing adversary, and runs in polynomial time. Previous robust secret sharing schemes for $t < n/2$ either suffered from a suboptimal overhead, offered no (provable) security against a rushing adversary, or ran in superpolynomial time.
2020
TCC
On the Complexity of Arithmetic Secret Sharing 📺
Since the mid 2000s, asymptotically-good strongly-multiplicative linear (ramp) secret sharing schemes over a fixed finite field have turned out as a central theoretical primitive in numerous constant-communication-rate results in multi-party cryptographic scenarios, and, surprisingly, in two-party cryptography as well. Known constructions of this most powerful class of arithmetic secret sharing schemes all rely heavily on algebraic geometry (AG), i.e., on dedicated AG codes based on asymptotically good towers of algebraic function fields defined over finite fields. It is a well-known open question since the first (explicit) constructions of such schemes appeared in CRYPTO 2006 whether the use of ``heavy machinery'' can be avoided here. i.e., the question is whether the mere existence of such schemes can also be proved by ``elementary'' techniques only (say, from classical algebraic coding theory), even disregarding effective construction. So far, there is no progress. In this paper we show the theoretical result that, (1) {\em no matter whether this open question has an affirmative answer or not}, these schemes {\em can} be constructed explicitly by {\em elementary algorithms} defined in terms of basic algebraic coding theory. This pertains to all relevant operations associated to such schemes, including, notably, the generation of an instance for a given number of players $n$, as well as error correction in the presence of corrupt shares. We further show that (2) the algorithms are {\em quasi-linear time} (in $n$); this is (asymptotically) significantly more efficient than the known constructions. That said, the {\em analysis} of the mere termination of these algorithms {\em does} still rely on algebraic geometry, in the sense that it requires ``blackbox application'' of suitable {\em existence} results for these schemes. Our method employs a nontrivial, novel adaptation of a classical (and ubiquitous) paradigm from coding theory that enables transformation of {\em existence} results on asymptotically good codes into {\em explicit construction} of such codes via {\em concatenation}, at some constant loss in parameters achieved. In a nutshell, our generating idea is to combine a cascade of explicit but ``asymptotically-bad-yet-good-enough schemes'' with an asymptotically good one in such a judicious way that the latter can be selected with exponentially small number of players in that of the compound scheme. This opens the door to efficient, elementary exhaustive search. In order to make this work, we overcome a number of nontrivial technical hurdles. Our main handles include a novel application of the recently introduced notion of Reverse Multiplication-Friendly Embeddings (RMFE) from CRYPTO 2018, as well as a novel application of a natural variant in arithmetic secret sharing from EUROCRYPT 2008.
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
EUROCRYPT
Towards Optimal Robust Secret Sharing with Security Against a Rushing Adversary 📺
Serge Fehr Chen Yuan
Robust secret sharing enables the reconstruction of a secret-shared message in the presence of up to t (out of n) incorrect shares. The most challenging case is when $$n = 2t+1$$, which is the largest t for which the task is still possible, up to a small error probability $$2^{-\kappa }$$ and with some overhead in the share size.Recently, Bishop, Pastro, Rajaraman and Wichs [3] proposed a scheme with an (almost) optimal overhead of $$\widetilde{O}(\kappa )$$. This seems to answer the open question posed by Cevallos et al. [6] who proposed a scheme with overhead of $$\widetilde{O}(n+\kappa )$$ and asked whether the linear dependency on n was necessary or not. However, a subtle issue with Bishop et al.’s solution is that it (implicitly) assumes a non-rushing adversary, and thus it satisfies a weaker notion of security compared to the scheme by Cevallos et al. [6], or to the classical scheme by Rabin and BenOr [13].In this work, we almost close this gap. We propose a new robust secret sharing scheme that offers full security against a rushing adversary, and that has an overhead of $$O(\kappa n^\varepsilon )$$, where $$\varepsilon > 0$$ is arbitrary but fixed. This $$n^\varepsilon $$-factor is obviously worse than the $$\mathrm {polylog}(n)$$-factor hidden in the $$\widetilde{O}$$ notation of the scheme of Bishop et al. [3], but it greatly improves on the linear dependency on n of the best known scheme that features security against a rushing adversary (when $$\kappa $$ is substantially smaller than n).A small variation of our scheme has the same $$\widetilde{O}(\kappa )$$ overhead as the scheme of Bishop et al. and achieves security against a rushing adversary, but suffers from a (slightly) superpolynomial reconstruction complexity.
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
Amortized Complexity of Information-Theoretically Secure MPC Revisited 📺
A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general n-player MPC shows how one may trade the adversary thresholdt against amortized communication complexity, by using a so-called packed version of Shamir’s scheme. For e.g. the BGW-protocol (with active security), this trade-off means that if $$t + 2k -2 < n/3$$ t+2k-2<n/3, then kparallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGW-execution.In this paper we propose a novel paradigm for amortized MPC that offers a different trade-off, namely with the size of the field of the circuit which is securely computed, instead of the adversary threshold. Thus, unlike the Franklin-Yung paradigm, this leaves the adversary threshold unchanged. Therefore, for instance, this paradigm may yield constructions enjoying the maximal adversary threshold $$\lfloor (n-1)/3 \rfloor $$ ⌊(n-1)/3⌋ in the BGW-model (secure channels, perfect security, active adversary, synchronous communication).Our idea is to compile an MPC for a circuit over an extension field to a parallel MPC of the same circuit but with inputs defined over its base field and with the same adversary threshold. Key technical handles are our notion of reverse multiplication-friendly embeddings (RMFE) and our proof, by algebraic-geometric means, that these are constant-rate, as well as efficient auxiliary protocols for creating “subspace-randomness” with good amortized complexity. In the BGW-model, we show that the latter can be constructed by combining our tensored-up linear secret sharing with protocols based on hyper-invertible matrices á la Beerliova-Hirt (or variations thereof). Along the way, we suggest alternatives for hyper-invertible matrices with the same functionality but which can be defined over a large enough constant size field, which we believe is of independent interest.As a demonstration of the merits of the novel paradigm, we show that, in the BGW-model and with an optimal adversary threshold $$\lfloor (n-1)/3 \rfloor $$ ⌊(n-1)/3⌋, it is possible to securely compute a binary circuit with amortized complexity O(n) of bits per gate per instance. Known results would give $$n \log n$$ nlogn bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small $$\epsilon >0$$ ϵ>0 fraction below 1/3), this is improved to O(1) bits instead of O(n).
2017
EUROCRYPT