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
next prev 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 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$(echo .)com.au \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=c1.bitcoin@niftybox$(echo .)net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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