1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
Return-Path: <aj@erisian.com.au>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E680374
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 28 Nov 2018 10:49:57 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 567CD19B
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 28 Nov 2018 10:49:57 +0000 (UTC)
Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au)
by azure.erisian.com.au with esmtpsa (Exim 4.89 #1 (Debian))
id 1gRxPk-0006R5-F7; Wed, 28 Nov 2018 20:49:54 +1000
Received: by sapphire.erisian.com.au (sSMTP sendmail emulation);
Wed, 28 Nov 2018 20:49:46 +1000
Date: Wed, 28 Nov 2018 20:49:46 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Devrandom <c1.bitcoin@niftybox.net>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20181128104946.bftgbclno6gzzji4@erisian.com.au>
References: <CALhDas2W5QEPmw8JEgak0zf7y3N0UFTiMVk-djR8x9_WYZiyfQ@mail.gmail.com>
<CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAB0O3SVjhXVV4PKYPh+2O4xZomcyT-T2Mis1A8riTtrnUUigig@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
X-Spam-Score: -1.9
X-Spam-Score-int: -18
X-Spam-Bar: -
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,UNPARSEABLE_RELAY
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 28 Nov 2018 14:24:43 +0000
Subject: Re: [bitcoin-dev] Multi party Schnorr Rust implementation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Nov 2018 10:49:58 -0000
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
|
