Quantum Computing Series, Part 9: Quantum Cryptography

Quantum Cryptography

Quantum computing promises to open doors to many exciting technological possibilities. Quantum Cryptography is one such application area that could benefit greatly with advent of quantum computers and help make transactions secure. Perhaps the greatest benefit of quantum computing can bring to the table is securing the Internet of Things where quantum cryptography could find widespread use.

The mainstream encryption technologies that institutions rely on to conduct millions of daily transactions on the Internet would be a cakewalk for quantum computers to break, experts opine. The reason is that breaking the encryption requires intense computation power, which is way beyond today’s digital computers’ capabilities. However, quantum computers will bring about a paradigm shift to a computer’s computational power, increasing it exponentially; this will make cracking even the most sophisticated encryption mechanism a child’s play for a quantum computer. This indeed sounds like a genuine threat, but technology could be leveraged either way and that’s true for quantum computing. Currently, the focus of quantum computing is to help security analysts in a number of ways: from identifying security incidents to identifying and categorizing the incidents as actual threats.

Quantum computers, when they do become a reality, will thus render current cryptographic standards obsolete. If quantum computers appear as a viable technology tomorrow, there would be precious little alternative and acceptable means for securing our online and wireless transactions.

RSA is a widely used public-key encryption algorithm. In a nutshell, here’s how RSA operates. To use RSA, two keys are required: a public key to encode the message and a private key to decode the message. A user creates and publishes a public key. Anyone can use this public key (hence the name public) to encode a message. The public key is the product of two large prime numbers. The prime factors are kept secret which is used to decode the message. Using the public key, anyone can encode a message meant for that user. However, only the user can decode the message by using the private key, which again is based on the secret prime factors. The integrity or robustness of RSA encryption is directly dependent on recovering the prime factors when only the multiplicative product (on which public key is based) is known.

Encryption methods and algorithms are continuously being upgraded to make them more complex and harder to break. It’s a catch-up game where cryptographers always try to be one step ahead of hackers who always seek to break the encryption. Quantum computing changes the whole scenario. The algorithms considered today extremely sophisticated and complex would be ridiculously simple for quantum computers to break. This mandates a complete overhaul of online encryption algorithms. The efforts in developing such algorithms suited for the quantum computing world are known as Post-Quantum Cryptography.

The researchers must be able to devise new algorithms that are able to maintain security reliably in the quantum computing ecosystem replete with mind-boggling computational prowess and complexity.

Take, for instance, RSA, which is based primarily on the concept of it being extremely difficult to factor a large integer into a product of primes. Factoring has always been considered tough to crack because it is computationally intensive. If the problem of being computationally intensive is solved, then factoring suddenly wouldn’t be that hard of a problem. Consequently, the whole premise on which RSA is based wouldn’t take long to crumble. And, that’s something that quantum computing promises to do.

Public key systems are built from computational problems in algebra and number theory. A system can be secure if its corresponding computational problem is virtually unsolvable in the absence of a secret key. However, no current computational problems are too hard to solve. For quantum computers, solving the computational problems corresponding to most public key systems is quite easy.

Integer factorization relies on the shortcoming of insufficient computational ability of today’s digital computers to work with very large integers. The security of public key cryptographic systems is solely based on the fact that it lacks computational power.

Shor’s Algorithm

Large integer factorization is considered infeasible for ordinary digital computers. For example, a product of two 300-digit prime numbers. Using Shor’s algorithm—the first quantum computing algorithm that was proposed by Peter Shor, a computer science researcher at AT&T Bell Labs — a quantum computer could quite efficiently solve this problem of finding factors. This ability would render even today’s most sophisticated cryptographic systems to be easily decrypted using a quantum computer by employing a polynomial time algorithm to solve the problem.

Quantum Key Distribution

Most of the public key ciphers that are popular have the basic premise of difficulty in factoring integers or the discrete logarithm problem. Both of these can be solved by Shor’s algorithm. Most of the well-known encryption algorithms such as RSA, Diffie-Hellman, and Elliptic curve Diffie-Hellman are quite susceptible to breaking.

Quantum Entanglement

Entanglement is used in some protocols of quantum cryptography. The reason is the “shared noise” of entanglement presenting itself as a great one-time pad. Further, using entanglement-based quantum cryptography allows much easier detection of the presence of an intruder or interceptor. This is because the moment a measurement is made on the entangled pair system, it destroys the entanglement.

