Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of googlemail.com
	designates 209.85.215.174 as permitted sender)
	client-ip=209.85.215.174;
	envelope-from=john.dillon892@googlemail.com;
	helo=mail-ea0-f174.google.com; 
MIME-Version: 1.0
In-Reply-To: <CAMGNxUuhpOF+fOpHxQ7ZrV2=tGTEhfF3LiA=g87HZW=0QkNzYA@mail.gmail.com>
References: <CAKaEYh+G-cEif43UG1NhZ-zwJwos1-tsW-ZTMtWrHm+t3GCtzQ@mail.gmail.com>
	<51FE9834.7090007@gmail.com>
	<CAMGNxUuhpOF+fOpHxQ7ZrV2=tGTEhfF3LiA=g87HZW=0QkNzYA@mail.gmail.com>
Date: Mon, 5 Aug 2013 05:29:00 +0000
Message-ID: <CAPaL=UXqxS_p-cLt_Jvh2dzq-dr5nt1RQu1ojEnBxmSN+EuD7A@mail.gmail.com>
From: John Dillon <john.dillon892@googlemail.com>
To: Peter Vessenes <peter@coinlab.com>
Content-Type: text/plain; charset=ISO-8859-1
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] Preparing for the Cryptopocalypse
Precedence: list

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

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.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJR/zffAAoJEEWCsU4mNhiPypEH/1AoIR5eWewNbGO9/AZNykwf
Rs3P1iOJYt4oR0oTOHwlsXKX1qU9QAvWQUjDH60XyChCqb+E+xMz4LZgV6H71A03
XcEUZ6r4TRtEdH5kWwtoaxz2oxIIfwfRHIisUCCX2VvXzlBDjcuZvPQXSB0KE8Sx
z8pBZuRKbLeU19COK4BZs1/83/DTsYrV0Ln3LYT3UT5oiJBzA9pmX0cVxQePx2rc
hoNaxR4wR/oCUCvv73xhbzvB91RrAEgrJsd1ve4qR14LxWeOnTHqWQ2/E5JechZz
is/ryBW1Yit5GmsQlfNtKhS3zAaiCjha5e03CaSSlT0LjuVabe2A43LfEb0n4Mw=
=c5f5
-----END PGP SIGNATURE-----