Compact Verifiably Multiplicative Secret Sharing

A d-multiplicative secret sharing (d-MSS) scheme over a finite field allows the players to multiply d shared secrets without recovering the secrets by converting their shares locally into an additive sharing of the product [Journal of Cryptology, 2010]. A verifiably d-MSS (d-VMSS) further enables the players to locally generate an additive sharing of a proof that the output (rather than each share) is correct [IEEE Trans. on Information Theory, 2019]. In the most efficient construction known so far, while a share of the output is a single element of the finite field, a proof of correctness consists of two or more elements. In this paper, we study (in)feasibility of a single-element proof of correctness. First, we derive a sufficient condition on a proof-generation function, referred to as multiplicative-only homomorphism (MoH). Secondly, we show the concrete family of MoHs, meaning that the condition is satisfied. Then, we present a generic construction of d-VMSS from any d-MSS and any MoH. Finally, we show concrete instantiations of d-VMSS that realize a single-element proof of correctness.