“If current progress continues, quantum computers will be able to crack public key cryptography,” writes CNET, “potentially creating a serious threat to the crypto world, where some currencies are valued at hundreds of billions of dollars.” If encryption is broken, attackers can impersonate the legitimate owners of cryptocurrency, NFTs or other such digital assets.
“Once quantum computing becomes powerful enough, then essentially all the security guarantees will go out of the window,” Dawn Song, a computer security entrepreneur and professor at the University of California, Berkeley, told the Collective[i] Forecast forum in October. “When public key cryptography is broken, users could be losing their funds and the whole system will break….”
“We expect that within a few years, sufficiently powerful computers will be available” for cracking blockchains open, said Nir Minerbi, CEO of quantum software maker Classiq Technologies. The good news for cryptocurrency fans is the quantum computing problem can be fixed by adopting the same post-quantum cryptography technology that the computing industry already has begun developing.
The U.S. government’s National Institute of Standards and Technology, trying to get ahead of the problem, is several years into a careful process to find quantum-proof cryptography algorithms with involvement from researchers around the globe. Indeed, several cryptocurrency and blockchain efforts are actively working on quantum resistant software…
A problem with the post-quantum cryptography algorithms under consideration so far, though, is that they generally need longer numeric encryption keys and longer processing times, says Peter Chapman, CEO of quantum computer maker IonQ. That could substantially increase the amount of computing horsepower needed to house blockchains.
The real quantum test for cryptocurrencies will be governance structures, not technologies, says Hunter Jensen, chief technology officer of Permission.io, a company using cryptocurrency for a targeted advertising system… “It will be the truly decentralized currencies which will get hit if their communities are too slow and disorganized to act,” said Andersen Cheng, chief executive at Post Quantum, a London based company that sells post-quantum encryption technology.
A quantum attack algorithm permutes and combines the wave functions of the qbits in a way to arrive at the right answer being the most likely. Run it a few times and the most likely answer will be the most common.
We know of two primary algorithms, Shor’s and Grover’s. Grovers reduces the complexity of a dictionary lookup to the square root of the normal complexity. So effectively halves the key size. Shor’s solved the dlog and factoring problem efficiently breaking RSA and ECC public key systems.
The approaches to making post quantum secure algorithms for Grover is to increase the key size. The approach for public key systems involves coming up with new public key systems based on other mathematics for which you can show there is no permutation or combination of the qbit wave functions that will yield and answer.
That part is a solved problem and there are many such algorithms, however the other problem is you have to show that your quantum secure algorithm is also secure from conventional cryptanalysis and this is where many promising algorithms (E.G. ones without ridiculous key sizes) have failed. The others will never make it anyway because they require silly amounts of data to be sent back and forth. Check out the NIST post quantum cryptography contenders for the current leaders in the pack.
Ignore any idiot telling you to just double encrypt – it doesn’t solve the public key problem and a block cipher is a bijective mapping. A bijective mapping applied to another bijective mapping is just another bijective mapping which will not upset Grover’s algorithm much. The problem space is in the realm of public key cryptography.
- Simulating Physics with Computers” (PDF). International Journal of Theoretical Physics. 21 (6/7): 467–488.
- Breaking RSA Encryption with a Quantum Computer: Shor’s Factoring Algorithm” (PDF). Physics 481-681 Lecture Notes. Cornell University. Archived from the original (PDF) on 15 November 2012.
- “Quantum gold rush: the private funding pouring into quantum start-ups”. Nature. 574 (7776): 22–24.
- Trump budget proposal boosts funding for artificial intelligence, quantum computing”. The Hill.
- Hello quantum world! Google publishes landmark quantum supremacy claim”. Nature. 574 (7779): 461–462. Bibcode:2019Natur.574..461G. doi:10.1038/d41586-019-03213-z. PMID 31645740.
- Opinion | Why Google’s Quantum Supremacy Milestone Matters”. The New York Times. ISSN 0362-4331. Retrieved 25 September 2021.
- “On ‘Quantum Supremacy‘“. IBM Research Blog. 22 October 2019. Retrieved 9 February 2021.
- The Problem with Quantum Computers”. Scientific American.
- Nielsen, p. 29
- Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/cbo9780511976667. ISBN 9780511976667.
- Quantum Algorithm Zoo Archived 29 April 2018 at the Wayback Machine – Stephen Jordan’s Homepage
- Quantum Computers. ISBN 9781439243497.[self-published source?]
- Quantum Algorithm for the Collision Problem”, in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms, New York, NY: Springer, pp. 1662–1664, arXiv:quant-ph/9705002,
- A Quantum Algorithm for the Hamiltonian NAND Tree”. Theory of Computing. 4 (1): 169–190. doi:10.4086/toc.2008.v004a008. ISSN 1557-2862. S2CID 8258191.
- Integer Factoring” (PDF). Designs, Codes and Cryptography. 19 (2/3): 101–128. doi:10.1023/A:1008397921377. S2CID 9816153. Archived from the original (PDF) on 10 April 2015.
- A Public-Key Cryptosystem Based On Algebraic Coding Theory” (PDF). DSNPR. 44: 114–116. Bibcode:1978DSNPR..44..114M.
- Dihedral Hidden Subgroup Problem: A Survey”. Information and Media Technologies. 1 (1): 178–185. doi:10.2197/ipsjdc.1.470.
- Quantum computers will change the world (if they work)”. Wired UK.
- NSA seeks to build quantum computer that could crack most types of encryption”. The Washington Post.
- The Father of Quantum Computing”. Wired.
- What Can We Do with a Quantum Computer?”. Institute for Advanced Study.
- “Lunch & Learn: Quantum Computing”. Sibos TV. 21 November 2018. Retrieved 4 February 2021 – via YouTube.
- Quantum machine learning”. Nature. 549 (7671): 195–202. arXiv:1611.09347. Bibcode:2017Natur.549..195B. doi:10.1038/nature23474. ISSN 0028-0836. PMID 28905917. S2CID 64536201.
- Quantum Computing in the NISQ era and beyond”. Quantum. 2: 79. doi:10.22331/q-2018-08-06-79. S2CID 44098998.
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning”. Physical Review A. 94 (2): 022308. arXiv:1510.07611. Bibcode:2016PhRvA..94b2308B. doi:10.1103/PhysRevA.94.022308.
- Quantum computing assisted deep learning for fault detection and diagnosis in industrial process systems”. Computers & Chemical Engineering. 143: 107119. arXiv:2003.00264. doi:10.1016/j.compchemeng.2020.107119. ISSN 0098-1354. S2CID 211678230.
- Quantum computing based hybrid deep learning for fault diagnosis in electrical power systems”. Applied Energy. 303: 117628. doi:10.1016/j.apenergy.2021.117628. ISSN 0306-2619.
- The prospects of quantum computing in computational molecular biology”. WIREs Computational Molecular Science. 11. doi:10.1002/wcms.1481. S2CID 218889377.
- Lloyd, S. (23 August 1996). “Universal Quantum Simulators”. Science. 273 (5278): 1073–1078. Bibcode:1996Sci…273.1073L. doi:10.1126/science.273.5278.1073. PMID 8688088. S2CID 43496899.
- The Case Against Quantum Computing”. IEEE Spectrum.