public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Anthony Towns <aj@erisian.com.au>
To: Devrandom <c1.bitcoin@niftybox.net>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Multi party Schnorr Rust implementation
Date: Wed, 28 Nov 2018 20:49:46 +1000	[thread overview]
Message-ID: <20181128104946.bftgbclno6gzzji4@erisian.com.au> (raw)
In-Reply-To: <CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>

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



  parent reply	other threads:[~2018-11-28 10:49 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 [this message]
2018-11-28 16:43     ` Jonas Nick

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=20181128104946.bftgbclno6gzzji4@erisian.com.au \
    --to=aj@erisian.com.au \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=c1.bitcoin@niftybox.net \
    /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