SF Technotes

Quantum Computing vs. Conventional Cryptography

By Michael Castelluccio
March 28, 2018
0 comments

think_audience

Last week at IBM’s annual conference, Think 2018 (March 20-22, 2018), five interesting research projects were presented in featured sessions called “5 in 5”–“the technologies that will change the world in the next five years.”

 

Curiously, two of the five topics dealt with technologies that today stand at the brink of open conflict, with one of them at risk of annihilation. The two opposing forces are standard cryptography and quantum computing. The former represents a final line of defense against hackers, and the latter a developing computing capacity that will likely reduce conventional crypto to forgotten digital dust. If you try to imagine how that inevitability might alter today’s internet, you probably should begin with the elimination of both personal privacy and any safe commerce as a baseline.

 

IBM, fortunately, has research departments working not only on building new quantum computers, but also on something called “post-quantum cryptography.”

 

QUANTUM COMPUTERS

 

The binary computers that have so thoroughly intruded on our lives today work on complicated operations created by transistors and electronic switches, known as bits, that can be in either on or off states. They only have the two states, 0 or 1, and can only be in one of those states at a given time. Quantum computers, on the other hand, are based on quantum bits, which share a very confusing quality with Schroedinger’s cat-in-a-box thought experiment, where the cat is perceived as alive and deceased at the same time.

 

50Q

IBM 50Q System: An IBM crostata wired for a 50 qubit system

 

This quantum superposition applies to quantum computer bits (qubits), which can be either 1 or 0, or 1 and 0 at the same time. If that isn’t confusing enough, this kind of computer also employs quantum entanglement, which is the physical state created when pairs or groups of particles can’t be described independently of the state of the others in its pair or group, even if they’re a distance apart. The quantum state of the system is the system in its entirety.

 

These principles have been made operational in working quantum computers, but the progress has been slow. IBM, with its 50Q system, has struggled from a few to a 50-qubit system (see image above of the 50Q system). Researchers are realistically expecting 1,000-qubit systems in the next five to ten years with complexity never dreamed of in our current binary environment of 0s and 1s.

 

One of the problems with this kind of computing power is that it could solve in a matter of moments the mathematical problems that currently form the locks on cryptographic messaging.

 

LATTICE-BASED CRYPTOGRAPHY

 

In one of the 5 in 5 presentations, IBM researcher Cecilia Boschini was given about 10 minutes to distill the work her group is doing on a new set of algorithms for cryptography that could withstand the brute-force intelligence of a quantum computer. She began by explaining how we’re protected by cryptography today.

 

boschini

Cecilia Boschini IBM Math Researcher

 

“The security of the systems we use today is based on (math) problems that take ages to solve, even for someone who has access to the most powerful computers existing today. From a theoretical point of view, I would say it’s pretty safe.”

 

She didn’t have time for examples, but consider something as simple as a password you might use for your documents or applications. If you have an app, like Wolfram Password Generator, and you need an eight-character safe name, one click will give you, say, 0txbCi4w. Pretty simple—no special characters, and it doesn’t repeat any of the characters used.

 

For a hacker to launch a brute-force attack on this password, hammering away at trying different combinations of just numbers and letters, it would take, according to Wolfram, about 9.71 years to hack this password if the computer was operating at 100,000 attempts per second. That’s because a full enumeration of all 62.26 trillion possible passwords of this type would take 19.74 years of 100,000 attempts per second.

 

Now that makes conventional passwords and text that might be mathematically scrambled look relatively safe. Not so when facing quantum computing power.

 

Boschini explains the problem. Current cryptography depends on math problems that might take too long for anyone to even bother wasting computer resources on, but they’re solvable. And the bad news is that quantum computers with 1,000-qubit power could solve them in moments, not ages. The current public- and private-key encryption and digital signatures are based on megabyte-size algorithms. (For those who might be interested in the mathematical reason why cryptographers say quantum computers will be able to easily handle this kind of secret coding, do a search for something called Shor’s Algorithm.)

 

What’s needed, then, are quantum-resistant math problems, and Boschini and her research team believe lattice problems will provide the necessary complexity.

 

Lattice-based cryptography uses linear algebra. Boschini asked the attendees to imagine a two-dimensional grid of points. Next, she proposed, “Find the point in the grid that is the closest to a fixed central point in the space called the origin. In a two-dimensional lattice this is simple—you can just draw the grid of points and see the solution.”

 

Then she proposed additional complexity. What if the lattices are in hundreds of dimensions? You can no longer imagine visualizing the location of the origin. The solution of the math problem buried within this kind of matrix, the researchers believe, will provide the start for a post-quantum kind of cryptography.

 

5 IN 5

It seems with each new major development in computer technology, the steps climbed are progressively steeper, and the complexities become even more overwhelming. From bits and bytes, transistors and currents switched on and off, to qubits and quantum states doing computing and saving data with atoms and molecules, the last industrial revolution crawled in its development compared to the last 50 years of the digital revolution. Thank goodness, in this case, at least, the same company that’s building the ultimate hacking tool is simultaneously working on a set of algorithms beyond its reach.

 



Michael Castelluccio has been the Technology Editor for Strategic Finance for 23 years. His SF TECHNOTES blog is in its 20th year. You can contact Mike at mcastelluccio@imanet.org.


0 No Comments