As long as there is sensitive data there is always going to be another person out there who wants to have it which is why it is necessary to make that data readable only to the authorized parties. This is accomplished by utilizing encryption which renders the information useless to anyone without the capabilities to unencrypt the data. The origin of the word “encryption” is from the Greek language derived from the word kryptos meaning hidden and use of encryption can be dated back thousands of years. Around 1900 BC ancient Egyptians would utilize hieroglyphs not normally seen to hide the meaning of a tablet.
Spartans, around 700 BC, would write messages onto a thin leather strip while it was wrapped around a stick (imagine the leather strip being wrapped around a stick in a similar fashion to stripes on a candy cane or barber pole). When the leather strip was received it would be wrapped around a stick of the same diameter and the characters would line up side by side and form the message. With humanity soon entering the quantum age the majority of our current encryption methods will be obsolete. Forcing us to adapt to the computational strength of those quantum computers and make strong methods of encryption for the post-quantum age.
The type of encryption we use today accomplishes the same goal as the methods used by the Egyptians and Spartans but is more complicated. There are two major types – asymmetric and symmetric encryption. Asymmetric encryption, or public-key encryption, utilize private and public keys to encrypt and decrypt data. The public key can be distributed to anyone and is used to encrypt messages that can only be decrypted by the private key which is supposed to be kept secret and not given out to anyone. On the other hand, symmetric encryption uses the same key for encryption and decryption. The two keys being the same it is relatively easy to produce a strong key.
Quantum computing is not a new idea and has been tossed around quite frequently but many people do not actually know how they work. It operates in a vaguely similar fashion to our current computers that use zeros and ones as bits but instead of trying to avoid quantum mechanics the computer is built upon them. The base of a quantum computer is a quantum bit, qubit for short. They are physical particles such as a photon, nucleus, or electron.
Quantum gates take the place of transistors in quantum computers and these quantum gates measure the spin of the qubit by looking at the magnetic field. The two states can either be spin up or spin down comparable to the ones and zeros of current computers. Qubits are in a state called quantum superposition which means the qubit is simultaneously in spin up and spin down.
Another theory is called quantum entanglement which states that the only thing we know about two qubits that are paired together is that they are opposite of each other. When one qubit is measured you know the state of its pair without measuring it. With multiple states, four coefficients are used which show the probability of the state that the configuration is in (up-up/up-down/down-up/down-down). The four coefficients are equivalent to bits in current computers which is where the power in quantum computing comes from. In current computers for two bits you get 2 bits of information, with 2 qubits you get 4 bits of information, with 3 qubits you get 8 bits of information and this curve continues exponentially and can be shown with the equation 2n = X where “n” is the number of qubits in a configuration and “X” is the number of bits you will get out of the configuration.
Quantum computers having all this power make it extremely easy for them to go through huge amounts of data relatively quickly whether that be a simulation of a quantum environment, searching a database, or most important for information security, finding the prime factors of a number. Shor’s Algorithm answers the problem of “given a large integer ‘n’ (typically several hundred digits long), factorize ‘n’ as a product of primes” (Moorhouse). The problem with this is that common encryption such as RSA are built upon the fact that factoring a large number into two large prime factors is very difficult and time consuming for current computers. However, this is not difficult for quantum computers as they have the capability to do complex algorithms in a significantly less amount of time.
Old methods of encryption are slowly being replaced by stronger more modern methods that can resist the computing power of quantum computers giving birth to a new age of post-quantum encryption. One of the new methods to withstand quantum computers is a hash-based public-key signature system. In this system the equation of H(x) = y is utilized. “The signer starts by generating a secret x and then computes y = H(x), the signers secret key has 8b2 bits (b=128), namely 4b independent uniform random strings, each string having 2b bits, the signer then computes the public key as H. To sign a message m the signer generates a uniform random string r, computes the bits, and reveals as a signature of m” (Bernstein). This method is known more commonly as the Lamport-Diffie one-time signature system. If a signer wants to sign more than one message they have to chain the messages together. To accomplish this the signer generates a public key to be placed at the end of a message. The next message sent is decrypted with the public key placed at the end of the previous message. This chaining process can be repeated as many times as necessary.
Code-based public-key encryption built on the McEliece cryptosystem utilizes asymmetric encryption and includes both encryption of data as well as a signature scheme for the sender, made in 1978 by Robert McEliece. It was the first scheme to put randomization into the process of how it encrypts data. Due to that randomization, this system is extremely resistant to attacks using Shor’s algorithm making it a good candidate for the post-quantum age (McEliece). This system utilizes a public key (G) with the equation G = SGsP. The variable S is a random dense nonsingular matrix and P is a random permutation matrix. Gs in the equation is the private key (Wang). This system relies on hidden Goppa code in order to be decrypted. Hidden Goppa code is an algebraic-geometric linear code which is made using an algebraic curve over an infinite field. The reason it is hidden is that the public key is derived from the private key and is disguised in the encryption as a general linear code.
In the need for new encryption multivariate-quadratic public-key signature schemes are a great option for quantum computer resistant signature schemes. These types of encryption are young and similar systems to them have been broken in the past leaving only a few versions that are still used today. Some versions commonly used include Enhanced Tame Triangular System (enTTS), Rainbow, and Unbalanced Oil and Vinegar(UOV). The strength behind this encryption method comes from the multivariate polynomials which mean the polynomials depend on more than one variable to be created. In the UOV scheme variables are grouped into two separate groups and then mixed into a central polynomial.
The unbalanced aspect of this scheme is referring to the relation of the two groups of variables, oil, and vinegar. There is always more vinegar than oil variables. The Rainbow scheme is built on the UOV scheme and layers multiple polynomials developed using the UOV scheme on top of each other dependent on the previous layer. The next layer uses the results from the previous below it to calculate the new polynomial for that layer. This process can be repeated an infinite amount of times, theoretically. Due to the layering aspect of this scheme, the variables can be smaller leading to smaller public and private key which makes it easier to decrypt and verify on part of the sender and receiver using the system (Czypek 8).
Quantum computers incorporate the laws of quantum mechanics into the way they operate so it only makes sense for them to have new quantum encryption along with them. Fortunately for us, it just so happens that the laws of physics include its own form of encryption along with quantum mechanics. The No-Go theorem, which states that a particular situation is not physically possible, includes several sub-theorems: Bell’s theorem, Kochen-Specker theorem, Gleason’s theorem, no-teleportation theorem, no-cloning theorem, no-broadcast theorem, and no-deleting theorem.
Bell’s theorem is the name for a family of results, showing us that it’s impossible for a local realistic interpretation of quantum mechanics (Bell) meaning it’s impossible to have an accurate definition for quantum mechanics since there is a seemingly random aspect of quantum physics. The Kochen-Specker theorem compliments Bell’s by placing limits on types of hidden variable theories used to explain the probabilistic nature of quantum mechanics. It states that it is not possible to add values to physical observables while, at the same time, preserving the functional relations between them (Kochen).
A quantum particle cannot be observed and have a value-added to the quantum particle and still be paired with another particle through quantum entanglement. Gleason’s theorem, in summary, says every quasi-state is already a state and that a quantum state is determined by only knowing the answer to all of the possible yes or no questions (Gleason). These theories together counter the hidden variable theories which attempt to explain the randomness of quantum mechanics as a deterministic model featuring hidden states, saying that all observables defined for a quantum system have definite values at all times.
The no-cloning, no-delete, no-teleportation and no-broadcast theorem group explain why quantum information is so secure and how it incorporates encryption like the system just from the nature of quantum mechanics themselves. The no-cloning theorem says that it is impossible to make a copy of an unknown quantum state. A quantum system can be entangled with only one quantum system and, with the definition of entanglement being the only thing we know about paired qubits is that they are opposite, the paired systems are not clones. The reverse of the no-cloning theorem is the no-delete theorem which states that given an entangled quantum state it is impossible to delete one of the copies. The no-teleportation theorem explains that a quantum state cannot be converted into classical bits, ones, and zeros.
This relates to the Kochen-Specker theorem which says it is impossible to add values to physical observables meaning that even with an infinite number of classical bits you could not fully describe the state of a quantum system. The no-broadcast theorem branches off of the no-cloning theorem. Quantum information cannot be copied so there cannot be more than two recipients, both sides of the entangled system, for there to be more than two sides that mean the information has to be copied in some way. Quantum mechanics having these theorems make for a very safe and efficient type of encryption. It also makes it possible to detect eavesdropping easily because if a quantum state is observed then it changes that very data, which would alert both sides that someone has tampered with the quantum information.
Quantum key distribution, which makes use of all the theorems above, is the only encryption system provably secure by the laws of physics. It uses quantum mechanics to produce a shared random secret key which is only known to each party. The randomly generated quantum key is sent through a fiber optic line as a photon. Information, previously encrypted with that key, is sent over the internet to the intended recipient and the only way to encrypt that data is with the quantum key sent across the fiber line. If information through the internet is copied it is not possible to decrypt it because a man in the middle cannot recreate the quantum state of the private key. If the private key is observed through a man in the middle attack on the fiber optic line it changes since it was observed and once it ends up at its intended destination the receiver of the private key can see that it was observed due to the quantum state has changed. There is a physical limitation to this system, fiber optic lines for quantum key distribution have a maximum length of 60 miles. For this to work successfully, trusted quantum key distributors must be set up every 60 miles in a web shape to cover a wide area.
The quantum age is rapidly approaching making it necessary to adapt our computers to be able to withstand a brute force attack pushing us to stray away from our current factorization-based encryption and adopt new methods like hidden Goppa code, random strings, and multilayered polynomial schemes. The development of current quantum computers, spearheaded by the company D-Wave who is backed by major companies such as Google, Lockheed Martin, and NASA, has passed the “is it possible?” stage and is now moving into the “is it scalable?” stage. The largest current quantum computer is the D-Wave 2000Q which contains 2000 qubits. This computer-based on the equation of transferring quantum bits into classical bits (2n = X) and using 2000 for “n,” shows that “X” is essentially an infinite number of bits. Due to this, the future of information security is progressing in the direction of quantum key distribution as it is the only encryption scheme provably secure by the laws of physics.