[Bitcoin-development] Preparing for the Cryptopocalypse

[Bitcoin-development] Preparing for the Cryptopocalypse

[Melvin Carvalho]

[-- 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 --]

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Alan Reiner]

[-- 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 --]

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Peter Vessenes]

[-- 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 --]

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[John Dillon]

-----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-----

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Alan Reiner]

[-- 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 --]

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Peter Vessenes]

[-- 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 --]

Re: [Bitcoin-development] Preparing for the Cryptopocalypse

[Mike Hearn]

[-- 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 --]