Preparing for the Cryptopocalypse
8 messages, 4 to 6 Aug 2013. Started by Melvin Carvalho.
Alan Reiner (2), Peter Vessenes (2), Melvin Carvalho, John Dillon, Greg Maxwell, Mike Hearn
A great presentation on advances in crypto
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:
Quoted text (17 lines)
> 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
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
On Mon, Aug 5, 2013 at 3:30 AM, Peter Vessenes <peter@coinlab•com> wrote:
Quoted text (8 lines)
> 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.
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:
Quoted text (2 lines)
> 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
Quoted text (6 lines)
> > 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
Quoted text (3 lines)
> > crypto. > > Is NTRU still an option? My understanding is that NTRUsign, the
algorithm to
Quoted text (2 lines)
> produce signatures as opposed to encryption, was broken last year: >
http://www.di.ens.fr/~ducas/NTRUSign_Cryptanalysis/DucasNguyen_Learning.pdf
Quoted text (3 lines)
> > 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
Quoted text (1 line)
> that we can, and should, never create more than one signature for any
given key
Quoted text (4 lines)
> 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
Quoted text (2 lines)
> 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
Quoted text (2 lines)
> and signature size to ECC. >
On Sun, Aug 4, 2013 at 8:30 PM, Peter Vessenes <peter@coinlab•com> wrote:
Quoted text (3 lines)
> 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.
Quoted text (1 line)
> 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.
Interesting! I will refrain from digging into QC right now, per Alan's suggestion. :)
Quoted text (4 lines)
> 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 :)