Protection From Quantum Attack

[MrFlay]

Here’s my idea to protect POW cryptocurrencies from a quantum attack. I’m posting it here in case I have come up with something novel.
TL;DR Protect crypto transactions from quantum attack by using a “key-pair chain” and timelocks to allow fraudulent transactions to be undone.

Suppose Alice creates a random seed, then uses it to create a public/private key pair. Then she takes this public key and uses it as the seed for a new key pair, and then creates another key pair from the latest public key and so on. She ends up with a list of key pairs, and she uses the last pair to create an address in a crypto-currency.

When Alice spends from her address, someone with a quantum computer cracks her exposed public key, and manages to get a fraudulent transaction published to the blockchain before the real one. This is not a problem as Alice’s address is set up with a time lock, giving a time period where generating key pairs can be used to override any transactions. So Alice just needs to create a new transaction and sign it with her penultimate key pair (with a suitably high fee) to get control of her crypto-coins back.

This technique gives Alice protection against a quantum attack. However the attacker could just try again. To get round this, the keys in the key pair chain are not the same. The key at the end is standard encryption strength, the one before is stronger, and the one before that is even stronger. The original key pair can be an implementation of a quantum ‘safe’  signature (e.g. Lamport signatures). So the attacker knows that if they mange to get their fraudulent transaction published, it will just be replaced with a transaction that is much harder to forge, so it is probably not worth trying.

Note that there is an issue with the transaction fee for the forged transaction. If the miner keeps the fee it can be used as a mechanism to siphon off Alice’s funds. If the fee goes to Alice, then people could use the transaction overrides as a cheap way to put data on the blockchain. So there probably needs to be some sort of compromise or fee restriction.

In summary, this technique allows a cryptocurrency to have the security of large signatures, but without increasing the size of data on the blockchain (unless there is an actual attack). The penalty for this security is an increase in the time receivers have to wait for transactions to confirm.

[pooya87]

"if" an attacker could find private key of Alice from her public key then it means the system is flawed and should not even be used. solutions like this are like workarounds that are just putting band aid on a bullet wound! the real solution is to change the asymmetric cryptography scheme to something that could not be broken by the attacker in first place.

[HeRetiK]

The original key pair can be an implementation of a quantum ‘safe’  signature (e.g. Lamport signatures). So the attacker knows that if they mange to get their fraudulent transaction published, it will just be replaced with a transaction that is much harder to forge, so it is probably not worth trying.

If at this point the currency supports quantum-resistant signatures, why use them only for the failsafe transaction? Wouldn't it make more sense to just use quantum-resistant signatures from the start and skip the whole key-chaining / timelock part?

[MrFlay]

Thanks for the replies.

If at this point the currency supports quantum-resistant signatures, why use them only for the failsafe transaction?

QR resistant signatures are typically huge compared to standard signatures, so it doesn't make sense to use them when quantum computers don't exists. It's good to have a backup plan just in case though.

solutions like this are like workarounds that are just putting band aid on a bullet wound!

The idea in the opening post is to make a cryptocurrency that is resilient to a catastrophic signature failure. It is supposed to be a band aid to keep things going until a 'real solution' can be implemented.

[pereira4]

Peter Wiulle doesn't paint a pretty picture on the state of things currently:

Any unconfirmed transaction in flight exposes public keys, so if a QC exists, at least moving coins around safely becomes impossible. Further, a massive fraction of the currency supply can be taken. Lastly, you likely have exposed your own pubkey already.

Given all those hypothetical attack models that pubkey hashing doesn't help with at all, I think it's fair to say that Bitcoin as it exists today is not quantum secure, period.

If you have an idea that can really hide pubkeys then do a BIP and translate it into code, but the point PWiuelle makes is that already exposed pubkeys are all funds prone to be QC'd which means it's an epic cluster since everyone would need to move their funds. Ideally there should be a hardfork and satoshis coins moved to be protected somehow... I hope someone smart is really planning ahead and thinking of the game theory involved to coordinate this stuff, because not only you need the code but you need planning and consensus.

[figmentofmyass]

