What Will Cryptography Look Like in a Post-Quantum World?
There is no doubt that current encryption standards will have to evolve in order to stand strong against quantum computers.
Cryptography is the practice of using code to protect different types of information. Cryptography allows users to either store sensitive information or transmit it across insecure networks so that it cannot be read by anyone except the intended recipient. From withdrawing money from an ATM to using a secure browser, we all use some form of cryptography in our day-to-day lives.
Objectives
The four objectives — data confidentiality, data integrity, data non-repudiation, and data authenticity — form the foundation of modern cryptography. For the sake of explanation, let's call the sender, Alice, and the recipient, Bob.
Data confidentiality ensures that the contents of a message are encoded by Alice, using a cryptographic key. Once Bob receives the encrypted message, he decodes it using a cryptographic key, which doesn’t necessarily have to be the same one used as Alice.
Data integrity ensures that the message received by Bob is the same as the message sent by Alice. A process called hashing, in which a unique message digest is generated from the original message and sent along with it to Bob so that he can create a second unique message digest from the message to compare to the original one, is used to check data integrity.
Data non-repudiation ensures that a sender cannot deny the authenticity of a message that they have sent or a transaction they have conducted. Data signatures and cryptographic evidence can be used to provide proof of origin or receipt, so neither Alice nor Bob can deny their involvement in a particular communication or action.
Data authenticity ensures that the message received by Bob did come from Alice. This is done by using digital signatures, an application of hashing so that Alice can prove her identity to Bob, even if he has no personal knowledge of her identity.
Current-Day Cryptography
Secret Key Encryption
Secret key or symmetric-key encryption uses a single shared secret key, known only to the sender and receiver, for encryption and decryption. Keeping the secret key a secret is crucial because the moment the key is compromised the security of the entire encryption is also compromised.
Examples of symmetric-key cryptography are the Advanced Encryption Standard (AES) and Data Encryption Standard (DES) which are used to protect sensitive information.
Public Key Encryption
Public key or asymmetric-key encryption uses a pair of keys, a public key and a private key. The public key is known to everyone and is used by the sender to encrypt the message. The private key is known only to the recipient and is used by them to decrypt the cipher text. Unlike private key encryption, the recipient doesn’t need to share their private key.
Examples of public-key cryptography are Rivest-Shamir-Adleman (RSA) encryption, the Elliptic Curve Digital Signature Algorithm (ECDSA), and the Diffie-Hellman key exchange.
Hash Functions
Hash functions are a fundamental tool used to uphold data integrity. These functions transform input data and produce a deterministic fixed-size output. This resulting output is often referred to as a “hash value” or “digest.” They are designed to be computationally efficient, allowing for quick calculation of hash values, even for large inputs.
Examples of hash functions include the Secure Hash Algorithm (SHA) family, Message Digest Algorithm 5 (MD5), and Whirlpool.
Quantum Cryptography
By extension, quantum cryptography is the same are current-day cryptography except it leverages the properties of quantum mechanics and quantum phenomena to secure communication.
Quantum Key Distribution
Quantum Key Distribution (QKD) is a secure method that allows two parties, Alice and Bob, to exchange cryptographic keys over a potentially insecure communication channel while detecting any eavesdropping attempts. Here’s an overview of how it works:
Alice and Bob both have a quantum system (typically involving photons) and a classical communication channel (e.g. an optical fiber) for exchanging information. They both also share a publicly authenticated channel to initially exchange certain information and authenticate each other.
Alice generates a stream of individual photons with specific quantum properties and encodes her secret key information onto these photons using the chosen quantum property. One by one, Alice sends her encoded photons over the communication channel to Bob.
Upon receiving each photon, Bob measures its quantum property using specialized detectors, however, the measurement basis may be chosen randomly for each photon.
Due to the principles of quantum mechanics, any attempt by Eve to intrude on the QKD transmission between Alice and Bob would be detected. Photons are extremely fragile so if anyone were to try and intercept or measure the quantum state of the photons would inevitably disturb their properties. Thus, if Eve were to eavesdrop on the channel, the disturbance would be detectable to Alice and Bob.
Once the transmission is over, Alice and Bob compare notes over the publicly authenticated channel to reveal which basis Alice used to encode each photon and the results of Bob’s measurements with Alice’s encoding. If there are any discrepancies between Alice’s encoding and Bob’s measurements, it would indicate potential eavesdropping.
If Alice and Bob detect a significant error rate, which can’t be attributed to noise, the key exchange is aborted. Otherwise, they would apply a process called ‘privacy amplification’ which results in a shared secret key known only to Alice and Bob, which can be used for secure communication. This same key is then used in conventional cryptographic protocols to encrypt and decrypt messages between Alice and Bob.
The crucial advantage of QKD is the fact that it provides a way for Alice and Bob to create a secret key while being able to detect any potential eavesdropping attempts by measuring the quantum properties of the exchanged photons. This property makes QKD highly secure and resistant to quantum attacks, even in the future when quantum computers might threaten classical cryptographic methods.
No-Cloning Theorem
Imagine you have a special photocopier that can create perfect copies of any document you put into it. For example, if you put in a sheet of paper with the number “0” written on it, and out comes an identical copy with the same “0.”
Let’s switch gears and enter the realm of quantum mechanics, where things get a lot more different than the world we are used to living in. In this quantum world, instead of copying documents, we’re dealing with quantum particles in specific quantum states (qubits).
The No-Cloning Theorem is a fundamental concept in quantum mechanics which essentially states that:
You can’t copy quantum states, no matter how hard you try.
So, you’ve got your qubit in some quantum state, like a superposition of 0 and 1 at the same time (think Schrödinger’s cat being both alive and dead). You want to make a photocopy of it. You put your qubit into the quantum photocopier and press the “Copy” button, but guess what? The universe says, “Uh-uh, not happening!”
Unlike our classical world, where you can copy documents all day long, in the quantum world, copying is forbidden. You are incapable of producing an exact clone of a quantum state.
This makes the No-Cloning Theorem especially important in quantum cryptography because it’s what makes quantum communication so secure. When Alice and Bob send qubits over a quantum channel, they know that if Eve were to eavesdrop, she wouldn’t be able to make perfect copies without leaving a quantum footprint.
The No-Cloning Theorem is the guardian of quantum secrets and is the fundamental concept that makes quantum communication secure.
Heisenberg Uncertainty Principle
The Heisenberg Uncertainty Principle governs the relationship between the precision of measurements for two essential properties of particles: position and momentum. It states that you can never know both the position and momentum of a particle with unlimited precision at the same time. The more accurately you measure one of these properties, the less accurately you can measure the other. It’s like a cosmic blur.
This principle has real-world implications, especially in quantum cryptography. Closely related to the no-cloning principle, the uncertainty principle is essential in ensuring the security of QKD since any measurement by an eavesdropper introduces uncertainty that can be detected.
Shor’s Algorithm
Developed by Peter Shor in 1994, Shor’s Algorithm is a groundbreaking quantum algorithm because it efficiently factors large numbers, a task that is exceptionally difficult for classical computers. This capability has significant implications for cryptography, particularly regarding the security of widely used public-key encryption algorithms like RSA.
RSA encryption relies on the challenge of factoring large composite numbers into their prime factors. Its security is essentially tied to the assumption that factoring large numbers is a computationally intensive task, which it is for classical computers.
Schor’s algorithm takes advantage of quantum parallelism and the principles of quantum computing to explore multiple possibilities simultaneously. This quantum speedup enables it to factor large numbers in polynomial time, while classical algorithms would require exponential time.
The development of Shor’s algorithm and the potential threat it poses to classical public-key encryption schemes has prompted research into post-quantum cryptography.
Post-Quantum Cryptography
Due to the potential threat posed by quantum computers to classical cryptographic systems, there is growing interest in post-quantum cryptography. There is no doubt that current encryption standards will have to evolve in order to stand strong against quantum computers.
Post-quantum cryptography will have to develop encryption algorithms that are resistant to attacks by quantum computers. Researchers are currently exploring diverse approaches like lattice-based cryptography, code-based cryptography, and multivariate polynomial cryptography which are based on mathematical problems that are believed to be difficult for both classical and quantum computers to solve.
The transition to post-quantum cryptography will be gradual. As quantum computers become more and more powerful and sophisticated, organizations and industries need to plan for a smooth migration to quantum-resistant encryption to protect their sensitive data and communication.
NIST Migration Plan
The U.S. National Institute of Standards and Technology (NIST) is actively involved in research and standardization efforts related to Post-Quantum Cryptography.
They initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. NIST recognizes that the question of when a large-scale quantum computer will be built is merely a significant engineering challenge. It’s taken almost 20 years to deploy modern-day public key cryptography infrastructure, so ‘quantum proofing’ the current information security systems should start now.
