Re: [Bitcoin-development] Preparing for the Cryptopocalypse
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. -- 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
Re: [Bitcoin-development] Preparing for the Cryptopocalypse
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. > -- 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
Re: [Bitcoin-development] Preparing for the Cryptopocalypse
-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- -- 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
Re: [Bitcoin-development] Preparing for the Cryptopocalypse
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 -- 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
Re: [Bitcoin-development] Preparing for the Cryptopocalypse
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 -- 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
[Bitcoin-development] Preparing for the Cryptopocalypse
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