Secrets of the Quantum Lockbox: A Cryptic Tale of Post Quantum Encryption — Day 20
Day20 of #Quantum30 Challenge
Hello readers! With the completion of tasks of 20th day of #Quantum30 challenge, 2/3rd of this challenge is completed. Now, a lot of us have heard that Quantum Cryptography can break our daily used encryption schemes, well, that’s true, BUT, what if I say there is a way to even safeguard againt the supreme Quantum Computer. I’m talking about Post-Quantum Cryptography, do not confuse this with Quantum Cryptography, it is a different subject. Let’s start!
The first resource is “Post-quantum cryptography: Security after Shor’s algorithm” from the YouTube channel Chalk Talk.
1. Introduction to NIST:
The National Institute of Standards and Technology (NIST) is a US government entity responsible for maintaining standards in science and technology. NIST sells calibrated samples and maintains a Digital Library of Mathematical Functions. It’s involved in promoting the metric system and is currently running a contest to establish post-quantum cryptography standards.
2. Threats from Quantum Computers:
Quantum computers pose a significant threat to modern cryptography. Public-key cryptography relies on math problems that are easy to perform but hard to reverse. Quantum computers, with their potential to solve these problems quickly, could undermine security in encryption methods like RSA, Diffie-Hellman, and elliptic curve cryptography.
3. Shor’s Algorithm:
In 1994, Peter Shor proposed Shor’s algorithm, designed to run on quantum computers. It can factor large numbers and solve discrete log problems efficiently. While existing quantum computers are not yet powerful enough to implement this fully, the possibility of building a strong enough quantum computer in the future raises concerns about the security of current encryption methods.
4. Quantum Threats and Post-Quantum Cryptography:
Quantum computers could potentially decrypt stored messages encrypted with current methods, leading to the need for post-quantum cryptography. This form of cryptography ensures security against attacks from quantum computers while functioning on classical computers.
5. NIST’s Post-Quantum Standardization Process:
NIST’s approach involves a contest where researchers propose new cryptographic algorithms. These submissions go through multiple rounds of review and analysis. While no proposal can guarantee absolute security, this process promotes an open environment for identifying and addressing vulnerabilities.
6. Focus on Lattice-Based Cryptography:
The current contest primarily centers on lattice-based cryptography, which employs mathematical structures called lattices. Lattice-based cryptography has dominated previous rounds of the contest, but other options like code-based, hash-based, multivariate, and supersingular isogeny-based cryptography are also under consideration.
7. Exploring Non-Lattice-Based Options:
The ongoing fourth round of the NIST contest aims to expand the exploration of non-lattice-based cryptographic options. This seeks to diversify the range of cryptographic methods without replacing the already selected algorithms from previous rounds.
8. Conclusion:
NIST’s pursuit of post-quantum cryptography standards is essential due to the potential threat posed by quantum computers. While these computers might not be universally superior, they can efficiently solve specific problems, making the development of quantum-secure cryptographic standards imperative for maintaining secure communication in the future.
The second resource is “Understanding and Explaining Post-Quantum Crypto with Cartoons” from the YouTube channel RSA Conference by the speaker Klaus Schmeh, Chief Editor Marketing, Cryptovision.
Introduction:
Klaus Schmeh welcomes the audience to his presentation on post-quantum cryptography and introduces his approach of using cartoons to explain complex concepts. He also mentions his company and background.
Quantum Computers:
Schmeh introduces the concept of a quantum computer, which operates based on quantum mechanics principles. Quantum bits (qubits) can exist in multiple states simultaneously until they are observed. Quantum computers excel at parallel computations with singular results. Schmeh uses the example of Schrödinger’s cat to illustrate the quantum nature of qubits.
Quantum Computer Abilities:
Quantum computers can perform multiple computations in parallel if there’s a single result, making them suitable for tasks like finding an element in a set or identifying optimal solutions. However, they struggle with sorting, which requires multiple results. Schmeh emphasizes that quantum computers excel at prime factorization, which has implications for RSA encryption.
Quantum Computer’s Impact on RSA:
Schmeh explains the connection between prime factorization and RSA encryption. He mentions that quantum computers can efficiently break RSA encryption, particularly for smaller key lengths, which has implications for secure communication.
Alternative Cryptosystems:
Schmeh introduces the need for alternative encryption systems that are quantum-secure. He mentions six families of such systems and briefly explains each: lattice-based, code-based, hash-based, non-commutative, multivariate, and isogeny-based.
NIST’s Post-Quantum Standardization Competition:
Schmeh discusses the ongoing competition hosted by NIST for standardizing post-quantum cryptographic algorithms. He mentions the number of algorithms initially submitted and provides updates on the progress of the competition, highlighting the importance of standardization in the field.
Lattice-Based Cryptography:
Schmeh introduces the concept of lattice-based cryptography using the analogy of a snail navigating a lattice field. He explains that a lattice is defined by intersection points of equidistant lines, and the challenge is to find the closest lattice point. This concept is crucial in lattice-based cryptography.
Goldreich Cryptosystem — Lattice-based:
The presentation begins with an introduction to the Goldreich Cryptosystem, a lattice-based method also known as GH. This system employs a lattice field, with Alice’s private and public keys defined by different lattice fields. When Bob wants to encrypt a message for Alice, he places a “snail” within the lattice field. Alice can decode the message using her private key’s lattice field. While this method is quantum-proof, it has been found to be insecure due to non-quantum-related attacks.
Learning with Errors (LWE)—Lattice-based:
The focus then shifts to Learning with Errors (LWE), another lattice-based approach. LWE involves solving an overdefined equation system with small errors. Alice’s private key consists of the solution, while her public key contains the system with errors. Bob encrypts messages by utilizing random equations. Alice decrypts using her private key. LWE is proven secure due to the challenge of finding errors without knowing the solution.
Code-Based Cryptography:
The presentation moves on to code-based cryptography, using an analogy of an error-correcting spaceship. Parity bits and linear error-correcting codes are introduced. Mac Ellis encryption, similar to RSA, is explained. However, it’s resource-intensive due to the need for large key sizes and public keys.
Hash-Based Signatures:
Hash-based signatures are introduced, using a scenario involving an island salesman and Alice’s decision. Hashing functions replace the safe locks, and random numbers serve as keys. This method is secure but inefficient for large-scale use due to its long signatures.
Non-Commutative and Multivariate Algorithms:
Brief mentions are made of non-commutative algorithms, with a Rubik’s Cube analogy, and multivariate algorithms based on the ladder problem. Non-commutative algorithms are found to be insecure, while some multivariate algorithms are still in contention.
Isogeny-Based Algorithms:
The last family introduced is isogeny-based algorithms, based on maze-like structures defined by elliptic curves. While complex, they are considered secure, and one submission is still in the NIST competition.
NIST Post-Quantum Standardization Competition:
The presentation concludes with an overview of the NIST competition’s progress. Twelve lattice-based systems, seven code-based systems, four multivariate systems, and one hash-based system are still in the competition. The speaker anticipates the finalization of the winning algorithms within a few years.
In conclusion, the presentation provides an overview of various quantum-resistant cryptographic systems, their underlying principles, and their status in the NIST competition, shedding light on potential candidates for future secure encryption methods.
Thank you readers! QuantumComputingIndia #Quantum30