[cryptography] A secret sharing consensus protocol (or leader election protocol)

Steve Weis steveweis at gmail.com
Fri Jul 19 09:15:41 EDT 2013


This sounds like verifiable secret sharing with an honest majority.
Here's a sampling of a few papers on related topics:

"Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems"
http://eprint.iacr.org/2002/134.pdf

"Distributed Private-Key Generators for Identity-Based Cryptography"
http://www.cypherpunks.ca/~iang/pubs/DPKG-SCN10.pdf

"Verifiable Secret Sharing and Multiparty Protocols with Honest Majority"
http://cvs.cs.umd.edu/~gasarch/secretsharing/rabinVSS.pdf

"Multiparty Computation with Faulty Majority"
http://groups.csail.mit.edu/cis/pubs/shafi/1989-focs.pdf

"Optimal Algorithms for Byzantine Agreement"
http://dl.acm.org/citation.cfm?id=62225



On Thu, Jul 18, 2013 at 8:57 PM, Tony Arcieri <tony.arcieri at gmail.com> wrote:
> Has there been any work with combining Shamir-style secret sharing with
> consensus protocols like Paxos and Raft (or leader election protocols like
> Omega Meets Paxos)?
>
> The idea would be to have a network of n peers, who share a secret where t=2
> shares are required to reassemble the original secret. This secret is used
> to sign new values when a group consensus is reached via a Paxos-like
> protocol.
>
> In this scheme, a "proposer" would give its secret share, along with a
> proposed new value, to "acceptor" nodes, who can reassemble the entire
> secret. If they accept the new value, they can sign it with the secret, then
> immediately erase it. If we use a deterministic signature algorithm like
> Ed25519, every acceptor taking part in the consensus protocol can produce
> the same signed version of the proposed new value. They can then continue
> with the consensus protocol's accept phase. The result will be a quorum on a
> signed value (or a consensus failure if quorum can't be reached, of course)
>
> Let's assume a malicious entity gains control of one and only one of the
> nodes. They are now able to propose new values, so they can manipulate the
> peer network by proposing malicious values which will get accepted by the
> rest of the group.
>
> However, they do not *immediately* learn the private key. They would only
> learn the private key if any other node were to propose a value which
> contained their secret share.
>
> -- alternatively --
>
> Secret sharing could be combined with a leader election protocol. In this
> scheme, the leader and only the leader would learn the shared secret. All
> proposed values would have to be approved and signed by the leader.
>
> I'm not sure I like this as much though. The leader is a single point of
> failure, and an attacker could maliciously force a leader election through
> e.g. DoS, having compromised only one other host directly.
>
> --
> Tony Arcieri
>
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
>


More information about the cryptography mailing list