Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 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.

share|improve this answer
1  
Is it also (information theoretically) secure for the multiplicative group of the finite field $GF(2^n)$? –  mikeazo Nov 5 '13 at 15:20
    
@mikeazo: The multiplicative group of $GF(2^n)$ is a group, hence, yes, it is informationally secure. –  poncho Nov 5 '13 at 15:21
    
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? –  mikeazo Nov 5 '13 at 15:48
    
@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^*$ –  poncho Nov 5 '13 at 15:52
    
I assumed that $\mathbb{Z}_n^*$ was, by definition, elements that are co-prime to $n$. Either way, I appreciate the answer. –  mikeazo Nov 5 '13 at 15:56
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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