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--