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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <jeremy@taplink.co>) id 1W9tAI-0001oJ-5M
for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 09:16:34 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of taplink.co
designates 50.117.27.232 as permitted sender)
client-ip=50.117.27.232; envelope-from=jeremy@taplink.co;
helo=mail.taplink.co;
Received: from mail.taplink.co ([50.117.27.232])
by sog-mx-4.v43.ch3.sourceforge.com with smtp (Exim 4.76)
id 1W9tAH-0006W9-7x for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 09:16:34 +0000
Received: from laptop-air ([192.168.168.135]) by mail.taplink.co ;
Sun, 2 Feb 2014 01:16:43 -0800
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: "Adam Back" <adam@cypherspace.org>, "Peter Todd" <pete@petertodd.org>
References: <CAAS2fgQmsxjkQFSiCdeMoVMaqq5720KpUpdkKZOE+XytHsWw0w@mail.gmail.com>
<20140124090218.GA15398@savin>
<CANEZrP0MnXr4xjaMPg7v7vTiDQr-y7esvEBE=xk=Y0BUGXak9A@mail.gmail.com>
<20140124154235.GA3741@netbook.cypherspace.org>
<20140124161330.GA31233@petertodd.org>
<20140125161901.GA17457@netbook.cypherspace.org>
<20140202023651.GA18666@savin>
Date: Sun, 02 Feb 2014 01:16:20 -0800
MIME-Version: 1.0
Content-Transfer-Encoding: Quoted-Printable
From: "Jeremy Spilman" <jeremy@taplink.co>
Organization: TapLink
Message-ID: <op.xanddiq6yldrnw@laptop-air>
In-Reply-To: <20140202023651.GA18666@savin>
User-Agent: Opera Mail/1.0 (Win32)
oclient: 192.168.168.135#jeremy@taplink.co#465
X-Spam-Score: -2.1 (--)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
-0.5 RP_MATCHES_RCVD Envelope sender domain matches handover relay
domain
-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
author's domain
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1W9tAH-0006W9-7x
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] (space) efficient reusable addr via weil
pairing IBE (Re: Bait for reusable addresses)
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sun, 02 Feb 2014 09:16:34 -0000
>
> Consequently you can now securely and very network/space efficiently
> securely delegate searching a block by computing the private key for t=
he
> IBE pub key that any sender would use for that block, and sending it a=
s
> a query to a random (or node-capture defended random selected node).
> The node can decrypt the encrypted bloom baits with it, but remains
> powerless to correlate with bloom baits to other payments received by
> the same user in bother blocks.
>
I'm not sure I've fully wrapped my head around it.
d/Q - Identity key
E - Generate an epoch-pubkey: E =3D Q * H1(epoch)
r/P - Ephemeral privkey/pubkey, or discoverable from inputs
S =3D r * K - Shared secret (ECDE)
Payer derives an encryption key H(S), and encrypts M, which is a 1 byte =
=
bloom bait.
For each epoch, payee generates e =3D d * H1(epoch) and provides the key=
to =
a full node for monitoring. So you are providing a per-block or per-epoc=
h =
private key, along with the block ID or epoch ID that the key correspond=
s =
to.
The full node then uses this privkey to decrypt the same byte in all the=
=
transactions in that epoch/block which match the expected layout/templat=
e, =
e.g. given a certain length OP_RETURN, pull the specific byte and decryp=
t.
This decrypted byte is then in turn used as bloom bait which may or may =
=
not cause the transaction to be sent back to the SPV client.
Am I right in saying the full node has no idea if decryption is =
'succeeding' it just feeds the resultant bait into the bloom filter and =
=
the transaction may match or not? So we do get some level of repudiation=
=
by the SPV client -- the server doesn't know exactly which transactions =
=
belong to the SPV client.
The bloom bait specified in the reusable address is still making the =
bandwidth/privacy trade-off, it just doesn't become public information, =
=
because it's protected by another factor?
What encryption scheme is being used here?
-=3D-=3D-=3D-=3D=3D
Another approach (inspired by IBE) which narrows the discoverability of =
=
transactions to the nodes that your SPV client is actually communicating=
=
with, for the specific blocks/epochs that you specify, would be to use =
PEKS.
PEKS(Q, W) for a public key Q and a keyword W produces a searchable =
encryption of the word W.
The payee holding 'd' (privkey for Q) can create a trapdoor which allows=
a =
server to search for transactions with W, where the searching party only=
=
knows if a match is found or not.
Payer:
d/Q - Longstanding / identity privkey/pubkey
r/P - Ephemeral privkey/pubkey, or discoverable from inputs
W - Searchable Keyword
H1 - Hash function, {0, 1} =E2=88=97 =E2=86=92 G1
H2 - Hash function, G2 =E2=86=92 {0, 1}p
Secret, as usual per ECDH:
S =3D r * Q
For payer to create the searchable encryption of W for Q, called 'Sw':
Sw =3D H2(e(H1(W), S))
OP_RETURN P, Sw
For payee to search for a given 'W', payee calculates a trapdoor 'Tw':
Tw =3D d * H1(W)
For a searcher, given a Trapdoor (Tw), check each Transaction (P, Sw):
H2(e(Tw, P)) =3D=3D? Sw
If the values match, the keyword matches
Without getting into the concepts of e(g,g) and binomial pairing, I thin=
k =
of it this way:
Sw =3D H2(r * Q * H1(W)), but recall: rQ =3D=3D dP, so...
=3D H2(d * P * H1(W)), which can be written
=3D H2(d * H1(W) * P)
Severs finds all transactions with 'P' on relevant parts of the =
blockchain, multiplies by the provided trapdoor 'Tw', applies 'H2', and =
=
checks for a matching 'Sw' in the transaction;
Tw =3D d * H1(W)
Sw =3D H2(Tw * P)
H2(d * H1(W) * P)
PEKS is vulnerable to an offline keyword guessing attack, where you can =
=
discover the value of the keyword being searched, if the keyword is low =
=
entropy. The server/attacker can figure out the value of W, but they can=
't =
generate their own trapdoors to search for other keywords.
But in this case, the 'keyword' can simply be the block ID / epoch ID =
itself, not a secret value at all. In other words, the server can only =
search for your transactions within the blocks/epochs that you specify.
Using blockID/epochID as W, this would allow a server to find all =
transactions belonging to the payer for that blockID / epochID. The SPV =
=
client would simply provide the trapdoor for each block/epoch to be =
searched.
There are extensions to PEKS which provide for 'fuzzy' matching but they=
=
are 'fuzzy' within the scope of Q, not across different Q, so that doesn=
't =
help provide any repudiation. So I see this as only slightly improving =
Peter's original proposal of providing 'Q' to the searcher, but if you =
want repudiation, not as good as Adam's solution.
Perfunctory disclaimer... Hopefully this is close to correct, but please=
=
don't anyone actually try to implement this!
Thanks,
Jeremy
|