A well-known example of quantum cryptography is quantum key distribution. It offers a theoretically secure solution to the key exchange problem. Using quantum key distribution, a key is shared between two parties without the risk of any information leak. Even if any third party eavesdrops on the communication between the two parties, the shared key is not revealed. The moment someone tries to glean information when the key is being established, key establishment fails. Both the parties notice this instantly. On the other hand, once the key establishes, it is used for encrypted communication using classical techniques. For example, the exchanged key could then be used for symmetric cryptography.

Today’s widely used public-key encryption and signature schemes such as RSA are easy to break using Shor’s algorithm for factoring and discrete logarithms running on a quantum computer. Quantum cryptography allows completion of different cryptographic tasks that are seemingly impossible when using only classical communication. A quantum state encodes some data within it, and when someone tries to read that encoded data, the state changes. This property of quantum computing makes it very useful to detect eavesdropping during quantum key distribution.

Quantum key distribution is considered secure even against quantum computers. This is because it is based on physical principles of the quantum world and not mathematical complexity, like post-quantum cryptography.


Cryptanalysis comes from the Greek terms: kryptós, meaning hidden, and analýein, meaning to untie. It is the study of information systems to understand the hidden aspects of the systems. Cryptanalysis can be used to breach cryptographic security systems—even without knowing the cryptographic key—thereby revealing the contents of encrypted messages.

Cryptanalysis also includes analyzing side-channel attacks. These attacks, instead of targeting any weaknesses in the cryptographic algorithms, exploit the loopholes in implementing these algorithms.

Cryptanalysis techniques, methods, and means have witnessed a sea-change through the history of cryptography. The primary challenge has been to deal with the increasing cryptographic complexity. Right from the pen-and-paper methods of yesteryear, to basic machines such as the British Bombes and Colossus computers at Bletchley Park in World War II, to the amazingly advanced mathematical computerized schemes popular today. Breaking modern cryptosystems require solving problems in pure mathematics. One such well-known problem is integer factorization.

Quantum Computing Applications for Cryptanalysis

Currently, there is a lot of research being done on quantum computers. Efforts to build a practical real-world usable quantum computer, which could find potential use in cryptanalysis, are underway. For example, Shor’s algorithm for factoring large integers in polynomial time can break some commonly used forms of public-key encryption.

Even brute force key search can achieve significant speed gains. Grover’s algorithm, running on a quantum computer, can make the search quadratically faster. Using the double key lengths, however, could counter this.

For cryptanalysis, opportunities have increased in terms of interception, side channel attacks, bugging, and quantum computers. Former NSA technical director Brian Snow had raised the concern regarding academic and government cryptographers’ slow progress in cryptanalysis. However, it might be premature to do a postmortem for cryptanalysis. It remains unknown how effective the cryptanalytic methods used by intelligence agencies are as many serious attacks have been reported.

Instances of Attacks Against Cryptographic Primitives

The following attacks against both academic and practical cryptographic primitives have been published:

  • Madryga, a block cipher, was proposed in 1984 but wasn’t widely used; in 1998, it was found susceptible to ciphertext-only attacks
  • FEAL-4, a proposed replacement for DES standard encryption algorithm, came under a barrage of attacks, many of which are entirely practical, from the academic community causing it to break down
  • A5/1, A5/2, CMEA, and DECT systems find use in mobile and wireless phones. Using commonly available computers and related electronic devices, these can be broken in the blink of an eye.
  • Brute-force keyspace search, a primitive technique, has proven effective to break ciphers such as single-DES and 40-bit export-strength cryptography and applications such as the DVD Content Scrambling System.
  • Wired Equivalent Privacy (WEP) is a protocol for securing Wi-Fi communication. In 2001, due to a weakness in the RC4 cipher and the design of the WEP protocol itself, it was proven to be breakable. Subsequently, Wi-Fi Protected Access replaced WEP, lending Wi-Fi networks better security.
  • The widely popular and adapted MD5 algorithm too was proven to be insecure in 2008. Researchers broke SSL by leveraging shortcomings in the MD5 hash function as well as the loopholes in the certificate-issuance process. This made it possible to exploit collision attacks on hash functions. Subsequently, certificate issuers made changes to the established certificate-issuance practices to protect against similar future attacks.

In conclusion, even though the best modern ciphers might be way more resistant to cryptanalysis than the Enigma, the larger umbrella of information security, and within it cryptanalysis specifically, remain quite active.

Learn more: https://amyxinternetofthings.com/