Ideally there should be a hardfork and satoshis coins moved to be protected somehow... I hope someone smart is really planning ahead and thinking of the game theory involved to coordinate this stuff, because not only you need the code but you need planning and consensus.

adding a quantum resistant signature scheme could be done with a soft fork, and so could locking/destroying vulnerable coins (including the satoshi coins). however, judging by the public lashing theymos got for this idea i'm not confident consensus will ever be reached on the second point.

a lot of people seem to prefer the idea of letting lost coins recirculate but i don't think they necessarily realize the effect this will have on price.

[BrewMaster]

adding a quantum resistant signature scheme could be done with a soft fork,

quantum resistant signatures should be implemented when we fear quantum computers are close to breaking ECDSA. that means this switch should be first enforced and second be irreversible. in other words nobody should be able to still make ECDSA signatures anymore after that change since we would be consider it weak at that point....
... this means it should be a hard fork not a soft fork.

[figmentofmyass]

adding a quantum resistant signature scheme could be done with a soft fork,

quantum resistant signatures should be implemented when we fear quantum computers are close to breaking ECDSA. that means this switch should be first enforced and second be irreversible. in other words nobody should be able to still make ECDSA signatures anymore after that change since we would be consider it weak at that point....
... this means it should be a hard fork not a soft fork.

that doesn't require breaking backward compatibility with legacy nodes. the fork just needs to add new rules to lock or destroy ECDSA-secured coins. of course, that would make legacy nodes useless---but not incompatible---so it would still be a soft fork. (not that it matters)

this was theymos' idea:

One softfork set to trigger in 5 years would convert OP_CHECKSIG to OP_RETURN, destroying all coins protected by OP_CHECKSIG.

[AverageGlabella]

"if" an attacker could find private key of Alice from her public key then it means the system is flawed and should not even be used. solutions like this are like workarounds that are just putting band aid on a bullet wound! the real solution is to change the asymmetric cryptography scheme to something that could not be broken by the attacker in first place.

Which is only theoretically possible when there is a quantum computer with 1000s of qbits but we are a very long way from that becoming a reality and I would like to think we would no longer be using the same algorithm by then. Quantum resistant algorithms at the moment are having a big investment and we are not even close to achieving quantum computers that are capable of anything worrying with the current technology. Just think when we get closer to quantum computers how much funding would go into developing an algorithm which would be quantum resistant.

quantum resistant signatures should be implemented when we fear quantum computers are close to breaking ECDSA. that means this switch should be first enforced and second be irreversible. in other words nobody should be able to still make ECDSA signatures anymore after that change since we would be consider it weak at that point....
... this means it should be a hard fork not a soft fork.

I am not sure what you mean by close but I would like to think we are looking to change around 2025 at current technology advancement rate which is still many years in front of us. Quantum resistant algorithms already exist but I'm unsure whether any of them suit Bitcoins infrastructure however I know that quantum computers aren't really a threat and are just scare mongering by the media.

[BrewMaster]

-snipped-
that doesn't require breaking backward compatibility with legacy nodes. the fork just needs to add new rules to lock or destroy ECDSA-secured coins. of course, that would make legacy nodes useless---but not incompatible---so it would still be a soft fork. (not that it matters)

it is not about backward compatibility, it is about old nodes not being forward compatible and addition of new rules.
we first have to add a new OP code for the new signatures. and we have to use the new signature scheme that everyone accepts (reaching consensus) and since both of these are new rules that we would be adding they require hard fork.

[figmentofmyass]

-snipped-
that doesn't require breaking backward compatibility with legacy nodes. the fork just needs to add new rules to lock or destroy ECDSA-secured coins. of course, that would make legacy nodes useless---but not incompatible---so it would still be a soft fork. (not that it matters)

it is not about backward compatibility, it is about old nodes not being forward compatible and addition of new rules.

forward and backward compatibility are two sides of the same coin.

old nodes would be forward compatible. they could still process eg OP_LAMPORT transactions (though they would not be able to fully understand them), enforce their network consensus rules, forward blocks to peers. they just wouldn't be able to secure bitcoins (outputs sent to them would be destroyed) nor could they broadcast transactions that would be accepted by the network.

