From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6DLw-0000zl-QY for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 05:29:08 +0000 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; Received: from mail-ea0-f174.google.com ([209.85.215.174]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6DLu-0004zq-V6 for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 05:29:08 +0000 Received: by mail-ea0-f174.google.com with SMTP id z15so1371694ead.33 for ; Sun, 04 Aug 2013 22:29:00 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.14.1.70 with SMTP id 46mr15432697eec.82.1375680540606; Sun, 04 Aug 2013 22:29:00 -0700 (PDT) Received: by 10.223.41.4 with HTTP; Sun, 4 Aug 2013 22:29:00 -0700 (PDT) In-Reply-To: References: <51FE9834.7090007@gmail.com> Date: Mon, 5 Aug 2013 05:29:00 +0000 Message-ID: From: John Dillon To: Peter Vessenes Content-Type: text/plain; charset=ISO-8859-1 X-Spam-Score: -1.4 (-) 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 (john.dillon892[at]googlemail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit (john.dillon892[at]googlemail.com) -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: 1V6DLu-0004zq-V6 Cc: Bitcoin Dev 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 05 Aug 2013 05:29:08 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On Mon, Aug 5, 2013 at 3:30 AM, Peter Vessenes 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-----