Re: [Cfrg] Call for adoption: Threshold Signatures

[Jeff Burdges <[e-mail]>]

I’d meant to send a follow up email, but I already moderated my position on both those points.  :)

> On 20 Oct 2020, at 16:25, Chelsea Komlo <[e-mail]> wrote:
> Optimization to a single-round signing scheme. The ability to perform single-round (or async) signing is desirable for many implementers (and publishing public ephemeral values is a common technique in other cryptographic protocols). While misuse is possible, rollback issues are also possible in a two-round scheme as checkpoints can occur between rounds.

We need “hardware” security for the two pre-witnesses between the rounds, which software artifacts should enforce.  It’s easy if the hardware is simply RAM and if libraries enforce this by not providing callers with access to pre-witnesses in an easy to serialize form.  It’s also perfectly valid for a signer that runs inside a TEE to export pre-witnesses encrypted to its TEE.  It’s realistic for hardware signers for crypto-currencies to enforce this of course.

Yet, if you merely expose pre-witnesses directly in pure software, or write the draft s if that’s okay, then developers will reuse them.  This is a certainty, and will happen repeatedly, not some abstract risk.  

> Proof of Security for FROST. We have carefully reviewed your points in this email and eprint. As you said, your proof technique cannot be extended to prove the security of FROST. However, this result does not entail that FROST is insecure.

It turned out easy to tweak our entwined ROS result to cover "1.5 pre-witnesses" once I looked into the matter.  We’ll post another version with this update soon-ish once we’ve tweaked it to capture more generality, maybe minimize the KOSK assumption.  Of course KOSK is fine for threshold.

I worried more about whether “1.5 pre-witnesses" breaks altered verification schemes, but now some look okay and some like implicit certs require way more work anyways.  I’m thus now happy with “1.5” like in FROST so we just need warnings about using altered verification.  

It needs warnings about less than 256 bit to delinearization oracles too since I’ve witnessed people suggesting 128 bits with one oracle set to 1 for public keys before.

> We also want to highlight the MuSig2 paper [1] that also independently discovered the "binding" (or "delinearization") technique that FROST uses. Their proof is in the AGM+ROM, and proves security for two nonces when the binding factor for the first nonce is 1 (exactly the pattern that we use in FROST).

I’ve not yet looked beyond the MuSig2 paper’s intro, but..  It’s super cool that they also prove the result with four pre-witnesses under only ROM!  I would never have had courage to even attempt that.  :)  I think a draft need not discuss the four witness option, but we should discuss that with the MuSig2 guys since others may have other opinions. 

> We can certainly provide more explanation of our proof and how it compares to proving security in the AGM.

I read FROST v2 as claiming the two pre-wtinesses protocol is secure under ROM alone.  We’d could ask the MuSig2 guys if they believe that’s possible, or at least read how they use the extra witnesses ourselves, like maybe possible with a larger runtime sacrifice than merely two forkings, or maybe not possible. 

At first blush, I suspect if one actually formalizes your "cross session” Fiat-Shamir then you’ll wind up arguing security for outright broken stuff.  I never actually tried though, so I really donno, maybe something useful there. 

Anyways..

I’d love some guidance from the rest of the group about to what extent provable security issues should even appear inside the draft.

Best,
Jeff