Re: [bitcoin-dev] Multi party Schnorr Rust implementation

From: Jonas Nick <jonasdnick@gmail•com>
To: Anthony Towns <aj@erisian•com.au>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Multi party Schnorr Rust implementation
Date: Wed, 28 Nov 2018 16:43:12 +0000	[thread overview]
Message-ID: <dd9988c0-2635-88d7-21e4-ebd42e202990@gmail.com> (raw)
In-Reply-To: <20181128104946.bftgbclno6gzzji4@erisian.com.au>

> For deterministic nonces, you generate r=H(p,m) based on the message
> being signed and your private key, so can only start this process when
> you start signing, and the sharing rounds mean interactivity.

It's not your point but it should be noted that this is not secure unless all
other signers give you zero knowledge proof that they've generated their nonce
in the same way. Otherwise, if your asked to sign the same message you'll use
the same nonce for two different challenges. In your example you'd compute
s=r+H(R',P',m)*p and s'=r+H(R'',P',m)*p from which an observer can compute the
secret key p.

On 11/28/18 10:49 AM, Anthony Towns via bitcoin-dev wrote:
> On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote:
>> Are there any candidates for non-interactive threshold signatures?  Interactive
>> signatures are not very suitable for air-gapped use cases.
> 
> I think you can work around this to some extent by "batching" signing
> requests.
> 
> (Background:
> 
> For interactive multisignatures (threshold or not), the protocol is:
> 
>    produce secret nonce r, calculate public nonce R=r*G
>    everyone shares H(R)
>    everyone shares R, checks received values match received hashes
>    everyone calculates s=r+H(R',P',m)*p, shares s
> 
> For deterministic nonces, you generate r=H(p,m) based on the message
> being signed and your private key, so can only start this process when
> you start signing, and the sharing rounds mean interactivity.
> 
> )
> 
> But you don't strictly need deterministic nonces, you just have to never
> use the same nonce with a different message. If you arrange to do that
> by keeping some state instead, you can calculate nonces in advance:
> 
> phase 1:
>     produce secret nonces r1..r1024, calculate R1..R1024
>     share H(R1)..H(R1024)
> 
> phase 2:
>     store other parties hashes, eg as H1..H1024
>     share R1..R1024
> 
> phase 3:
>     check received nonces match, ie H(R1)=H1, etc
> 
> phase 4:
>     request to sign msg m, with nonce n
>     if nonce n has already been used, abort
>     mark nonce n as having being used
>     lookup other signer's nonces n and sum them to get R'
>     calculate s = rn + H(R',P',m)*p
>     share s
> 
> That way you could do phases 1-3 once, and then do 1024 signatures during
> the month on whatever your current timetable is.
> 
> You could also combine these phases, so when you get a signing request you:
> 
>    * receive msg to sign m, n=4; everyone else's R4, H(R5)
> 
>    * check  H(R4) = previously received "H(R4)"
>    * calculate R4' by summing up your and everyone's R4s
>    * bump state to n=5
>    * do the signature...
> 
>    * send sig=(s,R4), R5, H(R6)
> 
> which would let you have an untrusted app that does the coordination and
> shares the nonces and nonce-hashes, and getting all the needed air-gapped
> communication in a single round. (This is effectively doing phase 3 and
> 4 for the current signature, phase 2 for the next signature, and phase
> 1 for the signature after that all in one round of communication)
> 
> That seems almost as good as true non-interactivity to me, if your signing
> hardware is capable of securely storing (and updating) a few kB of state
> (which is probably not quite as easy as it sounds).
> 
> Cheers,
> aj
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 