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.&nbsp; 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.&nbsp; 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.&nbsp; As I said, I remember that one
    of the problems is solved by using the solution/circuit for the
    other.&nbsp; But I don't know if this relationship holds outside the
    realm of QCs.&nbsp;&nbsp; The guy who did this presentation said he's not a
    mathematician and/or cryptographer, yet he still strongly asserts
    the superiority of ECDLP.&nbsp; I'm not convinced.<br>
    <br>
    <br>
    On 08/05/2013 01:29 AM, John Dillon wrote:<br>
    <span style="white-space: pre;">&gt; On Mon, Aug 5, 2013 at 3:30 AM,
      Peter Vessenes <a class="moz-txt-link-rfc2396E" href="mailto:peter@coinlab.com">&lt;peter@coinlab.com&gt;</a> wrote:<br>
      &gt; &gt; I studied with Jeffrey Hoffstein at Brown, one of the
      creators of NTRU. He<br>
      &gt; &gt; told me recently NTRU, which is lattice based, is one of
      the few (only?)<br>
      &gt; &gt; NIST-recommended QC-resistant algorithms.<br>
      &gt;<br>
      &gt; &gt; We talked over layering on NTRU to Bitcoin last year
      when I was out that<br>
      &gt; &gt; way; I think such a thing could be done relatively
      easily from a crypto<br>
      &gt; &gt; standpoint. Of course, there are many, many more
      questions beyond just the<br>
      &gt; &gt; crypto.<br>
      &gt;<br>
      &gt; Is NTRU still an option? My understanding is that NTRUsign,
      the algorithm to<br>
      &gt; produce signatures as opposed to encryption, was broken last
      year:<br>
      &gt;
<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>
      &gt;<br>
      &gt; Having said that my understanding is also that the break
      requires a few<br>
      &gt; thousand signatures, so perhaps for Bitcoin it would still be
      acceptable given<br>
      &gt; that we can, and should, never create more than one signature
      for any given key<br>
      &gt; anyway. You would be betting that improving the attack from a
      few thousand<br>
      &gt; signatures to one is not possible however.<br>
      &gt;<br>
      &gt; In any case, worst comes to worst there are always lamport
      signatures. If they<br>
      &gt; are broken hash functions are broken and Bitcoin is
      fundementally broken<br>
      &gt; anyway, though it would be nice to have alternatives that are
      similar is pubkey<br>
      &gt; and signature size to ECC.<br>
      &gt;</span><br>
    <br>
  </body>
</html>

--------------020606000006010401000905--