Re: secret sharing / voting
From: Michael Brown (see_at_signature.below)
Date: Thu, 26 Jun 2003 21:14:19 +1200
"Jesper Nordenberg" <firstname.lastname@example.org> wrote in message
> email@example.com (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 www.emboss.co.nz : OOS/RSI software and more :) Add michael@ to emboss.co.nz - My inbox is always open