4 ms·

Given the order-of-magnitude increase in speed (https://www.theregister.co.uk/2016/04/18/d_wave_demystifies_... https://www.theregister.co.uk/2016/04/18/d_wave_

by naskwo 9y ago

Given the order-of-magnitude increase in speed (https://www.theregister.co.uk/2016/04/18/d_wave_demystifies_... https://www.theregister.co.uk/2016/04/18/d_wave_demystifies_...) combined with the assumption that the price of these chips will go down as commercialization becomes more viable, isn't it naive to even consider the viability of cryptocurrency? I mean, if the core underlying value of this "asset class" is the fact that there is a scarcity of numbers (like collector baseball cards) combined with ease and anonymity of transactions (like diamonds), then unlimited computing power will demolish the value of cryptocurrencies as much as alchemy would diminish the value of Au.

tempestn 9y ago
Order of magnitude increase =/= unlimited, right? Also, it's my understanding that there is already plenty of work done on post-quantum cryptography. I don't know if it's entirely a solved problem, but my understanding is that it's at least solvable. Perhaps someone with more domain experience can weigh in.
flignats 9y ago
There are several quantum resistant crypto currencies. I.e. IOTA
- banderman 9y ago
  Can you please explain what makes it quantum resistant?
  - flignats 9y ago
    "IOTA uses hash-based signatures (https://www.imperialviolet.org/2013/07/18/hashsig.html https://www.imperialviolet.org/2013/07/18/hashsig.html) instead of elliptic curve cryptography (ECC). Not only is hash-based signatures a lot faster than ECC, but it also greatly simplifies the overall protocol (signing and verification). What actually makes IOTA quantum-secure is the fact that we use Winternitz signatures. IOTA's ternary hash function is called Curl."
  - nine_k 9y ago
    Not all crypto becomes easy to crack with a quantum computer: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography With its use, the scarcity of numbers remain, that is, finding a clash that would allow to forge a transaction stays infeasible, and mining stays hard. BTW while mining is so important with Bitcoin and Etherium, it's not a necessary part of a cryptocurrency. Mining is an incentive to keep doing blockchain validation. Some currencies exist without it (e.g. NXT).
    - garmaine 9y ago
      All crypto becomes easier (well, except for the one time pad). But some algorithms (AES, SHA) only require doubling the number of bits to achieve the same security level, which is rather trivial to do.
    - bdamm 9y ago
      To date the only practical replacements for RSA and EC achieve key derivation but not signatures. Without signatures we're not really 'complete' since certificates are hard to do with only key derivation. Post-quantum cryptograph research is a very active area right now. If these researchers do not find a practical signature algorithm, PKI as we know it will change very significantly. Ironically, blockchains might elevate in importance as a result, since the evolving blockchain is a useful construct for quantum resistance. It has cryptographic agility built in.
- woah 9y ago
  IOTA isn't even resistant to differential cryptanalysis.
  - flignats 9y ago
    Care to add sources?
    - seanwilson 9y ago
      A flaw was found in the hash function they rolled themselves which doesn't build confidence there aren't more vulnerabilities to be found: https://medium.com/@neha/cryptographic-vulnerabilities-in-iota-9a6a9ddc4367 https://medium.com/@neha/cryptographic-vulnerabilities-in-io... https://www.forbes.com/sites/amycastor/2017/09/07/mit-and-bu-researchers-uncover-critical-security-flaw-in-2b-cryptocurrency-iota/2/#625c6bc042ff https://www.forbes.com/sites/amycastor/2017/09/07/mit-and-bu... To make things even worse than rolling their own hash function, they're claiming the flaw was intentional! This makes them hostile and untrustworthy to the open source community if this is true and further erodes confidence they know what they're doing if this is their attempt at PR spin: https://hackernoon.com/why-i-find-iota-deeply-alarming-934f1908194b https://hackernoon.com/why-i-find-iota-deeply-alarming-934f1... > Next, and in my mind most damningly, Sergey Ivancheglo, Iota’s cofounder, claims that the flaws in the Curl hash function were in fact deliberate; that they were inserted as ‘copy protection’, to prevent copycat projects, and to allow the Iota team to compromise those projects if they sprang up.
      - flignats 9y ago
        These points have all been talked over extensively and are not a concern: https://medium.com/@comefrombeyond/cfbs-comments-on-https-www-media-mit-edu-posts-iota-response-5834c7f8172d https://medium.com/@comefrombeyond/cfbs-comments-on-https-ww...
        seanwilson 9y ago
        That blog response is completely unconvincing and makes me trust them even less. They have no proof of the extraordinary claim that the flawed hash function was intended (which is bad whether this is true or false) and their network going down for three days is a huge red flag that the protocol cannot be used in a decentralised way. He talks a good game but if you have any technical background you can see he isn't addressing what's being asked and is avoiding valid criticism via hand waving and character attacks.
AlexAltea 9y ago
There are several misconceptions about what universal quantum computers could do. One of them is talking about exponential increase of computing power with each new qubit. It just doesn't work like that. This brief talk from Scott Aaronson tackles this issue quite well: https://www.youtube.com/watch?v=JvIbrDR1G_c https://www.youtube.com/watch?v=JvIbrDR1G_c While quantum computers threaten some cryptographic schemes, it will just be the end of those schemes, not the end of cryptography in general (see: post-quantum cryptography). As long as we still have problems that are hard to compute and easy to verify, we can have cryptocurrencies. Quantum computers do not give "unlimited computing power" and do not threaten the existence of cryptocurrencies in general.
- rocqua 9y ago
  As far as I know, there isn't a conclusive decent public-key algorithm that is quantum resistent. We know that Diffie Helmann, RSA and their elliptic counterparts are broken in quantum. That was essentially all we had. I know that 'lattice based cryptography' is a potential option, and believe there are more potential options. However, as far as I know it is not even clear whether these are safe against classical computers. I should note that I don't know much more about 'lattice based crypto' than the name and the hope it is quantum resistent.
jVinc 9y ago
crypto-currency is not about scarcity of numbers its about proof of work. Bitcoin started with relatively little computation power and has now scaled to where more power is spent than a small country uses in the mining operation... Its unfeasible to mine bitcoin on a cpu or gpu because ASICs are just so much more efficient. None of this scaling in hashing rate really changing the underlying concept which is that you prove you did some work in order to add blocks. If quantum computers do in fact result in a couple of thousand orders of magnitude raise in the hashing rate... well then miners will use different hardware the difficulty of the network will adjust each 10 minutes as new hardware gets added, and after the change you'll just have a large army of quantum miners instead of ASIC miners. Remember the exitsanse of quantum computers does not prove P=NP, which is to say, even with quantum computers you can still have the class of problems which are difficult to solve but easy to verify which is the essential component of proof of work.
- roywiggins 9y ago
  > If quantum computers do in fact result in a couple of thousand orders of magnitude raise in the hashing rate... well then miners will use different hardware the difficulty of the network will adjust each 10 minutes as new hardware gets added, and after the change you'll just have a large army of quantum miners instead of ASIC miners. If it's a couple of thousand orders of magnitude, the first person with a working quantum chip might entirely dominate the hashpower, long before the chip is available commercially. So you'd end up concentrating hashpower into a couple of BigCorps's hands. Like, if I went back in time to the beginning of BTC with an ASIC I'd probably completely dominate the baby blockchain and outcompete the entire network.
Obi_Juan_Kenobi 9y ago
There are numerous options for quantum-resistant algorithms. Existing cryptographic currencies can fork to whatever seems most suitable. This wouldn't be a trivial change, but it can certainly be done. https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography There is also no such thing as 'unlimited' computing power with regard to proof of work. Difficulty simply adjusts, and the cost of a network attack will always be related to the rewards of mining.
zamalek 9y ago
Merkle-Damgard hash functions (such as SHA256) are merely weakened by QC. SHA256 is considered good enough and as such, BTC mining should be able to weather QC. There is a variant of Shor's Algorithm that can solve ECDSA, so you might have problems with your BTC wallet; a fork using a new resistant asymmetric algorithm would be needed. Memory-constrained algorithms, such as scrypt, should be quantum resistant based on what I know (which isn't much). If I'm not horribly misinformed, LTC mining should therefore be resistant. Again, LTC wallets would face problems.
- rocqua 9y ago
  Does the same hold for hashes based non on Merkle-Damgard but the sponge construction?
  - zamalek 9y ago
    It looks like we don't know, excluding some very specific sponge functions, based on some quick research.[1][2] [1]: https://eprint.iacr.org/2017/771.pdf https://eprint.iacr.org/2017/771.pdf [2]: https://crypto.stackexchange.com/questions/419/what-security-do-cryptographic-sponges-offer-against-generic-quantum-attacks/46705 https://crypto.stackexchange.com/questions/419/what-security... (NB: comments)
garmaine 9y ago
No, there are quantum resistant protocols that could be switched to instead when the gap starts to close.

by naskwo 9y ago

tempestn 9y ago

Order of magnitude increase =/= unlimited, right? Also, it's my understanding that there is already plenty of work done on post-quantum cryptography. I don't know if it's entirely a solved problem, but my understanding is that it's at least solvable. Perhaps someone with more domain experience can weigh in.

flignats 9y ago

There are several quantum resistant crypto currencies. I.e. IOTA

banderman 9y ago
Can you please explain what makes it quantum resistant?
- flignats 9y ago
  "IOTA uses hash-based signatures (https://www.imperialviolet.org/2013/07/18/hashsig.html https://www.imperialviolet.org/2013/07/18/hashsig.html) instead of elliptic curve cryptography (ECC). Not only is hash-based signatures a lot faster than ECC, but it also greatly simplifies the overall protocol (signing and verification). What actually makes IOTA quantum-secure is the fact that we use Winternitz signatures. IOTA's ternary hash function is called Curl."
- nine_k 9y ago
  Not all crypto becomes easy to crack with a quantum computer: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography With its use, the scarcity of numbers remain, that is, finding a clash that would allow to forge a transaction stays infeasible, and mining stays hard. BTW while mining is so important with Bitcoin and Etherium, it's not a necessary part of a cryptocurrency. Mining is an incentive to keep doing blockchain validation. Some currencies exist without it (e.g. NXT).
  - garmaine 9y ago
    All crypto becomes easier (well, except for the one time pad). But some algorithms (AES, SHA) only require doubling the number of bits to achieve the same security level, which is rather trivial to do.
  - bdamm 9y ago
    To date the only practical replacements for RSA and EC achieve key derivation but not signatures. Without signatures we're not really 'complete' since certificates are hard to do with only key derivation. Post-quantum cryptograph research is a very active area right now. If these researchers do not find a practical signature algorithm, PKI as we know it will change very significantly. Ironically, blockchains might elevate in importance as a result, since the evolving blockchain is a useful construct for quantum resistance. It has cryptographic agility built in.
woah 9y ago
IOTA isn't even resistant to differential cryptanalysis.
- flignats 9y ago
  Care to add sources?
  - seanwilson 9y ago
    A flaw was found in the hash function they rolled themselves which doesn't build confidence there aren't more vulnerabilities to be found: https://medium.com/@neha/cryptographic-vulnerabilities-in-iota-9a6a9ddc4367 https://medium.com/@neha/cryptographic-vulnerabilities-in-io... https://www.forbes.com/sites/amycastor/2017/09/07/mit-and-bu-researchers-uncover-critical-security-flaw-in-2b-cryptocurrency-iota/2/#625c6bc042ff https://www.forbes.com/sites/amycastor/2017/09/07/mit-and-bu... To make things even worse than rolling their own hash function, they're claiming the flaw was intentional! This makes them hostile and untrustworthy to the open source community if this is true and further erodes confidence they know what they're doing if this is their attempt at PR spin: https://hackernoon.com/why-i-find-iota-deeply-alarming-934f1908194b https://hackernoon.com/why-i-find-iota-deeply-alarming-934f1... > Next, and in my mind most damningly, Sergey Ivancheglo, Iota’s cofounder, claims that the flaws in the Curl hash function were in fact deliberate; that they were inserted as ‘copy protection’, to prevent copycat projects, and to allow the Iota team to compromise those projects if they sprang up.
    - flignats 9y ago
      These points have all been talked over extensively and are not a concern: https://medium.com/@comefrombeyond/cfbs-comments-on-https-www-media-mit-edu-posts-iota-response-5834c7f8172d https://medium.com/@comefrombeyond/cfbs-comments-on-https-ww...
      - seanwilson 9y ago
        That blog response is completely unconvincing and makes me trust them even less. They have no proof of the extraordinary claim that the flawed hash function was intended (which is bad whether this is true or false) and their network going down for three days is a huge red flag that the protocol cannot be used in a decentralised way. He talks a good game but if you have any technical background you can see he isn't addressing what's being asked and is avoiding valid criticism via hand waving and character attacks.

AlexAltea 9y ago

There are several misconceptions about what universal quantum computers could do. One of them is talking about exponential increase of computing power with each new qubit. It just doesn't work like that. This brief talk from Scott Aaronson tackles this issue quite well: https://www.youtube.com/watch?v=JvIbrDR1G_c https://www.youtube.com/watch?v=JvIbrDR1G_c While quantum computers threaten some cryptographic schemes, it will just be the end of those schemes, not the end of cryptography in general (see: post-quantum cryptography). As long as we still have problems that are hard to compute and easy to verify, we can have cryptocurrencies. Quantum computers do not give "unlimited computing power" and do not threaten the existence of cryptocurrencies in general.

rocqua 9y ago
As far as I know, there isn't a conclusive decent public-key algorithm that is quantum resistent. We know that Diffie Helmann, RSA and their elliptic counterparts are broken in quantum. That was essentially all we had. I know that 'lattice based cryptography' is a potential option, and believe there are more potential options. However, as far as I know it is not even clear whether these are safe against classical computers. I should note that I don't know much more about 'lattice based crypto' than the name and the hope it is quantum resistent.

jVinc 9y ago

crypto-currency is not about scarcity of numbers its about proof of work. Bitcoin started with relatively little computation power and has now scaled to where more power is spent than a small country uses in the mining operation... Its unfeasible to mine bitcoin on a cpu or gpu because ASICs are just so much more efficient. None of this scaling in hashing rate really changing the underlying concept which is that you prove you did some work in order to add blocks. If quantum computers do in fact result in a couple of thousand orders of magnitude raise in the hashing rate... well then miners will use different hardware the difficulty of the network will adjust each 10 minutes as new hardware gets added, and after the change you'll just have a large army of quantum miners instead of ASIC miners. Remember the exitsanse of quantum computers does not prove P=NP, which is to say, even with quantum computers you can still have the class of problems which are difficult to solve but easy to verify which is the essential component of proof of work.

roywiggins 9y ago
> If quantum computers do in fact result in a couple of thousand orders of magnitude raise in the hashing rate... well then miners will use different hardware the difficulty of the network will adjust each 10 minutes as new hardware gets added, and after the change you'll just have a large army of quantum miners instead of ASIC miners. If it's a couple of thousand orders of magnitude, the first person with a working quantum chip might entirely dominate the hashpower, long before the chip is available commercially. So you'd end up concentrating hashpower into a couple of BigCorps's hands. Like, if I went back in time to the beginning of BTC with an ASIC I'd probably completely dominate the baby blockchain and outcompete the entire network.

Obi_Juan_Kenobi 9y ago

There are numerous options for quantum-resistant algorithms. Existing cryptographic currencies can fork to whatever seems most suitable. This wouldn't be a trivial change, but it can certainly be done. https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography There is also no such thing as 'unlimited' computing power with regard to proof of work. Difficulty simply adjusts, and the cost of a network attack will always be related to the rewards of mining.

zamalek 9y ago

Merkle-Damgard hash functions (such as SHA256) are merely weakened by QC. SHA256 is considered good enough and as such, BTC mining should be able to weather QC. There is a variant of Shor's Algorithm that can solve ECDSA, so you might have problems with your BTC wallet; a fork using a new resistant asymmetric algorithm would be needed. Memory-constrained algorithms, such as scrypt, should be quantum resistant based on what I know (which isn't much). If I'm not horribly misinformed, LTC mining should therefore be resistant. Again, LTC wallets would face problems.

rocqua 9y ago
Does the same hold for hashes based non on Merkle-Damgard but the sponge construction?
- zamalek 9y ago
  It looks like we don't know, excluding some very specific sponge functions, based on some quick research.[1][2] [1]: https://eprint.iacr.org/2017/771.pdf https://eprint.iacr.org/2017/771.pdf [2]: https://crypto.stackexchange.com/questions/419/what-security-do-cryptographic-sponges-offer-against-generic-quantum-attacks/46705 https://crypto.stackexchange.com/questions/419/what-security... (NB: comments)

garmaine 9y ago

No, there are quantum resistant protocols that could be switched to instead when the gap starts to close.