What is Quantum Cryptography? Solving Quantum Cryptography
It is said that quantum computers will threaten the security of our digital civilization because they can easily overcome the encryption method that underpins almost all of it every email, every online purchase, every login is secured by the fact that it's a lot harder to factor out prime numbers than it is to multiply them together. Large products of prime numbers make encryption locks and the prime numbers go into them become the keys to the secrets in your inbox. Your secrets are safe for now because the most powerful classical conputers will take thousand of billions of years to find those factors depending on the key size.
But in 1994 a mathematician named Peter Shor developed an algorithm called Shor's Algorithm that could use a quantum computer to factor a prime number in a human lifetime or a human lunch break.
Quantum computers didn't exist in 1994 but just last years Google's quantum computer Sycamore, outsped best classical conputers for a very specific task. According to the researchers
Sycamore performed calculations to simulate another quantum system exponentially faster than would have been possible with a pure classical conputer.
We will talk about exactly what happened here in next article but what does this mean for internet cryptography? Is it game over? Not quite, quantum computers need to become far more reliable and have better fault-tolerance and/or support more vastly quite-a-bit to do the sort of prime factoring required for decryption. But those computers will eventually arrive. So, what's to be done? One option is to match quantum decryption with new quantum encryption to replace prime factoring. To distribute a quantum key, you also need a quantum internet to transfer quantum states. This is a far more challenging problem. Quantum states are insanely fragile and difficult to transport, and the quantum internet may not arrive before better quantum computers can encrypt current techniques and collapse the modern digital world. Fortunately there is another option and it will be much cheaper than building a quantum internet. It turns out there are some ingenious non-quantum ways to thwart the hacking powers of quantum computers. Enter post-quantum cryptography, or quantum resistance algorithms, which might replace our vulnerable prime-factoring based cryptography. To understand why some algorithms are vulnerable to quantum computing attacks while others are thought to be quantum resistance we need to review a bit about encryption. Prime factoring is an an example of what we call a one-way function. That's a mathematical operation that is very easy to figure out in one direction, bit very difficult to reverse.
The current encryption protocol uses prime factors and this is a RSA protocol named after Ron Rivest, Shamir and Leonard Adleman who came withit in 1977. It works greatly except its vulnerability to Shor's Algorithm and quantum computers. But prime factoring is only one example of a one-way function.
Ron Rivest, Shamir and Leonard Adleman
Are there other possibilities that don't have the same vulnerability? To understand that, we meed brief description of how quantum computers di their magic. If you try prime factorisation using a classical computer you
're stuck using an algorithm similar to one that was developed 2000 years ago by the Greek mathematician Eratosthenes. First, divide a number by 2 and see if you get an integer. If not, try 3, 5, 7, 11, 13 and so on. This is laborious as it takes much time to factor large numbers this way. Or you can run insane numbers of computers in parallel to each check every different factor. Still effectively impossible, however, Shor's Algorithm is potentially exponentially faster. There is a structure to factorisation that can be exploited by quantum computers and that structure is a period. For eg., let's consider powers of 2 such as2,4,8,16,32,64,128,256,512,1024 and so on such that if we divide these powers by 5 and look at the remainder ( an operation called mod ). It turns out that if you cam figure out the period of this sequence you can figure out the original number ( in this case is 2 ). The 18th century mathematician Leonhard Euler figured this structure to numbers that are the multiple of two prime numbers-just like RSA numbers. For a very large number you need an insane period of time or in parallel you need insane number of classical computers. This is where quantum computers wiered in. Classical conputers store the data in bits or bytes i.e.0 or 1. However, quantum computers store data in qubits, which, until they give output are in a quantum superposition of 0 and 1, with some probablity of either being measured when you try read out the qubit. So a set of qubits can be in any one of a large possible states, and each state represent a different number, each with a different probability. You can think of Each state being like a parallel processor, but now instead of processing across different computers you are processing in different states of quantum wave function or in different parallel realities if you are into the Many World interpretation of Quantum mechanics. The problem with this parallel processing is that you get only one answer when you try to read out the qubits. If you tried to use a quantum computer to guess the prime number you 'd read out one of these guesses but it's not more likely to be correct one than if you used a classical computer. But it turns out there is a way to boost the chances of getting the right answer. Instead of trying to hold possible prime factors in qubits, our array of qubits hold these repeating moduli of Shor's Algorithm-one per quantum state in the superposition. But now the entire superposition - all elements of the wave function are related by the period of their repetition. Essentially, you cause those part of the wave function to destructively interfere leaving the correct period boosted. Once you read out that period you can determine the prime-factors. Sofar, quantum computers are stuck under 100 qubits and non have managed to factora number higher than 21 with Shor's Algorithm. At any rate, quantum technology isn't there yet, when we figure out how to build Quantum computers with thousands of qubits even the very high digit RSA will not be safe.
So, how do we fix the problem?
The answer is to find one-way functions that don't have a known exploitable quality like the periodicity of prime factoring. That's the goal of a currently being run by NIST (National Institute for Standards & Technology). Algorithm applicants have been whittled down from a field of 70 to only 7 finalists and a couple of alternates which were announced in June. In 2022, NIST is expected to narrow it down to one or two quantum resistance algorithms. These will become the new standards for public key encryption and digital signatures- and they will hopefully be able to protect our data from quantum computing attacks. One of the NIST finalists achieves that through the McEliece cryptosystem, which gets its name from cryptographer Robert McEliece, who developed the hard math problem back in the 1970s .The principle behind McEliece is that it's really difficult to repair errors in large messages. That gives us the potential for one-way function. But decoding errors is much-much harder as the codeword size increases, unless you know something about the codeword ahead of time. In the above mentioned cryptosystem, the key is to modify the messages in a reversible way to create a very large codeword-then add errors to that codeword. Unless you know how the modification was done in the first place, it is essentially impossible to remove the added errors. McEliece does this by coding messages into large matrices. You have a big array of numbers , a Matrix , and you scramble it using key matrices and code your messages into the result. Then you add some errors. If someone understand the keys-the matrices used to do that scramble in the first place, they can pretty easily eliminate the errors and canfind the message easily that makes the sense. But without the keys it is near impossible to decode the errors from this gigantic matrix, and the presence of errors makes it impossible to brite force one-way function in the backward direction. McEliece avoids the periodicity that makes RSA vulnerable to Shor's Algorithm. Computing in parallel universe is just not helpful here. But there is a reason we have not been using McEliece:the public key - this giant matrix is very big. To be secure against quantum attacks for the foreseeable future, McEliece would need an 8Mb public key-8000 times larger. Right now network protocols aren't built for this and it could cause dramatic slowdowns in transactions. This problem is shared by at least one of the three public key encryption finalists-NTRU, CRYSTALS-KYBER and SABER, which are lattice based cryptosystems.
These type of cryptosystems rely on the difficulty of problems like the shortest vector problem. Unfortunately, those large lattices are why the lattice candidates have also large public keys. Perhaps, a bigger issue than the size of the public keys is the question is whether these algorithms are really robust against quantum and classical
attacks. Well, one important factor in this question is the age of the algorithm. The line of thought is basically this: the longer a cryptosystem has beeen around, the longer has someone has had to break it. If they have not, then this is a good sign. People have more confident in a 40-year old McEliece algorithm than recently created lattice based algorithm. So, will post-quantum cryptography save digital civilization? It's hard to say. It's true that these quantum resistance algorithms seems like they will be hard, if not impossible for quantum computers to crack, but that doesn't mean no k
one will come up with a way to do it. Infact, there is no guarantee a classical computer would not come up with a fast algorithm to solve them. Mathematicians and cryptographes have decades of security to point to as proof of their encrypting and decrypting abilities. But at the end of the day, quantum key distribution proponents would rather put their faith in fundamental laws of physics-pretty darn secure if only we had a quantum internet. In the meantime, post-quantum crypto may be our hope as black hat quantum hackers attempt to decrypt your embarassing email across the parallel quantum space time.
Thank you.
If you liked our article then please like, share and comment.
0 comments:
Post a Comment