A peek into Quantum Computing Vs Cryptography

Abstract — Advancements in computer technologies have brought us into the era of quantum computers. A quantum computer, with its ability to solve exponentially growing problems at a smaller period, has proven that it is a threat to the current cryptography practices. Quantum computers use specially designed methods to break encryption. Nevertheless, quantum-resistant ciphers should be used in the post-quantum world. NIST started research over discovering new quantum-safe algorithms and methods.

Keywords — Qubit, superposition, superexponential, post-quantum, quantum-safe, quantum-resistant, cryptography

I. Introduction

Today’s world relies on information and communication of information. The confidentiality, integrity, and availability of data and data processing machines is of importance. Cryptography is the process of achieving those goals. Since the introduction of quantum computers and their ability to solve math problems that protect cryptographic algorithms pose a threat to cryptographic practices. So, quantum-safe cryptography is required. This paper summarizes what a quantum computer is and how it represents a threat to the current cryptography. Also, it discusses the current approach to obtain quantum-safe cryptography.

II. What is a quantum computer

Anything happening in the physical world abides by the laws of quantum mechanics. So, a normal computer will also follow the laws of quantum mechanics but cannot perform like a quantum computer. A quantum computer achieves the performance by the principle of superposition. In quantum mechanics, an electron in an atom can bounce from one orbit to the other. That means that the electron can be in two states, i.e. disappearing from the current orbit and, at the same time, reappearing at a different orbit. This phenomenon is called superposition.[3]

Fig. 1. Electron disappearing and reappearing in different orbits showing superposition.

A. Normal Computer Execution

Consider an electrical appliance. It can only be in the state of ‘on’ or ‘off’ at a given point of time. A normal computer also executes on the same principle[1]. A computer executes on bits with binary values, either 1 or 0. A bit cannot have the value of both 1 and 0 at the same time. The conditions for a normal computer to perform operations is not very sensitive. Small interferences such as temperature changes, electromagnetic interferences, atmospheric changes do not impact the outcome [1][2].

B. Quantum Computer Execution

The performance achieved by the quantum computer is high since the environment it executes in allows the quantum bits (Qubits) to interact in a state of superposition. A Qubit is different from a normal bit since when in superposition, it can be in the state of 0 and 1 at the same time [4]. For maintaining the superposition of a Qubit, a quantum computer must be maintained at a temperature of absolute zero. It must be in a vacuum chamber since interferences from air molecules introduce errors to the outcomes. No radiations or light rays must be present since they influence the physical nature of the computer [1][4].

III. Quantum computers and Current cryptography

“Cryptography is the science, study, and practice of securing and authenticating people, data, transactions, and other objects between authorized parties.” [5] Popular cryptography practices are encryption and integrity hashing algorithms.

Encryption is the process by which plain text (message) is scrambled into a ciphertext such that only the intended party can unscramble it. Hashing is the process by which a unique code to the input text is generated.

A. Cryptographic algorithm protection

Algorithms used in encryption and hashing are based on trap door functions. “A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the “trapdoor.”” [6] The strength of the cryptographic algorithms depends on the difficulty of the trap door function. Examples of the trap door functions are the integer factorization problem, discrete logarithm problem, and elliptic-curve discrete logarithm problem.

B. Methods and algorithms used by quantum computers to break cryptography

1) Cutting Time

A computer’s ability to perform increases by adding bits to the existing architecture. Protection for the cryptographic algorithms comes from the fact that when provided with more bits to perform operations to break the algorithm, the algorithm should still be able to protect itself by the trap door functionality. The security offered by the trap door function to the algorithms usually takes the exponential form [5]. So, to solve a function that gives exponential times, the amount of work needed is more than exponential times, which can be called ‘superexponential’ time [5]. A quantum computer, due to the superposition of the qubits, can offer superexponential times to solve a problem, and an exponential time problem is vulnerable to this[5].

2) Quantum Algorithms

a) Grover’s algorithm

