Jan 12, 2020
Cryptography in the Quantum World
Cryptography is a vital part of network security. It is the art of coding information to hide the true meaning of the data. Cryptanalysis is the art of decoding the information. There are several popular encryption algorithms in use today, however the development of quantum code breakers may threaten their usefulness because the computers of the future may be all powerful by today’s standards. Therefore, there is no guarantee that current encryption techniques will still be viable in a post-quantum world.
Claude Shannon is known as the “father of modern cryptography.” He was an established scientist known for electronic communications and digital computing. He developed the idea of a unique shared secret or key, which was the first symmetric-key created in 1949. It was the only method of secure communication until 1976. (Elbirt, 2009)
In 1976, the Data Encryption Standard (DES), was created by IBM. DES is a symmetric key architecture and was designed for the government to protect information that was not classified, but still sensitive. It was eventually retired in 1998 because it was designed weakly, and powerful computers had cracked it.
The same year, 1976, Whitfield Diffie and Martin Hellman developed the first asymmetric-key which was called the “Diffie-Hellman” algorithm. It was the first public key cryptographic system. Asymmetric key systems use one public key that is freely given, and one private key that is kept secret. By contrast, remember that symmetric keys use a shared key, rather than two separate keys. (Hershey, 2003)
The Diffie-Hellman architecture relies on discrete logarithms to be secure. These discrete logarithms are easier to make than they are to break, that is why they can be used quickly and effectively. (Easttom 2018)
In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman published the RSA algorithm. It is a very important standard and a lot of financial industries rely on it. There is one big problem with the algorithm. It is possible that plaintext can be tested for by attempting to encrypt it. If the encrypted plaintext is the same as the ciphertext, then the plain text portion becomes obvious. RSA is secure because it is a very difficult factoring problem due to the math involved. However, with a powerful enough computer, this can be broken. (Hershey, 2003)
The Advanced Encryption Standard (AES) was published in 1998 replaced the Data Encryption Standard. It was published by Vincent Rijmen, Joan Daemen. AES can support 128, 192, and 256-bit block ciphers. This standard is very secure and remains popular today. (Elbirt, 2009)
Today’s cryptography is a mixture of symmetric-key and public-key algorithms for speed and security. A lot of services will use public-key encryption for establishing a session, and then switch to symmetric key for speed. Cryptography gives users confidentiality, data integrity, authentication, non-repudiation (denial of transmit), and access control. Without it, the world would lose major functions of finance, military, and healthcare. It is difficult to imagine losing the ability to communicate securely. (Elbirt, 2009)
There are three main directions of cryptanalysis or decoding a cryptographic system. Analysts can improve their hardware. Stronger computers that have faster processors or bigger memory can crack codes faster. Mathematicians can improve their algorithms. There are mathematicians working on algorithms all around the world because better algorithms can break cryptographic algorithms faster. And finally, cryptanalysis can use advances in computer architecture. It is like computer hardware, but primarily means the logical speed is increased.
Most public key infrastructure relies on factoring. For example: the factors of 12 are 1x12, 2x6, and 3x4. Cryptography relies on factors of enormous numbers. For example: in 1975, Morrison and Brillhart factored 2¹²⁸ + 1 into two prime numbers. One factor was 17 digits long, the other was 22 digits long. In 1981, 2²⁵⁶ + 1 was factored. In 1994, a 129-digit number was factored.
These discoveries were due to faster computers, multiprocessing, and powerful mathematical algorithms. Quantum computers are the next step forward in computing. Coupled with more advanced mathematics, and even multi-processor quantum computers, factoring numberings can be done at a speed that has not been though possible. The continuing development of quantum computers means that computers can decrypt keys exponentially faster. (Hershey, 2003)
Key delivery can also be more secure due to relying on quantum physics. Describing quantum physics is far beyond the scope of this essay, but in short it relies upon taking advantage of the unique property of light to be both a wave and a particle. It also relies on variations of the Heisenberg uncertainty principle, that the existence of certain properties randomizes the values of other properties. In other words, quantum cryptography uses polarized photons of light to transfer randomized keying material in a secure manner.
One practical use for this came in 1999, where scientists applied for a patent for quantum delivery of data from low-orbit satellites. This is very secure and can replace traditional radio frequency transmissions because satellite transmissions are increasingly susceptible to eavesdropping. (Hershey, 2003)
The quantum key distribution (QKD) uses quantum entanglement between two particles to send bits of data. These bits are the keys for ciphers, and they are very hard to intercept and even more difficult to interpret for outside forces. (Easttom, 2018)
One other tool for cryptanalysis is Shor’s algorithm. Invented in 1994 by Peter Shor, his algorithm can be performed on a quantum computer to trivialize difficult math problems. In very simple terms, Shor’s algorithm solves the problem: Given an integer N, find its prime factors. There are also applications for discrete logarithms, and special elliptic curves (Elliptic Curve Cryptography Diffie-Hellman (ECC-DH)) for cryptography.
Shor’s algorithm has the potential to break RSA and Diffie-Hellman public-key cryptography because it can increase the speed of the mathematics involved. (Eastom, 2018) Shor’s algorithm, and other post-quantum algorithms could potentially break modern encryption standards.
There are some cryptographic standards that are resistant to Shor’s algorithm such as hash-based cryptography, multivariate public key cryptography, and lattice-based cryptography. The AES standard, is a lattice-based problem that is resistant to quantum computing because it is based on ‘worst-case problems.’ These worst-case problems are just, incredibly difficult problems. Normal cryptography like RSA is just ‘average’ difficulty. Thus, the answer for quantum cryptanalysis could be using just more difficult math. (Easttom, 2018)
The history of cryptography is very interesting and very recent. Methods that were once thought of as secure could become in danger due to the speed of quantum computing. Some methods of traditional cryptography like lattice-based cryptography, may be resistant to quantum computer simply by virtue of their difficulty in solving. Whatever happens in the future, quantum computers will be deciding the future of cryptography.
References:
Elbirt, A. (2009). Understanding and applying cryptography and data security . Boca Raton, Florida: CRC Press.
Easttom, W., Darraj, E., Butler, W., & Pittman, J. (2018). A Comparative Study of Lattice Based Algorithms for Post Quantum Computing (ProQuest Dissertations Publishing). Retrieved from http://search.proquest.com/docview/2285152349/
Hershey, J. (2003). Cryptography demystified. New York: McGraw-Hill.
Jordan, S., & Liu, Y. (2018). Quantum Cryptanalysis: Shor, Grover, and Beyond. IEEE Security & Privacy, 16(5), 14–21. https://doi.org/10.1109/MSP.2018.3761719
