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