Hi! For subscription need to sign up or login the account.Signup|Login

Cryptography

How Quantum Computing Will Impact Cryptography And Network Security

Quantum computers are exponentially more powerful than its classical counterpart, it outperforms the most advanced type of modern digital computers, especially when it comes to random number generation in cryptography. Quantum computers work on quantum bits (qubits) which are different from the classical bits, while, classical bits hold values of either a 0 or a 1, qubits, on the other hand, can be in a superposition of 0 and 1 at the same instance of time. However, the development of quantum computers is both a boon and bane for modern technologies. No wonder in the fact that quantum computers have become the new front for both the business and government sectors. But, as mentioned earlier quantum computers are both an opportunity and a threat, the biggest threat being the fact that quantum computers do threaten encryption. Which is by far one of the most sensitive parts of digital security as it provides privacy to our data, starting from banks to healthcare.

Quantum Computing – Boon or Bane For Modern Technologies?

The standard encryption algorithms that are used in this modern technological era will soon be compromised by quantum computers. It has been surmised that a quantum computer with 4,000 qubits will be able to easily compromise encryption algorithms which are considered to be extremely strong. And, it is been approximated that by 2023 quantum computers with such power will be available, and within a blink of an eye existing cryptography algorithms will no longer be able to secure our data.
Let’s dive in further to see how quantum random number generation works and how quantum computers compromise strong classical encryption algorithms like RSA. RSA, being the standard cryptographic algorithm used on the internet, is a method that is an open secret but, is very hard to crack as it uses two keys for encryption. The public key is open and the client uses that key to encrypt a random session key, the person who intercepts the encrypted key must use the second key which is the private key in order to decrypt it. But, once the session key gets decrypted, the server uses that key to encrypt and decrypt further data with some other faster algorithm. So, in order to have secure communication, the private key must be kept safe.
The idea behind RSA encryption is prime factorization. While multiplying two prime numbers is really easy but a number which is a product of two unknown prime numbers is very hard to factorize. For example, 25980376026529 is a 45 bit cryptographic random number which is a product of two prime numbers 566557 and 45856597. Now, cracking something like this would take at least more than a few months. Based on this aspect, the public key is distributed based on the product of two prime numbers which is used to encrypt the secret message, however, without the knowledge of the prime factors used, the message will not be decrypted or it will be next to impossible to decrypt it.
In 2014, on Amazon EC2 WraithX factorized a 696-bit number, and it is being surmised that a 1024-bit key using the best available classical computer can be factorized within a few months or years. However, the complexity of prime factorization problem grows exponentially with the key length and since we are using 2048-bit keys we are considered safe. But, the curse of prime factorization complexity was solved by an eminent scientist Peter Shor in 1994, who proposed the famous quantum algorithm called Shor’s algorithm. In order to understand how Shor’s algorithm works the idea of the RSA algorithm has to be clearly explained.
At Random Quantum, we bring a revolutionary solution, RQubit that is unbreakable, unpredictable and truly random. It is capable of generating cryptographic random numbers with the ability to truly eliminate the possibility of biasedness, and error containment for complete safety.
The steps of RSA is explained below
This same concept is used in the architecture of security protocols like HTTPS at both client end as well as server end to secure the connection at the transport layer. Now, let’s look into the prime factorization complexity, Using a classical computer, the complexity with which we are able to solve prime factorization is: Here, n represents the number of bits required to represent the product of the prime numbers. But, Shor’s algorithm can do the same work in a complexity of O(n3 log n) using a number of gates O(n2 log n log(log n)). Now, after this let’s understand the working of Shor’s algorithm.
Shor’s algorithm
Shor’s algorithm is a polynomial-time quantum computer algorithm which is used for integer factorization. The efficient nature of Shor’s algorithm is due to the efficient nature of quantum Fourier transform and modular exponentiation by repeated squarings. Shor’s algorithm consists of two parts,
  1. A reduction algorithm which is generally performed on a classical computer, in order to reduce the factoring problem to a order finding problem.
  2. A quantum algorithm to solve the order finding problem.

Reduction algorithm

  • A random number is selected (k < n)
  • gcd(k,n) is calculated using Euclidean algorithm
  • If, gcd(k,n) ≠ 1, then k is a nontrivial factor of n hence stop
  • Else, quantum period finding subroutine is used to find r, where r is the period of the function f(x)=kx mod n
  • If r is odd or kr/2 ≡ -1 mod n, then jump to step i.
  • Else, one of gcd(kr/2+1, n) or gcd(kr/2-1, n) is a nontrivial factor of n hence stop.

Quantum algorithm

  • The registers are initialized to

    Here, the initial state is a superposition of Q states where q independent qubits are generated, each in a superposed state.

  • A quantum function f(x) is constructed which is applied to the above state in order to obtain Uf|x, 0q⟩ = |x, f(x)⟩
  • Inverse quantum Fourier transform is applied to the input register.
  • A measurement is performed which is used to obtain an outcome y in the input register and some outcome z in the output register.
  • Otherwise, jump to step i of this subroutine.
  • Since yr/Q is some arbitrary integer c, so y/Q=c/r. On performing continued fraction expansion on y/Q we get approximations d/s of it which satisfies two conditions:
    • A. s<n
    • B.
    If the conditions are met, the s is either an appropriate period or a factor of r
  • If f(x)=f(x + s) ⇔ ks ≡ 1 mod n, then stop.
  • Else using multiples of s obtain more candidates for r, if any candidate works then stop.
This is how quantum computing provides a way to attack security algorithms like RSA. Shor’s algorithm gives potential threat to modern classical cryptography algorithms. However, since quantum computers are still at a nascent stage so it is difficult to harvest the full potential of Shor’s algorithm, but the day is not far when it will take a few minutes to compromise strong cryptographic algorithms. Fortunately, researchers are working on quantum-resistant cryptography that will be able to resist code-breaking efforts of quantum computers.

References

  1. https://www.americanscientist.org/article/is-quantum-computing-a-cybersecurity-threat
  2. https://medium.com/@jonathan_hui/qc-cracking-rsa-with-shors-algorithm-bc22cb7b7767
  3. Nielsen, Michael A. & Chuang, Isaac L. (2010), Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, .
  4. Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput., 26 (5): 1484–1509, arXiv: quant-ph/9508027v2 , Bibcode: 1999SIAMR..41..303S, doi: 10.1137/S0036144598347011.
  5. Quantum Computing and Shor’s Algorithm , Matthew Hayward’s Quantum Algorithms Page , 2005-02-17, imsa.edu
  6. Shor’s Factoring Algorithm , Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document