The Grover’s algorithms proved that for a problem to be solved needing n solutions which are to be tried one at a time can be solved in the square root of n with a quantum computer. Given that the quantum computer offers log(n) + 1 Qubits [5].

Grover’s algorithm can be used to break symmetric encryption and some hash algorithms on a quantum computer. It can also be used to crack some asymmetric algorithms [5]. To keep the encryption and hashing intact, double the symmetric key size and the hash size [5].

b) Shor’s algorithm

The protection of the asymmetric algorithms comes from the fact that the factoring of a given prime number takes much time [5]. So, given a large prime number, C getting the correct set of prime numbers A and B, which satisfy A * B = C, takes a longer time [5].

Shor’s stage 1, the prime focus is on guessing the involved prime numbers. Shor’s algorithm uses a mathematical equation to formulate all the guesses. A quantum computer considers only the most feasible combinations and discards the rest. Stage 2 of the algorithm uses Fourier Transforms to generate waves of each prime number in the guess set and starts combining them in pairs to form a single sine wave. The resulting sine wave with the longest peaks and smallest valleys is the combination we are looking for. This process happens very quickly. It is easy to break the public key encryption with the set of prime numbers [5].

C. Algorithms at Risk[5]

Table 1. Algorithms at risk of breaking by quantum computer.

D. Quantum Resistant Ciphers

The cryptographic algorithms that are not affected by the quantum computer attacks are known as quantum-resistant or quantum-safe or post-quantum ciphers[5]. NIST is researching to obtain quantum-resistant ciphers.

IV. NIST and quantum-safe cryptography

National Institute of Standards and Technology develops and deploys the standards in the United States. In the era of quantum computing and its capability to crack the current cryptographic practices, a new set of standards must be established. NIST, to obtain new quantum-resistant algorithms, has called for the submission of possible algorithms[7]. Each submission was a package that included the algorithms optimized in C language, some test results that can be proven, a detailed explanation of the algorithms and practices, and they required that the algorithm be run on a wide variety of hardware and software[7]. A total of 82 submissions were made, out of which 69 were selected. This was the first round of assessment. Out of the 69 selected algorithms, NIST selected 26 submissions based on the round two evaluation criteria, i.e., security, cost and performance, and algorithm and implementation characteristics[7].

Table 2. NIST is considering these algorithms for standardization as post-quantum cryptography algorithms [7].

V. Conclusion

Practical application and extensive use of quantum computers might take around a decade. By the time standardized quantum-resistant algorithms and practices like quantum key generation and quantum key distribution must be established.

References

[1] N. D. Mermin, Quantum computer science: an introduction. Cambridge, UK: Cambridge University Press, 2007.

[2] Rahul_RoyCheck out this Author’s contributed articles., “Conventional Computing vs Quantum Computing,” GeeksforGeeks, 21-Dec-2018. [Online]. Available: https://www.geeksforgeeks.org/conventional-computing-vs-quantum-computing/. [Accessed: 10-Apr-2020].

[3] Robin.materese@nist.gov, “The Strange World of Quantum Physics,” NIST, 02-Apr-2018. [Online]. Available: https://www.nist.gov/topics/physics/introduction-new-quantum-revolution/strange-world-quantum-physics. [Accessed: 10-Apr-2020].

[4] E. Chris Fisher, “IBM | What is Quantum Computing?”, IBM Quantum, 2020. [Online]. Available: https://www.ibm.com/quantum-computing/learn/what-is-quantum-computing/. [Accessed: 12- Apr- 2020]

[5] R. Grimes, Cryptography Apocalypse : Preparing for the Day When Quantum Computing Breaks Today’s Crypto, 1st ed. Newark: Wiley, 2019.

[6] “Trapdoor function”, En.wikipedia.org, 2020. [Online]. Available: https://en.wikipedia.org/wiki/Trapdoor_function. [Accessed: 12- Apr- 2020]

[7] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, Y. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson and D. Smith-Tone, “Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process”, National Institute of Standards and Technology, 2019 [Online]. Available: https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf. [Accessed: 12- Apr- 2020]