Verifiably Multiplicative Secret Sharing | Information Theoretic Security (2024)

• Authors:
• Maki Yoshida NICT, Tokyo, Japan

  NICT, Tokyo, Japan

  View Profile

  ,
• Satoshi Obana Hosei University, Tokyo, Japan

  Hosei University, Tokyo, Japan

  View Profile

Information Theoretic Security: 10th International Conference, ICITS 2017, Hong Kong, China, November 29 – December 2, 2017, ProceedingsNov 2017Pages 73–82https://doi.org/10.1007/978-3-319-72089-0_5

Abstract

Barkol et al.(Journal of Cryptology, 2010) introduced the notion of d-multiplicative secret sharing (d-MSS), which allows the players to multiply shared d secrets by converting their shares locally into an additive sharing of the product, and proved that d-MSS among n players is possible if and only if no d unauthorized sets of players cover the whole set of players (type $Q_d$). Although this result implies some limitations on secret sharing in the context of MPC, the d-multiplicative property is still useful for simplifying complex tasks of MPC by computing the product of d field elements directly and non-interactively. In this paper, to further improve usefulness, we introduce and study the verifiability of multiplication, which is mainly formalized for the motivated applications of d-MSS. Informally, a d-MSS scheme is verifiable if the scheme enables the players to locally generate an additive sharing of proof that the summed value is the correct product of shared d secrets. First, we prove that verifiably d-MSS among n players is possible if no $d+1$ unauthorized sets of players cover the whole set of players (type $Q_{d+1}$) where the error probability is zero. That is, a larger number of players n is required. In addition, in the proposed error-free scheme, the share size of a proof increases with the number of unauthorized sets. To achieve the optimal bound on n of d-MSS (type $Q_d$) efficiently, we accept an error probability. We prove that verifiably d-MSS among n players is possible if and only if no d unauthorized sets of players cover the whole set of players (type $Q_d$) where the error probability is non-zero but is chosen arbitrarily. In the proposed scheme, each share of a proof consists of only two field elements. From these results, we can see that there is a tradeoff between usability and correctness (i.e.either no additional players or no error). Because these schemes do not require any setup or interaction, we can freely select them as the situation demands.

Digital Edition