public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Alan Reiner <etotheipi@gmail.com>
To: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Preparing for the Cryptopocalypse
Date: Mon, 05 Aug 2013 01:37:53 -0400	[thread overview]
Message-ID: <51FF3A31.5050209@gmail.com> (raw)
In-Reply-To: <CAPaL=UXqxS_p-cLt_Jvh2dzq-dr5nt1RQu1ojEnBxmSN+EuD7A@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 2260 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 3237 bytes --]

  reply	other threads:[~2013-08-05  5:38 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-08-04 17:13 [Bitcoin-development] Preparing for the Cryptopocalypse Melvin Carvalho
2013-08-04 18:06 ` Alan Reiner
2013-08-05  3:30   ` Peter Vessenes
2013-08-05  5:29     ` John Dillon
2013-08-05  5:37       ` Alan Reiner [this message]
2013-08-05  6:41     ` Gregory Maxwell
2013-08-05 15:37       ` Peter Vessenes
2013-08-06 11:09       ` Mike Hearn

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=51FF3A31.5050209@gmail.com \
    --to=etotheipi@gmail.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox