public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
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
> 


      reply	other threads:[~2018-11-28 16:43 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-11-27 17:52 [bitcoin-dev] Multi party Schnorr Rust implementation Omer Shlomovits
2018-11-28  6:33 ` Devrandom
2018-11-28  8:13   ` Omer Shlomovits
2018-11-28 10:49   ` Anthony Towns
2018-11-28 16:43     ` Jonas Nick [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=dd9988c0-2635-88d7-21e4-ebd42e202990@gmail.com \
    --to=jonasdnick@gmail.com \
    --cc=aj@erisian.com.au \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox