Why 256 bit keys are large enough

Re:Why 256 bit keys are large enough by iwwr on Monday December 17, 2012 @11:35AM (#4932978)

Using elliptic-curve cryptosystems you may be able to reduce PK key sizes to near symmetric crypto lengths (within a factor of 2-4).

http://www.nsa.gov/business/programs/elliptic_curve.shtml

But remember that before we build our Dyson sphere, we may get quantum computers, which makes our bruteforcing polynomial rather than exponential. Cryptsystems based on discrete log, EC discrete log or prime factorization (pretty much all existing crypto-infrastructure) are vulnerable.

More on this http://en.wikipedia.org/wiki/Post-quantum_cryptography

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by jackpirate on Monday December 17, 2012 @01:32PM (#4933561)

which makes our bruteforcing polynomial rather than exponential

I think that's wrong. Grover's algorithm let's us speed up any algorithm, but not exponentially. You just take the sqrt of the run time.

https://en.wikipedia.org/wiki/Grovers_algorithm

Shor's algorithm lets us factor numbers in polynomial time. This would break RSA, but not every algorithm in general. I think, but I'm not 100% sure, that elliptic curve methods have no known polynomial time quantum algorithms, for example.

https://en.wikipedia.org/wiki/Shors_algorithm

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by pjscott on Monday December 17, 2012 @04:45PM (#4934571)

A version of Shor's algorithm applies to elliptic curve crypto:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.38...

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by Aardwolf on Monday December 17, 2012 @12:35PM (#4933286)

The person quoting Schneier said: "... will be infeasible until computers are built from something other than matter and occupy something other than space"

So are quantum computers not from matter and not in space? :)

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by kluge on Monday December 17, 2012 @01:00PM (#4933420)

They (and Schneier) were talking about symmetric encryption, which does not rely on the things quantum computing is going to affect.

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by Lagged2Death on Monday December 17, 2012 @01:11PM (#4933470)

But remember that before we build our Dyson sphere, we may get quantum computers...

Does quantum computing somehow get around the fundamental energy requirements?

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by gsteinb88 on Monday December 17, 2012 @02:37PM (#4933921)

Yes. The fundamental energy requirements come out of the destruction of information from a bit flip (or from a 2 bit -> 1 bit gate). Qubits don't undergo that transition - until the final measurement, they're in a superposition of both states, so the transformations are really just rotations and reflections of a state, which in principle are not subject to the same requirements. Also, the real power of quantum computing comes from the ability to 'test multiple answers' at once, at least in principle. In reality, we've only figured out how to do this for a small subclass of problems.

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by iwwr on Monday December 17, 2012 @01:20PM (#4933513)

For symmetric cryptosystems search difficulty is halved (a 256 bit AES key under a quantum bruteforce becomes as 'hard' as a 128 bit key under conventional bruteforce).

For asymmetric systems, search is reduced to polynomial (if using the discrete log, EC discrete log or prime factorization).

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by jacquesm on Monday December 17, 2012 @07:19PM (#4935355)

Doesn't halving the search difficulty mean dropping 1 bit from the key length? So 256->255 rather than 256->128?

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by scott_weber on Monday December 17, 2012 @11:07PM (#4936015)

The numbers are correct, but it was written in an odd way. Grovers algorithm gives a speedup of sqrt(n), so the exponent gets halved.

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by betterunix on Monday December 17, 2012 @06:30PM (#4935140)

For some public key systems, the search becomes polynomial. Luckily, we know of ones for which that is not the case (as far as we know), and so if a practical quantum computer could be built we would just deploy new cryptosystems (pricey, but not end-of-the-world pricey).

[ Parent | on HN ]