Everything is hackable! During the RSA Conference 2017 Crypto panel, Prof. Shamir (the letter “S” in the RSA) said, “I think there is a higher chance that RSA could be broken by a mathematical attack.” and he also wondered to note “Quantum Computers” will be a reality soon! That said, the evolution of practical quantum computers are not far away, according to a recent MIT Technology review article, which highlighted most research works on Quantum computing are closer to a solution (Google Quantum Computer!). This means quantum computations can pose some serious threats to existing public-key cryptography mechanisms in use. Are they serious or deluded? Not really, It turns out that they are right to rave.
Even NIST believes on those expert predictions that within the next 20 or so years, the emergence of quantum computers will easily break all public key cryptography and digital signature schemes (ex. RSA, ECDH, ECDSA) currently being used. The impact on symmetric key mechanisms is not that much as it can be handled through larger key sizes (verified by using Grover’s algorithm and Shor’s algorithm — Both are commonly used for breaking Cryptography).
Not surprising, last year (Dec 2016), NIST launched a Post-Quantum Cryptography project initiative to develop quantum-resistant public-key cryptographic algorithms that are secure against both quantum and modern computers currently being used and can also interoperate with existing communications protocols and networks. Currently. there are about 5 algorithm proposals for public-key post-quantum cryptography considered to be quantum-safe are being evaluated.
- Lattice-based Cryptography: Based on the construction of cryptographic primitives using computational lattice problems. They are known to be secure assuming the worst-case hardness of certain lattice problems as it has proven to be difficult to estimate of the security of lattice schemes. In 2009, Craig Gentry introduced the first fully homomorphic encryption scheme, which was based on a lattice problem. Other known lattice-based cryptographic functions are Indistinguishability Obfuscation, cryptographic maps, attribute-based functional encryption. NTRU encryption and NTRU signatures have been researched for many years without anyone finding a successful attack.
- Multivariate Cryptography: Based on solving multivariate equations. The Rainbow scheme is based on multivariate cryptography, which could be a potential signature scheme to provide the basis for a quantum secure digital signature.
- Code-based Cryptography: Based on error-correcting codes, such as the McEliece and Niederreiter encryption algorithms and related signature scheme. EU Commission recommended McEliece public key encryption as a candidate for long-term protection against attacks by quantum computation.
- Hash-based Cryptography: Based on Hash-based signature schemes like Lamport signature scheme (one-time signature and Merkel signature scheme based on Hash trees (also called Merkel trees — used in Bitcoin Blockchain).They are known to be secure as long as hashes are not invertible and it certainly depends on large hash sizes.
- Supersingular Elliptic Curve Isogeny Cryptography: Based on the Supersingular elliptic curve and it works like Diffie-Hellman Key exchange methods and its implementation, it can be an alternative to Diffie-Hellman with forward secrecy that can resist and provide protection against quantum computations.
All are quite promising developments, with NIST investing on PQC initiatives newer algorithms and their prototype implementations are evolving faster. Lately, Google Research has evolved an implementation of Lattice-based Cryptography using Ring Learning-with-Errors (RLWE) algorithm has integrated into OpenSSL, which can be potentially leveraged as a potential alternative to current public-key encryption schemes for providing post-quantum security for TLS and IPSec/IKE.
Quantum-safe Blockchain ?
Looking into the Public-key infrastructure risks with the impact of quantum computing, As we think, Blockchain is potentially vulnerable because of its reliance on PKI based digital signatures and hashing algorithms. The heavy use of Hashing algorithms will have a lesser impact as the chain can be easily enhanced by upgrading it from SHA-256 to SHA-384 to SHA-512 and so on. (For example, Bitcoin address is just an SHA-256 hash of your public key). The interesting aspect, in the proof-of-work miners world, there will be an unfair advantage to the miner who uses the quantum computer will get the biggest miner reward 🙂
Update (Oct 16):
How Google’s Quantum Computer Could Change the World (Wallstreet Journal, Oct 16)
NIST IR-8105 – http://nvlpubs.nist.gov/nistpubs/ir/2016/NIST.IR.8105.pdf
NIST PQC Project initiative – https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/