Re: Attack on Verifiable Secret Sharing scheme

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 07/29/05

  • Next message: Anonymous: "Re: Barcode Email" 
    Date: Fri, 29 Jul 2005 03:55:18 +0000 (UTC)

    Ann Brandon wrote:
    >So, there are n partys P_1, ... , P_n and a dealer, who shares a secret
    >x in a verifiable (t+1,n)-threshold manner. That means party P_i gets
    >share s_i = f(i) from the dealer.
    >Now the dealer is destroyed. Some time later a new party P_{n+1} wants
    >to have a share s_{n+1}, so what to do now? The dealer can't do the job,
    >cause it is not available anymore.
    >A possibility to solve this problem is that P_{n+1} chooses a set of
    >(t+1)-partys T. Each party P_i of T sends the value ss_i = l_i(n+1)*s_i
    >(where l_i(n+1) is the lagrange factor for polynomial interpolation for
    >the value s_{n+1}) to P_{n+1}, who then can calculate her share as:
    >s_{n+1} = \sum_{P_i \in T} ss_i.
    >The problem with this scheme is now that the values l_i(n+1) are known
    >to each party, so P_{n+1} can calculate the shares of all partys from T.
    >If P_{n+1} is corrupted, then the adversary gets all shares from honest
    >partys from T. This is a very big problem.

    Can we do the following? Have each party of T, say party i, compute a
    random t+1-out-of-n+1 verifiable sharing of zero, say
      0 ---> (r_{i,1},..,r_{i,n+1}).
    For j=1,..,n, send r_{i,j} to party j, who adds r_{i,j} to their share.
    Also send send l_i(n+1)*s_i + r_{j,n+1} to party n+1, whose share is the
    sum of all of these quantities. Since this is a VSS, parties 1,..,n can
    verify that each quantity r_{i,j} they receive is accurate, and after the
    whole thing is finished, party n+1 can verify that their final share is
    accurate. Does this work?

    This requires O(t) broadcasts of messages of size O(t) (you would say
    O(t^2) broadcasts (of messages of size O(1)), along with O(tn) unicasts
    of messages of size O(1).

    BTW, the literature on "proactive security" may be relevant here.

  • Next message: Anonymous: "Re: Barcode Email"

    Relevant Pages