we first have to add a new OP code for the new signatures. and we have to use the new signature scheme that everyone accepts (reaching consensus) and since both of these are new rules that we would be adding they require hard fork.

https://en.bitcoin.it/wiki/Softfork

New transaction types can often be added as softforks, requiring only that the participants (sender and receiver) and miners understand the new transaction type. This is done by having the new transaction appear to older clients as a "pay-to-anybody" transaction (of a special form), and getting the miners to agree to reject blocks including these transaction unless the transaction validates under the new rules. This is how pay to script hash and Segregated Witness were added to Bitcoin.

[dave111223]

Check out the latest google invention.... A processor capable of doing in 3 minutes what summit (the most powerful computer in the world made in IBM) would have done in 10,000 years... It could change a lot of things in the world of crypto, such computing power.... And at the same time it will make it possible to achieve very beautiful things!

[AverageGlabella]

Check out the latest google invention.... A processor capable of doing in 3 minutes what summit (the most powerful computer in the world made in IBM) would have done in 10,000 years... It could change a lot of things in the world of crypto, such computing power.... And at the same time it will make it possible to achieve very beautiful things!

No their quantum computer is different to the quantum computers which would be a threat to Bitcoin. However if it were to be used against Bitcoin and we went on with the assumption that it could contribute to the networks processing power. Do you know how much money that quantum computer takes to build? Then you have running costs and maintenance and when considering these which could be used for more beneficial projects I doubt the government would be happy with Google processing some Bitcoin transactions on the network. Then its the problem of there only being one of these quantum computers in existence and looking at the price to both build and maintain the machine there would probably not be very many people who would be able to afford it which means it would have little effect on the difficulty of Bitcoin mining and all of this is assuming its appropriate to mine Bitcoins which it is not.

[dave111223]

Check out the latest google invention.... A processor capable of doing in 3 minutes what summit (the most powerful computer in the world made in IBM) would have done in 10,000 years... It could change a lot of things in the world of crypto, such computing power.... And at the same time it will make it possible to achieve very beautiful things!

No their quantum computer is different to the quantum computers which would be a threat to Bitcoin. However if it were to be used against Bitcoin and we went on with the assumption that it could contribute to the networks processing power. Do you know how much money that quantum computer takes to build? Then you have running costs and maintenance and when considering these which could be used for more beneficial projects I doubt the government would be happy with Google processing some Bitcoin transactions on the network. Then its the problem of there only being one of these quantum computers in existence and looking at the price to both build and maintain the machine there would probably not be very many people who would be able to afford it which means it would have little effect on the difficulty of Bitcoin mining and all of this is assuming its appropriate to mine Bitcoins which it is not.

I totally agree with you. These will clearly not be the priorities. Afterwards, we can also think that with Moore's theory, which will be less and less true, the individual will have easier and easier access to machines capable of breaking these codes. I'm not talking about the next 5 years, but 20 years from now, it doesn't really seem stupid... Just look at the progress that has been made over the past 20 years. Not sure that quantum computers remain the property of big groups for very long...

[AverageGlabella]

I totally agree with you. These will clearly not be the priorities. Afterwards, we can also think that with Moore's theory, which will be less and less true, the individual will have easier and easier access to machines capable of breaking these codes. I'm not talking about the next 5 years, but 20 years from now, it doesn't really seem stupid... Just look at the progress that has been made over the past 20 years. Not sure that quantum computers remain the property of big groups for very long...

Its been predicted that we will be seeing exponential growth within the quantum computing industry but that does not mean its the same quantum computer which is efficient at factoring and therefore a threat to the algorithm Bitcoin uses. These quantum computers will probably be utilized by SpaceX and other companies which need to process a lot of math related work quickly. Aside from that the military will probably have access to quantum computers which would be the ones which are very good at factoring as they try and break the encryptions of communications. I don't think Bitcoin is high on the list for anyone who is capable of owning a quantum computer in the next 10 years.