### Homomorphic Secret Sharing for Multipartite and General Adversary Structures Supporting Parallel Evaluation of Low-degree Polynomials

Reo Eriguchi and Koji Nuida

##### Abstract

Homomorphic secret sharing (HSS) for a function $f$ allows input parties to distribute shares for their private inputs and then locally compute output shares from which the value of $f$ is recovered. HSS can be directly used to obtain a two-round multiparty computation (MPC) protocol for possibly non-threshold adversary structures whose communication complexity is independent of the size of $f$. In this paper, we propose two constructions of HSS schemes supporting parallel evaluation of a single low-degree polynomial and tolerating multipartite and general adversary structures. Our multipartite scheme tolerates a wider class of adversary structures than the previous multipartite one in the particular case of a single evaluation and has exponentially smaller share size than the general construction. While restricting the range of tolerable adversary structures (but still applicable to non-threshold ones), our schemes perform $\ell$ parallel evaluations with communication complexity approximately $\ell/\log\ell$ times smaller than simply using $\ell$ independent instances. We also formalize two classes of adversary structures taking into account real-world situations to which the previous threshold schemes are inapplicable. Our schemes then perform $O(m)$ parallel evaluations with almost the same communication cost as a single evaluation, where $m$ is the number of parties.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in Asiacrypt 2021
Keywords
Homomorphic secret sharingGeneral adversary structureParallel evaluation
Contact author(s)
reo-eriguchi @ g ecc u-tokyo ac jp
History
Short URL
https://ia.cr/2021/1395

CC BY

BibTeX

@misc{cryptoeprint:2021/1395,
author = {Reo Eriguchi and Koji Nuida},
title = {Homomorphic Secret Sharing for Multipartite and General Adversary Structures Supporting Parallel Evaluation of Low-degree Polynomials},
howpublished = {Cryptology ePrint Archive, Paper 2021/1395},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1395}},
url = {https://eprint.iacr.org/2021/1395}
}

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