Quote from: gmaxwell on April 24, 2013, 10:02:38 PM

Quote from: Shevek on April 24, 2013, 08:53:37 PM

I don't agree with this.
256-bit ECDSA is 128 bit strong in the unlike scenario of anybody searching collisions between two hazard keys (birthday paradox).
But more realistic scenario is looking for collisions with specific keys hoarding large amounts of BTCs. In this case 256-bit strength remains.

ECDSA is not a hash function. At attacker with the pubic key isn't confined to use the dumbest possible brute-force attack.

Pollard's lambda algorithm takes sqrt() operations so roughly 2^128 security.

Most people aren't aware that elliptic curve algorithms, in general, require about twice as many bits of keyspace as their security level. The wikipedia article on key size provides a half-decent introduction to the topic.

Security is measured in effective key length, which really boils down to "how many operations are needed to break this?". It is the key size of an ideal system that can only be brute forced, but provides the same level of security.

Most symmetric systems have effective key sizes equal to (or nearly equal to) their actual key size. For example, AES uses 128 bit keys, and provides 128 bits of effective key size.*

Public key systems, however, suck in that regard. Algorithms based on prime factors require keys at least 16 times as large for the same security level. Think 2048 bits of keyspace for 128 bits of security. ECDSA looks a lot better by comparison, only needing twice as many key bits.

* Two interesting things to note. First, 2¹²⁸ is WAY beyond our ability to break, and will remain that way for a long time. Second, AES was designed with quantum attacks in mind. You should be using the 256 bit extension of AES if you think that someone might actually figure out how to build a machine that can run Grover's algorithm and a reversible single circuit version of the AES transform. This is because Grover's reduces the effective key size by half, which is the same thing as taking the square root of the key space.