Re: [Cfrg] Threshold signatures

[Phillip Hallam-Baker <[e-mail]>]

On Fri, Jan 3, 2020 at 9:43 AM Bill Cox <[e-mail]> wrote:

> On Thu, Jan 2, 2020 at 4:18 PM Jeff Burdges <[e-mail]> wrote:
>
>>
>> You need pairings ala BLS signatures for a one round trip multi-signature
>> scheme.  I donno if anyone proved that but you’ll get nothing from fancy
>> zero-knowlede proof tricks among the signers obviously.  I’d expect BLS
>> smart cards for cyber-coin validators within the next couple years, if not
>> already.
>>
>> Jeff
>>
>
> You can also use this pairing scheme for rate-limited threshold
> password-authenticated key generation.  This could be useful for his
> Mathematical Mesh, but as he says, crypto on devices changes only very
> slowly.
>

We take a long time to get comfortable with it. NSA nagged us about Suite-B
for how many decades before we started using ECC?

At this point, I think we need to focus on making X25519/448 and
Ed25519/448 the basis for the next gen of security products. It took about
five years from AES being announced as a winner for it to become the new
normal.

A brilliant intern we had last year re-invented this pairing scheme, and I
> spent a week trying to work out how to do it without bilinear pairing.  It
> can also be done on RSA-like groups of unknown order (the OPRF server is
> allowed to know the order, but probably should forget it), but the security
> of the scheme is less obvious.  Both of these schemes also enable the
> quorum members to do extra work to strengthen password guesses, similar to
> Makwa.
>

A correct formal proof is useful but it isn't a substitute for a compelling
explanation of why the scheme is secure. I can provide that for threshold
decryption. And I think I can get there for the threshold signature schemes
I am looking at.


What is unclear to me is whether these schemes are generally useful because:
>
> 1) It is important for the server to know whether the password guess was
> correct, which is a key signal in rate-limiting.
> 2) Secret shares can only migrate to new HSMs/cloud providers when the
> user re-enters their password.
>
> More traditional threshold password-protected secret sharing schemes
> address these issues, at the cost of higher complexity and more
> communication rounds.  Which way should the world go?
>

Lets make it easy to use public key authentication across devices and
forget about passwords altogether.