Post-quantum cryptography, as the next 5-10 years to gradually replace RSA, Diffie-Hellman, elliptic curve and other current public key cryptography algorithms, is being understood by more and more people. At present, the new generation of cryptographic technology standards being developed by the National Institute of Standards and Technology (NIST) is the post-quantum cryptographic standard.
< br >
1.1.1, What is post-quantum cryptography?
Post-quantum cryptography is a new generation of cryptography algorithms that can resist the attack of quantum computers on existing cryptography algorithms.
< br >
The so-called \"post\" is because of the emergence of quantum computers, and the vast majority of existing public key cryptography algorithms (RSA, Diffie-Hellman, elliptic curve, etc.) can be broken by sufficiently large and stable quantum computers, so cryptography algorithms that can resist such attacks can survive in quantum computing and its subsequent era, so it is called \"post\" quantum cryptography. Some people also call it \"anti-quantum cryptography,\" which means the same thing. The English expression is: " Post-quantum Cryptography (PQC)" , or " Quantum-resistant cryptography" .
< br >
1.1.2. Why is it needed?
1) Quantum computers are very powerful, but the premise of using their powerful computing power is that there is a quantum algorithm that can efficiently solve the problem, otherwise quantum computers are useless, but because of their high cost. Data: A 5-qubit quantum computer costs around $10 million.
< br >
2) Some of the powerful algorithms\/applications available for quantum computers include: cryptographic algorithm security, mathematical computation, machine learning, etc.
< br >
3) For the security of cryptographic algorithms, mainly for public key cryptographic algorithms:
< br >
3.1) Mathematical problems that depend on the security of public key cryptography algorithms can be solved by efficient quantum algorithms. These public-key cryptography algorithms are no longer secure because the underlying dependent mathematical problems are solved. These mathematical problems include discrete logarithms (and elliptic curve versions), decomposition of large integers, and so on. This directly affects the current RSA, Diffie-Hellman, elliptic curve and other algorithms. The famous quantum algorithm was developed in 1994. s algorithm.
< br >
3.2) Regarding symmetric cryptographic algorithms and hash functions (such as AES, SHA1, SHA2, etc.), although there are quantum algorithms that can theoretically be broken, the impact of this algorithm is limited and there are many restrictions. The famous quantum algorithm was Grover in 1996. s algorithm.
< br >
4) For public key cryptography algorithm, the impact of quantum computer on security:
< br >
4.1) Completely break the currently widely used public key cryptography algorithm
< br >
4.2) Increasing the length of the parameter is not useful. Some people say: the length of RSA from 1024 to 2048 bits or even longer, isn't it safe? The answer is: for existing classical computers and algorithms, this is OK. But for quantum computers and algorithms, this is futile (unless RSA grows to 1GB or more in length). But in that case, does the algorithm still work? What about other algorithms?)
< br >
4.3) A new public key cryptography algorithm is required
< br >
5) For symmetric cryptographic algorithms, the impact of quantum computers on security:
< br >
5.1) Reduce the security of the existing algorithm: the security is reduced from k-bit to k\/2-bit
< br >
5.2) Increasing the length of the parameter is useful
< br >
5.3) Double the length of the key or hash, for example: AES-128 upgraded to AES-256, SHA-256 upgraded to SHA-512, etc. But this is not necessary, for reasons that will be explained later
< br >
6) Estimated time and cost of breaking RSA-2048:2030, quantum computer, $1 billion, nuclear power plant (PQCrypto 2014, Matteo Mariantoni estimates)
< br >
Copy code
About quantum computer, introduce a few more conclusions:
< br >
(1) The quantity of qubits is important, but the quality is even more important. In quantum computers currently being built, such as Google's 72 qubit chip, the qubits, or quantum physical bits, are of poor quality. Due to physical mechanisms such as quantum coherence, error correction mechanisms must be introduced, but hundreds of quantum physical bits are needed for error correction to achieve the function of a quantum logic bit
(2) Breaking the existing public key cryptography algorithm requires thousands or even tens of thousands of logical bits. Combined with the above, we can see that building quantum computers is still at a very early stage
(3) The D-Wave 2000Q \"quantum computer\" built by D-Wave is actually a quantum annealing algorithm, and is not a universally applicable quantum computer in the true sense
(4) For quantum algorithms (such as Grover), an exponential level of memory is required, so the threat of Grover's algorithm is less urgent than Shor's algorithm
Copy code
To summarize, Dustin Moody, head of the post-quantum cryptography team at NIST, spoke at the AsiaCrypt 2017 conference:
< br >
< br >
< br >
can see
< br >
(1) Public key cryptography algorithm: Red Cross, need to replace the post-quantum cryptography algorithm
< br >
(2) Symmetric cryptographic algorithm: blue box, less urgent need for new algorithms to replace. You can adjust the parameters to solve the problem
< br >
1.1.3, What do we need?
Post-quantum cryptography, obviously. More precisely, it is the post-quantum cryptography standard. An important takeaway from cryptography practice is: don't build your own wheels (unless you're a big guy). The algorithms we use now, such as RSA, Diffie-Hellman, and elliptic curves, have gradually entered the application field after being set as international standards.
< br >
Post-quantum cryptography algorithms should:
< br >
(1) Security: not only safe under current computing conditions, but also safe under quantum computers
< br >
(2) Fast running speed: The existing results show that the calculation speed of post-quantum cryptography can exceed that of existing public key cryptography under the same security strength
< br >
(3) Reasonable communication overhead: In practice, an algorithm with a public key\/ciphertext size of several meters or even larger is almost never used. The current RSA-2048 public key size is about 256 bytes and the elliptic curve is about 64 bytes. The best post-quantum cryptography algorithms have public keys around 1KB in size
< br >
(4) can be used as a direct substitute for existing algorithms and protocols, such as public key encryption, key exchange, digital signature, etc
< br >
(5) Wider application scenarios: for example: Homomorphic Encryption (Homomorphic Encryption), Attribute-based Encryption (attribute-based encryption), and Functional encryption (Functional Encryption) are indistinguishable Advanced cryptographic applications such as Indistinguishability Obfuscation