Post
Topic
Board Development & Technical Discussion
Re: Why is ECDSA needed at all?
by
funkenstein
on 08/11/2016, 21:34:02 UTC
If my idea is worthless, then it strengthens the point why ECDSA is needed, and people will apreciate ECDSA more.

Your idea is not worthless and is already used in one of the altcoins. It's actually a nice solution for IoT-friendly cryptography for which ECDSA is too "heavy". The only requirements are to wait long enough between beginning and committing a transaction and to not reuse addresses (private keys).

Or you could use Winternitz (Lamport signatures) with Merkel trees for a more robust solution that doesn't reveal the private key and has roughly 1/20th the resource overhead (not including hardware acceleration of SHA256) of the most efficient (curve25519) elliptic curve cryptography (not factoring in batch mode). But the major downside is the size of signatures increase exponentially with increasing bit security level, which is also the problem with RSA. The theoretical gain is future quantum computing resistance, but research is proceeding on elliptic curve (isogenies) variants which are quantum computing secure.

There are many reasons why this makes sense... the generation time to create new signatures using Lamport + Merkle is negligent as that is amortized by the client which can afford the extra time for improved security. The signing is up to 10x faster but at the cost of higher bandwidth requirements like Anonymint says. However the upside is favorable as it creates a quantum resistant system that doesn't need a bunch of one way hashing to "work-around" the problem of ECDSA.

Another benefit you get from this is that Bitcoin requires one-time use addresses because those public keys once seen on the network can be used to steal balances by NSA once ECDSA is compromised so all spends with change are sent to new addresses with pubkeys not published yet. Because of this there is lack of usability on services that build upon the transaction creation process. For example in Syscoin I wanted to have an identity system (aliases) that would keep balances like accounts. To avoid mangled code to detect which addresses belong to an alias as change I simply removed the need to create new pubkeys for change and send change back to the alias pubkey which are public on the network. The multisig feature of bitcoin lacks clarity and usability because of the design of bitcoin because pubkeys cannot be published and thus redeemscripts need to be saved and sent across potentially unsafe communication lines...(read my multisig post here: http://syscoin.org/multisignature-identity-system-syscoin-2-1-technical-update/) with aliases I also save a redeem script for multisig alias identities so that any spending can be done without the need to transmit this information to each other (increases usability exponentially). The reasoning behind these changes were that if ECDSA were to be compromised Bitcoin would have a situation where they would probably fork it in as quickly as possible and choose the best implementation... leaving the need for one-time use addresses null and void which would mean my implementation which is one of simplicity actually is the optimal solution. Since I am not a cryptographer I'm not going to bother trying to change the implmentation although it shouldn't be too hard to figure out, just for lack of time to do other work but it makes total sense for long run that either Bitcoin through their new soft-fork voting mechanism or a potential coin supplanting Bitcoin would use something like this to overcome quantum computing.


Since you bring it up, and folks have been considering, lets look at some of the troubles. 

1)  Keys much larger.  As in 10x or more.  Blockchain bloat will be an issue if the thing becomes popular. 
2)  Lamport signatures are really use-once, because after using it once - the key is basically revealed.  So, what if you want to publish an address for donations?  Is there a way to do this?  Perhaps you could set up a way to sign a group of transactions all at once, consolidating them.  Making sure to change the address that you have published for donations first, of course.  It seems an unsolved problem still. 

Those are the big problems.  A couple of other points:

1) I'm not concerned with quantum computers, Lamport sigs is still an improved security even without that threat.  This is because they are provably as hard to crack as it is to generate a collision in the hash function being used.  ECDSA is not provably as hard as anything, always something that concerns some folks. 

2) Quantum computers allegedly could still provide a route to quicker collision finding in hash functions anyway.  Perhaps not as much of a difference as for Shor' s algo or for ECDSA, but still worth pointing out.