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"

    Relevant Pages

    • Re: Rolling codes and vehicle locks
      ... code, sequence number, and a "secret". ... Unless the car transmits a unique shared secret key to the fob (very ...
    • Re: Strange Hotel Regional TV set up
      ... The remote control wouldn't allow re-tuning ... that doesn't have some "secret" sequence or combination yet ... ... I often either plug the aerial into my laptop or if I can get at the ...
    • Re: secret sharing / voting
      ... > Does anybody know a secret sharing scheme (or something else that I ... Create a random bit sequence of length n. ... Now you create "yes" votes of length n by selecting some one bits ...
    • Re: Unique number generation
      ... If secret is the same for all numbers then val is unique if ... Encryption is a one-one and onto map. ... >the sequence number either. ... Otherwise how could you decrypt? ...
    • Re: one last election thing....
      ... I missed it and wanted to vote for Norm ... for Alternate Tuning Tsar. ... Sorell for Ambassador to New Zealand; Ken Cashion for Director of Secret ... We aren't talking about the election results? ...