Re: secret sharing / voting

From: Michael Brown (see_at_signature.below)
Date: 06/26/03

  • Next message: AE: "Re: secret sharing / voting"
    Date: Thu, 26 Jun 2003 21:14:19 +1200

    "Jesper Nordenberg" <> wrote in message
    > (Markus) wrote in message
    > > Does anybody know a secret sharing scheme (or something else that I
    > > can use to solve the above problem) that could be used?
    > How about this one:
    > Create a random bit sequence of length n. Randomly pick n/2 bits that
    > you will ignore in the sequence. The other n/2 bits are the secret
    > key. Now you create "yes" votes of length n by selecting some one bits
    > from the sequence and setting the other bits to zero. You should
    > select the bits so that a given number (but no less) of "yes" votes
    > always contains all the one bits in the secret. "no" votes of length n
    > are created by selecting one bits from the ignored bit set. To get the
    > secret just OR together all votes, discard the ignored bits and you
    > will get the secret.

    This fails on a couple of counts ... (1) is that the secret can be
    determined by less people than ideal by brute-forcing any "0" bits left in
    the secret, though a long secret (where each key contributes a large number
    of 1s to the final value) would fix this, and (2) is that the voters can be
    identified by masking the vote against inverse of the ignored mask. If it's
    all zero (ie: no contribution to the final secret), then that person voted
    against recreating the secret.

    AC2 has a bit on schemes that do work, but it's all a bit to heavy to
    summarise in a newgroup article. The ones it mentions are:
    [] The LaGrange Interpolating Polynomial Scheme - Too complex to summarise
    in one line, but as good as OTP
    [] Vector Scheme - Invented by George Blakley, basically each vote is an
    n-dimensional plane (where n is the required number of people), and the
    secret is the intersection of n planes.
    [] Asmuth-Bloom - Uses the Chinese remainder theorem to do some stuff ...
    [] Karnin-Greene-Hellman - Solving of a n*n system of linear equations.

    It also goes on to reference things about detecting cheaters and also more
    advanced threshhold stuff.

    Michael Brown : OOS/RSI software and more :)
    Add michael@ to - My inbox is always open

  • Next message: AE: "Re: secret sharing / voting"