9
$\begingroup$

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

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Is it also (information theoretically) secure for the multiplicative group of the finite field $GF(2^n)$? $\endgroup$
    – mikeazo
    Nov 5, 2013 at 15:20
  • $\begingroup$ @mikeazo: The multiplicative group of $GF(2^n)$ is a group, hence, yes, it is informationally secure. $\endgroup$
    – poncho
    Nov 5, 2013 at 15:21
  • $\begingroup$ I guess your caveat (assuming $p$ is prime) confused me. To have a multiplicative group $p$ doesn't have to be prime. Is the issue in the case of non-prime $p$ sampling uniformly? $\endgroup$
    – mikeazo
    Nov 5, 2013 at 15:48
  • $\begingroup$ @mikeazo: the problem is that if $p$ isn't prime, then there are nonzero values that don't have multiplicative inverses. If you avoid such values, then you're fine. It's just that I don't remember off the top if elements not coprime to $n$ are considered members of $\mathbb{Z}_n^*$ $\endgroup$
    – poncho
    Nov 5, 2013 at 15:52
  • $\begingroup$ I assumed that $\mathbb{Z}_n^*$ was, by definition, elements that are co-prime to $n$. Either way, I appreciate the answer. $\endgroup$
    – mikeazo
    Nov 5, 2013 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.