[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"

"Distributed Private-Key Generators for Identity-Based Cryptography"

"Verifiable Secret Sharing and Multiparty Protocols with Honest Majority"

"Multiparty Computation with Faulty Majority"

"Optimal Algorithms for Byzantine Agreement"

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