* [Bitcoin-development] Preparing for the Cryptopocalypse @ 2013-08-04 17:13 Melvin Carvalho 2013-08-04 18:06 ` Alan Reiner 0 siblings, 1 reply; 8+ messages in thread From: Melvin Carvalho @ 2013-08-04 17:13 UTC (permalink / raw) To: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 88 bytes --] A great presentation on advances in crypto http://www.slideshare.net/astamos/bh-slides [-- Attachment #2: Type: text/html, Size: 177 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 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 0 siblings, 1 reply; 8+ messages in thread From: Alan Reiner @ 2013-08-04 18:06 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1531 bytes --] 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 [-- Attachment #2: Type: text/html, Size: 2700 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-04 18:06 ` Alan Reiner @ 2013-08-05 3:30 ` Peter Vessenes 2013-08-05 5:29 ` John Dillon 2013-08-05 6:41 ` Gregory Maxwell 0 siblings, 2 replies; 8+ messages in thread From: Peter Vessenes @ 2013-08-05 3:30 UTC (permalink / raw) To: Alan Reiner; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 426 bytes --] 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 [-- Attachment #2: Type: text/html, Size: 615 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-05 3:30 ` Peter Vessenes @ 2013-08-05 5:29 ` John Dillon 2013-08-05 5:37 ` Alan Reiner 2013-08-05 6:41 ` Gregory Maxwell 1 sibling, 1 reply; 8+ messages in thread From: John Dillon @ 2013-08-05 5:29 UTC (permalink / raw) To: Peter Vessenes; +Cc: Bitcoin Dev -----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----- ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-05 5:29 ` John Dillon @ 2013-08-05 5:37 ` Alan Reiner 0 siblings, 0 replies; 8+ messages in thread From: Alan Reiner @ 2013-08-05 5:37 UTC (permalink / raw) To: Bitcoin Dev [-- 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 --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-05 3:30 ` Peter Vessenes 2013-08-05 5:29 ` John Dillon @ 2013-08-05 6:41 ` Gregory Maxwell 2013-08-05 15:37 ` Peter Vessenes 2013-08-06 11:09 ` Mike Hearn 1 sibling, 2 replies; 8+ messages in thread From: Gregory Maxwell @ 2013-08-05 6:41 UTC (permalink / raw) To: Peter Vessenes; +Cc: Bitcoin Dev On Sun, Aug 4, 2013 at 8:30 PM, 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. 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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-05 6:41 ` Gregory Maxwell @ 2013-08-05 15:37 ` Peter Vessenes 2013-08-06 11:09 ` Mike Hearn 1 sibling, 0 replies; 8+ messages in thread From: Peter Vessenes @ 2013-08-05 15:37 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 86 bytes --] Interesting! I will refrain from digging into QC right now, per Alan's suggestion. :) [-- Attachment #2: Type: text/html, Size: 213 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Bitcoin-development] Preparing for the Cryptopocalypse 2013-08-05 6:41 ` Gregory Maxwell 2013-08-05 15:37 ` Peter Vessenes @ 2013-08-06 11:09 ` Mike Hearn 1 sibling, 0 replies; 8+ messages in thread From: Mike Hearn @ 2013-08-06 11:09 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Dev [-- Attachment #1: Type: text/plain, Size: 624 bytes --] > 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 :) [-- Attachment #2: Type: text/html, Size: 873 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2013-08-06 11:09 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 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 2013-08-05 6:41 ` Gregory Maxwell 2013-08-05 15:37 ` Peter Vessenes 2013-08-06 11:09 ` Mike Hearn
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox