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; 
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>
Content-Type: multipart/alternative;
	boundary="------------020606000006010401000905"
Subject: Re: [Bitcoin-development] Preparing for the Cryptopocalypse
Precedence: list

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