### Improved single-round secure multiplication using regenerating codes

Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damgård, and Chaoping Xing

##### 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 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Keywords
Multiparty ComputationRegenerating CodesSecure Multiplication
Contact author(s)
daniel escudero @ protonmail com
m a abspoel @ cwi nl
History
2021-09-20: revised
See all versions
Short URL
https://ia.cr/2021/253

CC BY

BibTeX

@misc{cryptoeprint:2021/253,
author = {Mark Abspoel and Ronald Cramer and Daniel Escudero and Ivan Damgård and Chaoping Xing},
title = {Improved single-round secure multiplication using regenerating codes},
howpublished = {Cryptology ePrint Archive, Paper 2021/253},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/253}},
url = {https://eprint.iacr.org/2021/253}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.