From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 (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 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 References: <51FE9834.7090007@gmail.com> In-Reply-To: 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 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--