Is multiplicative secret sharing secure?

Question

I suggested mulitiplicative secret sharing in an answer to another question, but noted that I wasn't sure if it was even secure and was hoping someone would comment on the security. Since no one did, I thought I'd ask it as a separate question.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

To share $s$ with $k$ parties such that all $k$ are required to reconstruct $s$, we choose $s_1,s_2,\dots,s_{k-1}\in\mathbb{Z}_p^*$ at random and set $s_k=s*(s_1*s_2*\dots*s_{k-1})^{-1}$. Thus, $s=s_1*s_2*\dots*s_{k}$.

What is the security of this secret sharing method? Is it information-theoretic? In other words, if fewer than $k$ parties get to gether they should (either for a computationally bounded or possibly an unbounded adversary) learn no additional information about $s$.

Answer 1

Assuming that $p$ is prime, then you are in a cyclic group. Consequently, this is identical to considering the shares $s_i$ as "exponents" of a generator $g$ of $Z_p^*$.

Now we can write: $s_1 = g^{s'_1}, \ldots,s_{k}=g^{s'_{k}}$ and $s=\prod_{i=1}^{k} s_i$

Or we can view this as: $s = g^{\sum_{i=1}^{k} s'_i}$.

Consequently it looks like a perfect (= information theoretically secure) additive secret sharing scheme "in the exponent" to me.

Answer 2

It is informationally secure (assuming $p$ is prime).

In general, we can create an $(n,n)$ secret sharing method (that is, one that generates $n$ shares, and which requires all $n$ shares to reconstruct the secret) by taking any group $G$ with group operation $*$, mapping the shared secret into a group member $s$, selecting $n-1$ random (uniformly distributed) group elements $s_i$, and publishing the shares $s_1, s_2, ..., s_{n-1}$ and $s * (s_1 * s_2 * ... * s_{n-1})^{-1}$.

This is informationally secure, because if we have $n-1$ shares, then we still don't have any information on the shared secret $s$; for each possible value of $s$, there is a possible value of the missing share.