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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <etotheipi@gmail.com>) id 1V6DUh-00086K-60
for bitcoin-development@lists.sourceforge.net;
Mon, 05 Aug 2013 05:38:11 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.128.43 as permitted sender)
client-ip=209.85.128.43; envelope-from=etotheipi@gmail.com;
helo=mail-qe0-f43.google.com;
Received: from mail-qe0-f43.google.com ([209.85.128.43])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1V6DUg-0000Tt-59
for bitcoin-development@lists.sourceforge.net;
Mon, 05 Aug 2013 05:38:11 +0000
Received: by mail-qe0-f43.google.com with SMTP id k5so1493733qej.16
for <bitcoin-development@lists.sourceforge.net>;
Sun, 04 Aug 2013 22:38:04 -0700 (PDT)
X-Received: by 10.49.59.69 with SMTP id x5mr24161633qeq.18.1375681084623;
Sun, 04 Aug 2013 22:38:04 -0700 (PDT)
Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net.
[76.111.96.126])
by mx.google.com with ESMTPSA id a4sm1300277qai.3.2013.08.04.22.38.03
for <bitcoin-development@lists.sourceforge.net>
(version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Sun, 04 Aug 2013 22:38:04 -0700 (PDT)
Message-ID: <51FF3A31.5050209@gmail.com>
Date: Mon, 05 Aug 2013 01:37:53 -0400
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:17.0) Gecko/20130620 Thunderbird/17.0.7
MIME-Version: 1.0
To: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
References: <CAKaEYh+G-cEif43UG1NhZ-zwJwos1-tsW-ZTMtWrHm+t3GCtzQ@mail.gmail.com>
<51FE9834.7090007@gmail.com>
<CAMGNxUuhpOF+fOpHxQ7ZrV2=tGTEhfF3LiA=g87HZW=0QkNzYA@mail.gmail.com>
<CAPaL=UXqxS_p-cLt_Jvh2dzq-dr5nt1RQu1ojEnBxmSN+EuD7A@mail.gmail.com>
In-Reply-To: <CAPaL=UXqxS_p-cLt_Jvh2dzq-dr5nt1RQu1ojEnBxmSN+EuD7A@mail.gmail.com>
X-Enigmail-Version: 1.5.2
Content-Type: multipart/alternative;
boundary="------------020606000006010401000905"
X-Spam-Score: -0.6 (/)
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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(etotheipi[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
-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: 1V6DUg-0000Tt-59
Subject: Re: [Bitcoin-development] Preparing for the Cryptopocalypse
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: Mon, 05 Aug 2013 05:38:11 -0000
This is a multi-part message in MIME format.
--------------020606000006010401000905
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Whoops, I didn't mean to run us down the Quantum Computing debate path.
I was simply using my experience with QCs as a basis for questioning the
conclusion that ECDLP is so much more robust than RSA/factoring
problems. It's possible we would simply be jumping from one burning
bridge to another burning bridge by rushing to convert everything to ECC
in the event of a factoring breakthrough.
From the perspective of quantum computers, it seems those two problems
are essentially the same. As I said, I remember that one of the
problems is solved by using the solution/circuit for the other. But I
don't know if this relationship holds outside the realm of QCs. The
guy who did this presentation said he's not a mathematician and/or
cryptographer, yet he still strongly asserts the superiority of ECDLP.
I'm not convinced.
On 08/05/2013 01:29 AM, John Dillon wrote:
> On Mon, Aug 5, 2013 at 3:30 AM, Peter Vessenes <peter@coinlab.com> wrote:
> > I studied with Jeffrey Hoffstein at Brown, one of the creators of
NTRU. He
> > told me recently NTRU, which is lattice based, is one of the few (only?)
> > NIST-recommended QC-resistant algorithms.
>
> > We talked over layering on NTRU to Bitcoin last year when I was out that
> > way; I think such a thing could be done relatively easily from a crypto
> > standpoint. Of course, there are many, many more questions beyond
just the
> > crypto.
>
> Is NTRU still an option? My understanding is that NTRUsign, the
algorithm to
> produce signatures as opposed to encryption, was broken last year:
>
http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf
>
> Having said that my understanding is also that the break requires a few
> thousand signatures, so perhaps for Bitcoin it would still be
acceptable given
> that we can, and should, never create more than one signature for any
given key
> anyway. You would be betting that improving the attack from a few thousand
> signatures to one is not possible however.
>
> In any case, worst comes to worst there are always lamport signatures.
If they
> are broken hash functions are broken and Bitcoin is fundementally broken
> anyway, though it would be nice to have alternatives that are similar
is pubkey
> and signature size to ECC.
>
--------------020606000006010401000905
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Whoops, I didn't mean to run us down the Quantum Computing debate
path. I was simply using my experience with QCs as a basis for
questioning the conclusion that ECDLP is so much more robust than
RSA/factoring problems. It's possible we would simply be jumping
from one burning bridge to another burning bridge by rushing to
convert everything to ECC in the event of a factoring breakthrough.
<br>
<br>
From the perspective of quantum computers, it seems those two
problems are essentially the same. As I said, I remember that one
of the problems is solved by using the solution/circuit for the
other. But I don't know if this relationship holds outside the
realm of QCs. The guy who did this presentation said he's not a
mathematician and/or cryptographer, yet he still strongly asserts
the superiority of ECDLP. I'm not convinced.<br>
<br>
<br>
On 08/05/2013 01:29 AM, John Dillon wrote:<br>
<span style="white-space: pre;">> On Mon, Aug 5, 2013 at 3:30 AM,
Peter Vessenes <a class="moz-txt-link-rfc2396E" href="mailto:peter@coinlab.com"><peter@coinlab.com></a> wrote:<br>
> > I studied with Jeffrey Hoffstein at Brown, one of the
creators of NTRU. He<br>
> > told me recently NTRU, which is lattice based, is one of
the few (only?)<br>
> > NIST-recommended QC-resistant algorithms.<br>
><br>
> > We talked over layering on NTRU to Bitcoin last year
when I was out that<br>
> > way; I think such a thing could be done relatively
easily from a crypto<br>
> > standpoint. Of course, there are many, many more
questions beyond just the<br>
> > crypto.<br>
><br>
> Is NTRU still an option? My understanding is that NTRUsign,
the algorithm to<br>
> produce signatures as opposed to encryption, was broken last
year:<br>
>
<a class="moz-txt-link-freetext" href="http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf">http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf</a><br>
><br>
> Having said that my understanding is also that the break
requires a few<br>
> thousand signatures, so perhaps for Bitcoin it would still be
acceptable given<br>
> that we can, and should, never create more than one signature
for any given key<br>
> anyway. You would be betting that improving the attack from a
few thousand<br>
> signatures to one is not possible however.<br>
><br>
> In any case, worst comes to worst there are always lamport
signatures. If they<br>
> are broken hash functions are broken and Bitcoin is
fundementally broken<br>
> anyway, though it would be nice to have alternatives that are
similar is pubkey<br>
> and signature size to ECC.<br>
></span><br>
<br>
</body>
</html>
--------------020606000006010401000905--
|
