6
$\begingroup$

I am a mathematician with no background in crypto or security. For work, I had to read up Chap.13 "Secret Sharing Schemes" in Stinson's Cryptography (3rd ed). My question is about a simplification of the so-called Monotone Circuit Construction.

In Sect. 13.2 Stinson discusses the case that you have $w$ participants $\mathcal{P} = \{ P_1, \ldots, P_w \}$ and you want to realize the access structure $\Gamma \subseteq 2^{\mathcal{P}}$, which is just an arbitrary set of subsets of $\mathcal{P}$. This means, exactly the subsets in $\Gamma$ should get access to the secret and no other group.

The method he presents was invented by Benaloh & Leichter (CRYPTO '88) and is called (by Stinson) the Monotone Circuit Construction. The idea is simple: You build a monotone Boolean circuit that "recognizes" $\Gamma$ and then compute the shares based on the wiring of the circuit (see Algorithm 13.1).

All this is fine, but it seems a bit overblown. Why not do the following? For each group of $\Gamma$ with $t$ participants you just "split" the secret number randomly among them (meaning, you use a $(t,t)$-Threshold Scheme) -- and you're done. This even should be a special case of the Monotone Circuit Construction.

I have two questions about this:

  1. Is the above suggestion secure?
  2. What's the advantage of the more general approach as presented by Stinson?
Improve this question
$\endgroup$
6
  • $\begingroup$ Your suggestion isn't well defined. What is $t$ for an arbitrary collection of subsets in the powerset? $\endgroup$
    – kodlu
    Feb 22, 2017 at 6:08
  • $\begingroup$ @kodlu: It should be well-defined. $t$ depends on the particular group (i.e., subset) in $\Gamma$. $\endgroup$
    – eins6180
    Feb 22, 2017 at 6:15
  • 1
    $\begingroup$ Your approach is probably secure (in an information theoretic sense) but it blows up the number of shares that a participant needs to store --- it is equal the number of groups it participates in. This renders the secret sharing scheme inefficient. The approach using boolean formulae is in this sense efficient. $\endgroup$
    – ckamath
    Feb 22, 2017 at 8:10
  • $\begingroup$ Note that one can extend the result of Benaloh and Leichter to boolean circuits, assuming bounded adversaries, using a folklore technique by Yao (see On the Power of Computational Secret Sharing, by Vinod et al.). $\endgroup$
    – ckamath
    Feb 22, 2017 at 8:12
  • $\begingroup$ @Occams_Trimmer: But why are MCCs more efficient? Theorem 13.2 is basically the same bound, right? Or is it possible to prove better bounds? $\endgroup$
    – eins6180
    Feb 22, 2017 at 8:18

1 Answer 1

Reset to default
4
$\begingroup$
  1. Is the above suggestion secure?

Sure; for any group that doesn't have a subset that's a group in $\Gamma$, they don't have enough information to reconstruct the shared secret.

Your approach is indeed a subset of Benaloh's, where you constrain the circuit to be a layer of AND gates, followed by a single OR gate.

  1. 2.What's the advantage of the more general approach as presented by Stinson?

The size of the shares; your scheme requires a share size for an individual that is proportional to the number of groups it's a member of. For example, if the access structure is "any of 1000 members of group A, plus any of 1000 members of group B, plus any of 1000 members of group C", then everyone's shares will be 1,000,000 times the size of the shared secret; with Benaloh's method, each share need not be any larger than the shared secret.

Of course, if the access structure is "any 500 of the 1000 member groups", you're far better off with Shamir's method, rather than either of these two...

Improve this answer
$\endgroup$
0

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.