Re: [Cfrg] Additional consequences of the move to ECC (and they are good)

Hi Tom, catching up on this thread a bit late…

> On Jul 18, 2015, at 5:01 AM, Tom Ritter <tom@ritter.vg> wrote:
> 
> I've read a paper that enables generation of a single public ElGamal
> key from multiple public ElGamal keys; allowing for distributed key
> generation and decryption.  Simple question, complicated answer I'm
> sure, but is the same thing documented/possible for ECC?  Any
> pointers?

Standard verifiable [Shamir] secret sharing (VSS) techniques allow this, in either integer (ElGamal) groups or elliptic curves.  Not sure if there’s a definitive reference with “everything together in one place” though; I’d like to see one.  One implementation of most of the required mechanism is available in our advanced crypto library for Go: e.g., see http://godoc.org/github.com/DeDiS/crypto/poly <http://godoc.org/github.com/DeDiS/crypto/poly>

Classic VSS works fine for “small” groups, e.g., a few 10s of members, but won’t scale readily to large groups: to avoid a globally trusted dealer all N members must “deal” N polynomial shares to all other members, then add up everyone else’s shares, yielding O(N^2) complexity.  The work I mentioned in my earlier July 12 E-mail ("scalable collective signing”) addresses the problem of scaling VSS techniques to large groups.  It currently focuses on collective signing, but should be readily extensible to collective ElGamal encryption/decryption.  I’m happy to work with you or anyone with an interest or a burning use-case for something like this.

Cheers
Bryan

> Thanks,
> tom
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg

Re: [Cfrg] Additional consequences of the move to ECC (and they are good)

Attachment: smime.p7s