Re: [Cfrg] Call for adoption: Threshold Signatures

[Jeff Burdges <[e-mail]>]

> On 8 Oct 2020, at 18:33, Nick Sullivan <nick=[e-mail]> wrote:
> Please give your views on the following questions:
> a) should this topic be adopted by the CFRG as a work item, and if so

There are numerous crap multi-signature implementations so yes maybe a good time.  

> b) should one or both of these documents should be considered as a starting point for this work

I’ve not looked closely at either draft, so I’ll need to do so, but.. 

I do think a deliniarized witness approach works best, like what we deployed in January or what FROST switched to in July.  I’ll therefore only comment on two issues I see with the FROST paper.


1. Flexible rounds are a foot gun

These “flexible rounds” seem dangerous because they make witness freshness an implementation detail external to the cryptographic code.   I’m sure ZCash could deploy flexible rounds security for their use case because they work quite closely with their wallet developers.  It’s unlikely however that most organizations could deploy flexible rounds securely.  I’d therefore suggest that anything about flexible rounds be excluded from standards. 

Also, there are actually three choices here, (1) MuSig-DN requires agreements by the first round, (2) deliniarized witnesses permit agreement on message and signer by the second round, and (3) flexible rounds abuses deliniarized witnesses by allowing "pre-witnesses” to be saved to disk to combine many first rounds into one setup round. 

If you do want flexible rounds then you need quite patient and careful developers who do not mind inspecting the details of storage code, all application error handling, etc.  It’ll be very messy and expensive work.  I guess a TEE helps.

I’ve not even checked if the draft discusses flexible rounds.  If not, then no changes anyways.  


2. FROST has no security proof

FORST has a proof for an interactive protocol, which they follow with a heuristic resembling Fiat-Shamir but "cross session".  It’s exactly this sort of argument against which Drijvers, et al. warned!  There is a time and place for heuristic arguments, but not right after Drijvers, et al. broke so many related arguments in https://eprint.iacr.org/2018/417.pdf 

Also FROST also confuses this situation with their “one-shot VRF” terminology.  It’s true deliniarization produces PRF-like properties, but the resulting PRF is nothing like a VRF because the parameter acts differently.  If this miss-leading VRF terminology appears then it should be removed. 

All that said, we have in https://eprint.iacr.org/2020/1245/20201009:113646 what should be a correct security proof in AGM+ROM+KOSK+OMDL [0] for a related scheme, to which I gave the uninspired name 2-DWMS.  I’ll caution anyone who reads the proof that, although we never say forking or rewinding, our probabilistic method argument and H_0 tweak do use in full force that the Schnorr challenge oracle H is a random function (ROM).

2-DWMS-Sign:
Round 1.  Each candidate signer i proposes two pre-witnesses T_{i,j} = t_{i,j} G for j=1,2 (the 2-).
Round 2.  After agreement upon the message msg and signers [1] then everyone computes the aggregate public key X, a transcript of this data and the pre-witnesses
     trns = (msg, X, T_{1,1},T_{1,2},T_{2,1},…,T_{n,1},T_{n,2})
  and delinearization factors  \alpha_{i,j} = H_1(trns, i, j)  and a shared witness  S = \sum_{i,j} \alpha_{i,j} T_{i,j}.  Also compute and send a partial signature
     s_i = H(msg, X, S) sk_i + \alpha_{i,1} t_{i,1} + \alpha_{i,2} t_{i,2}
where sk_i is the ith signers secret key tweaked by Lagrange coefficients or whatever your scheme requires.

We broke 1-DWMS that delinearizes just one pre-witness.  FROST uses “1.5”-DWMS where signers supply two pre-witnesses (same first round), but alpha_{i,1} = 1 instead being a random oracle (one less scalar multiplication).  We broke the “1.5”-Entwined ROS property used internally by our security proof, so our security arguments depends upon alpha_{i,1} being a random oracle.  You therefore cannot deduce security for “1.5”-DWMS aka FROST using our current results. 

At first I thought “1.5”-DWMS might be breakable with 1024 parallel sessions, but..  We'll likely prove security for “1.5”-DWMS after some recent improvements elsewhere, although this requires convincing myself of one fishy step. 

Assuming we prove “1.5”-DWMS aka FROST to be secure, then there remains a sticky situation:  I suspect the “1.5”-entwined ROS break means alpha_{i,1} being a random oracle matters for some use cases like implicit certificates, and maybe even some “adaptor" signatures, meaning FROST becomes insecure under some Schnorr-like schemes with different verification rules. 

As a standard, I’d tentatively suggest we "take the high road” by recommending 2-DWMS over “1.5”-DWMS, so that alpha_{i,1} becomes a random oracle in this draft, and each signer does one extra scalar multiplication per signer.  Again I’ve nothing concrete here so I might change my mind!  We should anyways caution users about using altered verification like implicit certificates, etc. without adapting security proofs to their altered verification. 

> c) are you willing to help work on this item and/or review it

Yes in principle.  I suppose a draft normally cites external resources for formal arguments, yes?  If folk wish I could supply brief comments on correctly proving security for deliniarized witness schemes.  I’ll figure out if our improved proof applies to “1.5”-DWMS regardless. 

Best,
Jeff

[0]  AGM can mean several things, and the name sucks, but we need an AGM that lives closer to GGM than some extractor variants.  

[1]  As hinted above, agreeing upon the signer set and message by the second round is much weaker than “flexible rounds” like FROST proposes.  FROST proposes that the pre-witness secrets t_{i,j} be saved to disk, so then restoring from backups compromises users' secret keys (either if done twice or if done once and under a k-sum attack).