# Re: secret sharing / voting

**From:** Michael Brown (*see_at_signature.below*)

**Date:** 06/26/03

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

**Previous message:**jsavard_at_ecn.ab.ca: "Re: Authenticated Encryption Modes"**In reply to:**Jesper Nordenberg: "Re: secret sharing / voting"**Next in thread:**Jesper Nordenberg: "Re: secret sharing / voting"**Reply:**Jesper Nordenberg: "Re: secret sharing / voting"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Thu, 26 Jun 2003 21:14:19 +1200

"Jesper Nordenberg" <megagurka@yahoo.com> wrote in message

news:9c838fb.0306252328.54e6e1d6@posting.google.com...

*> markus-1977@gmx.net (Markus) wrote in message
*

news:<ad66a92b.0306251111.45ced000@posting.google.com>...

*> > 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

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

**Previous message:**jsavard_at_ecn.ab.ca: "Re: Authenticated Encryption Modes"**In reply to:**Jesper Nordenberg: "Re: secret sharing / voting"**Next in thread:**Jesper Nordenberg: "Re: secret sharing / voting"**Reply:**Jesper Nordenberg: "Re: secret sharing / voting"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]