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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pete@petertodd.org>) id 1W9veV-0007T2-6t
for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 11:55:55 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org
designates 62.13.149.56 as permitted sender)
client-ip=62.13.149.56; envelope-from=pete@petertodd.org;
helo=outmail149056.authsmtp.com;
Received: from outmail149056.authsmtp.com ([62.13.149.56])
by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1W9veT-0000Lw-46 for bitcoin-development@lists.sourceforge.net;
Sun, 02 Feb 2014 11:55:55 +0000
Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237])
by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s12Btgk9059552;
Sun, 2 Feb 2014 11:55:42 GMT
Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109])
(authenticated bits=128)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s12BtcHs066917
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO);
Sun, 2 Feb 2014 11:55:40 GMT
Date: Sun, 2 Feb 2014 06:55:31 -0500
From: Peter Todd <pete@petertodd.org>
To: Adam Back <adam@cypherspace.org>
Message-ID: <20140202115531.GA22375@savin>
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>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="vkogqOf2sHV7VnPd"
Content-Disposition: inline
In-Reply-To: <20140202023651.GA18666@savin>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: f06bc6c3-8c00-11e3-94fa-002590a135d3
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdgAUHlAWAgsB AmIbWlVeVVh7XWI7 bAxPbAVDY01GQQRq
WVdMSlVNFUsrAB5z Qk1mERl0cQxHfzBx bUJnXT4NXEIoJkAu
QVNcRm0GeGZhPWMC WUQOJh5UcAFPdx8U a1N6AHBDAzANdhES
HhM4ODE3eDlSNilR RRkIIFQOdA5LBSY1 TB1DVTghE0wORig1
M1Q8J0MHFUwVPw07 PVc7EUwZOlcNBwxa fQlVCS5DJl8ODwsB
IEsaZ0NMWBdUQDsU DBoyagVFHydbUC5V TEJJRwsCEDhIS2gg
X-Authentic-SMTP: 61633532353630.1024:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 76.10.178.109/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Score: -1.5 (-)
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
X-Headers-End: 1W9veT-0000Lw-46
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 11:55:55 -0000
--vkogqOf2sHV7VnPd
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
> On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote:
> [quote author=3Dadam3us link=3Dtopic=3D431756.msg4729682#msg4729682
> date=3D1390660452]
> So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman,
> Mike Hearn, Bytecoin and others about reusable addresses.
>=20
> There is a summary of the situation here
> http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg=
03792.html
> and I had posed th question of whether it was possible to do better at
> all with Peter Todd:
You're explanation is a bit long-winded, so I'll start with a simplified
ECC-based version first and later explain how identity-based encryption
applies to the problem; I have a feeling not many non-crypt-experts
spent the time to figure out what you're talking about; do check if what
I've written below is correct:
So Alice wants to pay Bob, who is bandwidth constrained and frequently
offline. Meanwhile Ivan has a full node, but can't really be trusted.
Meanwhile Eve is busy trying to piece together everyones' financial
details.
Bob publicly publishes three pubkeys, Filter, Recover, and Spend, along
with a short n-bit prefix p. When Alice needs to pay Bob she creates a
ephemeral keypair and uses ECDH *two* shared secrets, n_f and n_r, from
Bob's Filter and Recover pubkeys respectively. She makes a transaction
that pays Bob by deriving pubkey Spend_{n_f} from the Spend and n_r
nonce. She also uses the Filter nonce and the prefix to derive a
encrypted prefix p'=3Dn_f^p and puts that prefix and the cleartext
ephemeral pubkey in the transaction as data.
When Bob wants to find that transaction he gives the prefix and Filter
secret key to Ivan, who then scans the blockchain. For every transaction
he computes n_f=3DECDH(Filter_sec, Ephm_pub), extracts the encrypted
prefix p' from the transaction, and checks if p'=3Dn_f^p If so he gives
that transaction to Bob who can then use his Recover secret key to check
if the transaction was in fact for him. (note how the prefix can
actually always be simply a given length of zeros)
Because Bob's prefix is short Ivan only learns probabalistic information
about what transactions might be Bob's. Eve doesn't know the Filter
secret key, and thus learns nothing at all from the blockchain data. On
the other hand after getting the key once Ivan can forever after get
that probability information about what transactions might be Bob's.
What we'd really like is for there to be some way for Alice to derive a
time-limited Filter pubkey from some public random beacon with value
R_i, such as the Bitcoin blockchain, such that each defined time
interval uses a different key. Bob would then only give Ivan the secret
key(s) for the time interval(s) in question.
Unfortunately ECDSA doesn't have a way to do this. The closest thing
available is BIP32-style key derivation, however it has the property
that given a derived secret key and known master pubkey the master
secret key can be derived. Thus Ivan can simply try every public Filter
key/epoch tweak he knows about until he finds Q,d' st. (d+d')G=3DQ+d'G
=46rom that he can recover d, reducing the security to where we started.
(or put another way, Ivan can store every (d+d') secret key he is asked
to search with, and test it against every public key he learns about
later)
Identity-based cryptograhy however can do that. Bob publishes a (single)
master public key, and anyone can derive public keys based on that
master key and the random beacon value R_i. Bob can then derive the
corresponding secret key, but unlike with ECDSA, that secret key *can't*
be used to derive the master private key. Having said that, it can of
course be linked to that key, so every query that Bob makes gives Ivan
some knowledge about what transactions might be in Bob's wallet.
Problem is, who the hell has a production-ready Weil pairing library
kicking around? (is this read? http://crypto.stanford.edu/pbc/) Also,
Weil pairing is not yet trustworthy:
< gmaxwell> (IMO thats how we should be using pairing in
cryptosystems: for lower value applications, and solving things that
can't be solved any other way)
--=20
'peter'[:-1]@petertodd.org
000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0
--vkogqOf2sHV7VnPd
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)
iQGrBAEBCACVBQJS7jIzXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDA3NTgyOWY2MTY5Yzc5ZDdkNWFhYTIwYmZhOGRhNmU5ZWRi
MjM5M2M0Zjg2NjJiYTAvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkftiCgf+I1LPJz3csEsWK5MnMHIbg5fv
T1+oD6gPCPwub8J3p6nLQ+x8bDis/2NU/I89irzKv1Z95bhPp7fbU/i/4DBaUQq3
4zHzBieMmE7VZKxGPg8hSApgZPYduhAoXPED8maK0Jf+0DH9aejGIC5WAcOWNN6B
xgRBssUCpcDicHJL1ZdHz58Qa2TEsGtnyFdwXE9LQAByxZVzojuKtZuwIBOLOc40
pRX4CMXHpgNsphpA+xC9bno6pfKxBtVx+Bx5LOTPP+pLKoXZ6A/exCXpbfiUYGy+
nvnvrzRYgcdxvfQ216EvmFav8KI7X4ZI5Wt0pNlGIz9X8fXOvqizJ2P89Kiddg==
=478Q
-----END PGP SIGNATURE-----
--vkogqOf2sHV7VnPd--
|
