From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V61sQ-00059t-I5 for bitcoin-development@lists.sourceforge.net; Sun, 04 Aug 2013 17:13:54 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.215.46 as permitted sender) client-ip=209.85.215.46; envelope-from=melvincarvalho@gmail.com; helo=mail-la0-f46.google.com; Received: from mail-la0-f46.google.com ([209.85.215.46]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V61sP-0004hy-Kg for bitcoin-development@lists.sourceforge.net; Sun, 04 Aug 2013 17:13:54 +0000 Received: by mail-la0-f46.google.com with SMTP id eh20so1517324lab.19 for ; Sun, 04 Aug 2013 10:13:46 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.112.200.37 with SMTP id jp5mr7196530lbc.61.1375636426887; Sun, 04 Aug 2013 10:13:46 -0700 (PDT) Received: by 10.112.159.233 with HTTP; Sun, 4 Aug 2013 10:13:46 -0700 (PDT) Date: Sun, 4 Aug 2013 19:13:46 +0200 Message-ID: From: Melvin Carvalho To: Bitcoin Dev Content-Type: multipart/alternative; boundary=001a11c36b6a90979d04e322504a X-Spam-Score: -0.6 (/) 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 (melvincarvalho[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -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: 1V61sP-0004hy-Kg Subject: [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: Sun, 04 Aug 2013 17:13:54 -0000 --001a11c36b6a90979d04e322504a Content-Type: text/plain; charset=ISO-8859-1 A great presentation on advances in crypto http://www.slideshare.net/astamos/bh-slides --001a11c36b6a90979d04e322504a Content-Type: text/html; charset=ISO-8859-1
A great presentation on advances in crypto

http://www.slideshare.net/astamos/bh-slides
--001a11c36b6a90979d04e322504a-- 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-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V62hq-0000wD-Gz for bitcoin-development@lists.sourceforge.net; Sun, 04 Aug 2013 18:07:02 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.216.53 as permitted sender) client-ip=209.85.216.53; envelope-from=etotheipi@gmail.com; helo=mail-qa0-f53.google.com; Received: from mail-qa0-f53.google.com ([209.85.216.53]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V62ho-0008JE-Pe for bitcoin-development@lists.sourceforge.net; Sun, 04 Aug 2013 18:07:02 +0000 Received: by mail-qa0-f53.google.com with SMTP id hu14so576924qab.12 for ; Sun, 04 Aug 2013 11:06:55 -0700 (PDT) X-Received: by 10.49.74.102 with SMTP id s6mr22228924qev.24.1375639615314; Sun, 04 Aug 2013 11:06:55 -0700 (PDT) Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net. [76.111.96.126]) by mx.google.com with ESMTPSA id om8sm2030675qeb.4.2013.08.04.11.06.53 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 04 Aug 2013 11:06:54 -0700 (PDT) Message-ID: <51FE9834.7090007@gmail.com> Date: Sun, 04 Aug 2013 14:06:44 -0400 From: Alan Reiner User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130620 Thunderbird/17.0.7 MIME-Version: 1.0 To: bitcoin-development@lists.sourceforge.net References: In-Reply-To: X-Enigmail-Version: 1.5.2 Content-Type: multipart/alternative; boundary="------------050809000905080302010604" X-Spam-Score: -0.6 (/) 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 (etotheipi[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -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: 1V62ho-0008JE-Pe 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: Sun, 04 Aug 2013 18:07:02 -0000 This is a multi-part message in MIME format. --------------050809000905080302010604 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit That is a great presentation, thanks for sharing that! Though I question the validity of the claim that ECC is so much more secure than RSA (with appropriate keysizes). My experience from studying quantum computing is that Factoring and DLP are intimately related, such that a break of one is likely to break the other. In fact, I seem to remember that QCs use an efficient DLP-solving circuit to "shortcut" the factoring problem. But it's been a long time since I looked at it, so I don't remember for sure. Also, it's not clear whether that relationship exists outside the scope of QCs. It's still a good presentation, but they're pushing ECC pretty hard as the answer to the cryptopocalypse, and I'm not convinced that's a real answer. -Alan On 08/04/2013 01:13 PM, Melvin Carvalho wrote: > A great presentation on advances in crypto > > http://www.slideshare.net/astamos/bh-slides > > > ------------------------------------------------------------------------------ > Get your SQL database under version control now! > Version control is standard for application code, but databases havent > caught up. So what steps can you take to put your SQL databases under > version control? Why should you start doing it? Read more to find out. > http://pubads.g.doubleclick.net/gampad/clk?id=49501711&iu=/4140/ostg.clktrk > > > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development --------------050809000905080302010604 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit That is a great presentation, thanks for sharing that!

Though I question the validity of the claim that ECC is so much more secure than RSA (with appropriate keysizes).  My experience from studying quantum computing is that Factoring and DLP are intimately related, such that a break of one is likely to break the other.  In fact, I seem to remember that QCs use an efficient DLP-solving circuit to "shortcut" the factoring problem.  But it's been a long time since I looked at it, so I don't remember for sure.   Also, it's not clear whether that relationship exists outside the scope of QCs.

It's still a good presentation, but they're pushing ECC pretty hard as the answer to the cryptopocalypse, and I'm not convinced that's a real answer.

-Alan



On 08/04/2013 01:13 PM, Melvin Carvalho wrote:
A great presentation on advances in crypto

http://www.slideshare.net/astamos/bh-slides


------------------------------------------------------------------------------
Get your SQL database under version control now!
Version control is standard for application code, but databases havent 
caught up. So what steps can you take to put your SQL databases under 
version control? Why should you start doing it? Read more to find out.
http://pubads.g.doubleclick.net/gampad/clk?id=49501711&iu=/4140/ostg.clktrk


_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

--------------050809000905080302010604-- From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6BVT-0005jG-Dn for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 03:30:51 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of coinlab.com designates 209.85.216.177 as permitted sender) client-ip=209.85.216.177; envelope-from=peter@coinlab.com; helo=mail-qc0-f177.google.com; Received: from mail-qc0-f177.google.com ([209.85.216.177]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6BVS-0006wT-Mw for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 03:30:51 +0000 Received: by mail-qc0-f177.google.com with SMTP id e11so1407527qcx.22 for ; Sun, 04 Aug 2013 20:30:45 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:x-gm-message-state; bh=4Py8Hal8/IVeCteGeigoKiEJSHmhyjzzxNw/JY2+4Fc=; b=aYKRQisxu+kEyMJjI1/lMlif1WCt/AjUTiXiExfuiq7AyAATjFeCOe/0rX+eBPyavj 1g+gnRz3QeNSRNcjkN8z/rltOoozuDD4M/FQNCyv5YpnjBR36VLkblO0LNGb+GuRHowv xAPwXn5UpEHBnnQFyYH5yi5rprsYehOazOUKL8CKopcWtB6sN90Z8TdU3VtPWazHTim2 D5AwzoUY5BYTR2/bOiogtmldxEWy+DvduSR7cQeAVB5J5oBXp89kRmRxH2SdYdUJ6AbW h3rWiQKrHnNxONTIy1jjUF0esYJNjXEAzlPjJsdgI2+JdWrzVNLI6HBIj3ft3oWWJGZO gq/g== X-Received: by 10.224.11.136 with SMTP id t8mr20264058qat.65.1375673445235; Sun, 04 Aug 2013 20:30:45 -0700 (PDT) MIME-Version: 1.0 Received: by 10.49.132.69 with HTTP; Sun, 4 Aug 2013 20:30:25 -0700 (PDT) In-Reply-To: <51FE9834.7090007@gmail.com> References: <51FE9834.7090007@gmail.com> From: Peter Vessenes Date: Sun, 4 Aug 2013 20:30:25 -0700 Message-ID: To: Alan Reiner Content-Type: multipart/alternative; boundary=001a11c2c2b807e69104e32aefdf X-Gm-Message-State: ALoCoQlvyAlwahTYQ1l1jVJBlJQ5VJG2mHhxg5cj/iNhQ3c8AWcrsPgGRFDH/28FPXt802Tpv64j X-Spam-Score: -0.5 (/) 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 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message X-Headers-End: 1V6BVS-0006wT-Mw 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 03:30:51 -0000 --001a11c2c2b807e69104e32aefdf Content-Type: text/plain; charset=ISO-8859-1 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. Peter --001a11c2c2b807e69104e32aefdf Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
I studied with Jeffrey Hoffstei= n 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 alg= orithms.=A0

We ta= lked 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.=A0=

Peter
=
--001a11c2c2b807e69104e32aefdf-- 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----- From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6DUh-00086K-60 for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 05:38:11 +0000 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; Received: from mail-qe0-f43.google.com ([209.85.128.43]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6DUg-0000Tt-59 for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 05:38:11 +0000 Received: by mail-qe0-f43.google.com with SMTP id k5so1493733qej.16 for ; Sun, 04 Aug 2013 22:38:04 -0700 (PDT) X-Received: by 10.49.59.69 with SMTP id x5mr24161633qeq.18.1375681084623; Sun, 04 Aug 2013 22:38:04 -0700 (PDT) Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net. [76.111.96.126]) by mx.google.com with ESMTPSA id a4sm1300277qai.3.2013.08.04.22.38.03 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 04 Aug 2013 22:38:04 -0700 (PDT) Message-ID: <51FF3A31.5050209@gmail.com> Date: Mon, 05 Aug 2013 01:37:53 -0400 From: Alan Reiner 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 References: <51FE9834.7090007@gmail.com> In-Reply-To: X-Enigmail-Version: 1.5.2 Content-Type: multipart/alternative; boundary="------------020606000006010401000905" X-Spam-Score: -0.6 (/) 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 (etotheipi[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -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: 1V6DUg-0000Tt-59 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:38:11 -0000 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 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 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-- 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-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6EUW-00025a-Kh for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 06:42:04 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.217.170 as permitted sender) client-ip=209.85.217.170; envelope-from=gmaxwell@gmail.com; helo=mail-lb0-f170.google.com; Received: from mail-lb0-f170.google.com ([209.85.217.170]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6EUV-00004t-Rj for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 06:42:04 +0000 Received: by mail-lb0-f170.google.com with SMTP id r10so1767347lbi.29 for ; Sun, 04 Aug 2013 23:41:57 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.152.181.65 with SMTP id du1mr7877970lac.76.1375684917100; Sun, 04 Aug 2013 23:41:57 -0700 (PDT) Received: by 10.112.160.104 with HTTP; Sun, 4 Aug 2013 23:41:57 -0700 (PDT) In-Reply-To: References: <51FE9834.7090007@gmail.com> Date: Sun, 4 Aug 2013 23:41:57 -0700 Message-ID: From: Gregory Maxwell To: Peter Vessenes Content-Type: text/plain; charset=UTF-8 X-Spam-Score: -1.6 (-) 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 (gmaxwell[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -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: 1V6EUV-00004t-Rj 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 06:42:04 -0000 On Sun, Aug 4, 2013 at 8:30 PM, 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. Lamport signatures (and merkle tree variants that allow reuse) are simpler, faster, trivially implemented, and intuitively secure under both classical and quantum computation (plus unlikely some proposed QC strong techniques they're patent clear). They happen to be the only digital signature scheme that you really can successfully explain to grandma (even for values of grandma which are not cryptographers). They have poor space/bandwidth usage properties, which is one reason why Bitcoin doesn't use them today, but as far as I know the same is so for all post-QC schemes. > Though I question the validity of the claim that ECC is so much more secure than RSA (with appropriate keysizes). The problems are intimately related, but under the best understanding ECC (with suitable parameters) ends up being the maximally hard case of that problem class. I do sometimes worry about breakthroughs that give index-calculus level performance for general elliptic curves, this still wouldn't leave it any weaker than RSA but ECC is typically used with smaller keys. From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6MrM-0000k5-Qg for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 15:38:12 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of coinlab.com designates 209.85.216.175 as permitted sender) client-ip=209.85.216.175; envelope-from=peter@coinlab.com; helo=mail-qc0-f175.google.com; Received: from mail-qc0-f175.google.com ([209.85.216.175]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6MrL-0003kN-4P for bitcoin-development@lists.sourceforge.net; Mon, 05 Aug 2013 15:38:12 +0000 Received: by mail-qc0-f175.google.com with SMTP id s11so1753449qcv.34 for ; Mon, 05 Aug 2013 08:38:05 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:x-gm-message-state; bh=xRQMuJhuZHEwXRFWRbOO3SsVl/sK7geXHbuduCSY38U=; b=gdbVq+kT+AFH+rPknStbEvdit0oGUQeyAzWi9QNMJznphe8qanFmSnlSQuAexv8jHp CnBGJUdD588MrFi3aumYYSkzx7pLz4/OCKUFQ+wGpWN7ML36VwkfvLL9uWasA+K+VjFx oFxeb6fcaxyqemddhW0jb2NTF/2fnVyDK+jufS/kvzG8dLqxqGCdtAhynFAocjLqF4Hl mWiopjZOOGnlRqHQ1M9gE/lGPUOat7aXxOmC5AONonrhLZSuivtVB5fOszZAbkfxDmve PwDt9ON34jMk2vIXARxWXfwrpdN8MAWRWZIVLx3z309c28RKI6XJ7HEpsrzycrQQZZfy H4Ng== X-Received: by 10.224.11.136 with SMTP id t8mr23699352qat.65.1375717085641; Mon, 05 Aug 2013 08:38:05 -0700 (PDT) MIME-Version: 1.0 Received: by 10.49.132.69 with HTTP; Mon, 5 Aug 2013 08:37:44 -0700 (PDT) In-Reply-To: References: <51FE9834.7090007@gmail.com> From: Peter Vessenes Date: Mon, 5 Aug 2013 08:37:44 -0700 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary=001a11c2c2b833aa8904e335181a X-Gm-Message-State: ALoCoQkaeZHeNj7RzmVkdFAwF5SJqu0zEefJIwIBBBNgE8g1fWTK/AQtdxjHPPlX8jxQzXp+LE+N X-Spam-Score: -0.5 (/) 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 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message X-Headers-End: 1V6MrL-0003kN-4P 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 15:38:13 -0000 --001a11c2c2b833aa8904e335181a Content-Type: text/plain; charset=ISO-8859-1 Interesting! I will refrain from digging into QC right now, per Alan's suggestion. :) --001a11c2c2b833aa8904e335181a Content-Type: text/html; charset=ISO-8859-1
Interesting! I will refrain from digging into QC right now, per Alan's suggestion. :)


--001a11c2c2b833aa8904e335181a-- From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1V6f97-0006cE-7c for bitcoin-development@lists.sourceforge.net; Tue, 06 Aug 2013 11:09:45 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.219.50 as permitted sender) client-ip=209.85.219.50; envelope-from=mh.in.england@gmail.com; helo=mail-oa0-f50.google.com; Received: from mail-oa0-f50.google.com ([209.85.219.50]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1V6f96-00064K-FT for bitcoin-development@lists.sourceforge.net; Tue, 06 Aug 2013 11:09:45 +0000 Received: by mail-oa0-f50.google.com with SMTP id i4so427008oah.37 for ; Tue, 06 Aug 2013 04:09:39 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.43.226 with SMTP id z2mr534399oel.76.1375787379080; Tue, 06 Aug 2013 04:09:39 -0700 (PDT) Sender: mh.in.england@gmail.com Received: by 10.76.84.231 with HTTP; Tue, 6 Aug 2013 04:09:38 -0700 (PDT) In-Reply-To: References: <51FE9834.7090007@gmail.com> Date: Tue, 6 Aug 2013 13:09:38 +0200 X-Google-Sender-Auth: 2eHhejn_gMsGw4hwjJh5ptI9TTc Message-ID: From: Mike Hearn To: Gregory Maxwell Content-Type: multipart/alternative; boundary=001a11333dce0444f704e34576ac X-Spam-Score: -0.5 (/) 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 (mh.in.england[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message 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: 1V6f96-00064K-FT 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: Tue, 06 Aug 2013 11:09:45 -0000 --001a11333dce0444f704e34576ac Content-Type: text/plain; charset=UTF-8 > They have poor space/bandwidth usage properties, which is one reason > why Bitcoin doesn't use them today, but as far as I know the same is > so for all post-QC schemes. > I believe post-QC schemes based on Regev's LWE assumption are getting competitive with more traditional schemes. A paper from 2010 says they were able to get to around the same as large RSA key sizes (2048 bits), which is much worse than ECC but not entirely infeasible. Especially given that barring some breakthrough, by the time QC is a real problem we'll have gigabit wifi and 32 core devices with a terabyte of storage embedded in our hands :) --001a11333dce0444f704e34576ac Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

=
They have poor space/bandwidth usage properties, which is one reason
why Bitcoin doesn't use them today, but as far as I know the same is so for all post-QC schemes.

I believe p= ost-QC schemes based on Regev's LWE assumption are getting competitive = with more traditional schemes. A paper from 2010 says they were able to get= to around the same as large RSA key sizes (2048 bits), which is much worse= than ECC but not entirely infeasible. Especially given that barring some b= reakthrough, by the time QC is a real problem we'll have gigabit wifi a= nd 32 core devices with a terabyte of storage embedded in our hands :)
--001a11333dce0444f704e34576ac--