Monday, November 07, 2016

Factoring Quantum Mechanics into Encryption

Recent cyber-attacks have left many people convinced that there is no real way to keep anything secret, at least not anything connected to the grid. You can strengthen your passwords and antivirus protection, but if the systems that send and receive your data are vulnerable, so are you. And the reality is, no one actually knows just how secure our encryption systems are.


Modern society is built on information. In an effort to keep that information safe as technology races forward, scientists are elbow-deep in the field of quantum cryptography. Just like it sounds, this field applies quantum mechanics to cryptography—the science of storing and transmitting information securely.

“Quantum cryptography is a field that promises security based on the laws of physics, as opposed to security based on computational assumptions as it is customary today,” according to Jose Luis Rosales and Vincente Martin from the Universidad Polit├ęcnica de Madrid, authors of a paper due out soon in Physical Review Letters. Their work opens the door to a new direction for quantum cryptography, one that could be capable of breaking current encryption systems and underscores the need for a new approach to encryption.

It’s difficult to put together a puzzle in the dark. Turning on a light gives you a new set of powerful strategies, such as sorting by color, sorting by subject, comparing pieces to the picture on the box, and visually searching for specific shapes. For a 1500-piece puzzle, turning on a light could make a virtually impossible task doable in a day.

Similarly, quantum mechanics gives us a new set of powerful strategies for solving some difficult problems. “The times when entanglement was a weird property of quantum physics, enclosed in the realm of pure physics. . . are long gone. Now we are learning to master the quantum world and have real applications for these weird properties, new sensors, computers and cryptography systems,” say Rosales and Martin.

Strangely enough, revisiting 4th grade math can help put their research on quantum cryptography in context. That’s about the time when kids start factoring numbers, often creating “factoring trees” that help break down large numbers into their prime factors. Remember these?
When you enter your personal information online, the data is encrypted and sent to its destination. The intended receiver has a secret encryption key that is used to decode your message. In most encryption systems, the key is an algorithm based on the prime factors of huge numbers.

Prime numbers occur all throughout the number line, but they seem to pop up randomly. They don’t follow a pattern that we know of, and there is no shortcut to knowing whether a number is prime. If you want to find the prime factors of a large number, you have to factor it piece-by-piece, systematically trying all possible combinations. This gets time consuming very quickly, even for computers. Well-designed algorithms based on large prime numbers are really difficult to break with today’s technology.

The problem is that technology doesn’t stand still. In 1994, mathematician Peter Shor showed theoretically that a quantum computer would give us a new, powerful strategy for finding the prime factors of a large number—making it possible to easily break current encryption systems. At the time, quantum computers were still a long way off, but we are getting ever closer.

Shor’s algorithm, as it’s now called, has been demonstrated experimentally since then and used to find the prime factors of numbers, but only ones as high as 21. That’s much smaller than the numbers used for encryption, of course, but the fact that it works further motivated the development of quantum computers and research on ways to keep information safe in a world where they exist.

Over the last couple of years, Rosales and Martin have developed another quantum-based strategy for factoring numbers that doesn’t require a fully functional quantum computer. First, they redefined the problem. Instead of waiting for a quantum computer that can run Shor’s algorithm, they considered whether it is possible to design and build a physical system that acts like Shor’s algorithm—a kind of quantum simulator.

If you go into a flight simulator at an arcade, you can “fly” a plane without having an actual plane. The computer-based flight game simulates a physical situation (flying). In this case, the researchers were looking for something that did the opposite. From among the realm of theoretical possibilities, they were looking for a quantum physical system that simulates a computer-based action (factoring a large number). And they found one.

Their work outlines a quantum simulator in which the mathematics of factoring is translated into the physics of the system. You can actually extract information on prime factors from information about the system’s energy. It sounds kind of crazy to those of us not immersed in the quantum world, but that’s its power—quantum mechanics offers completely different approaches to solving problems. It’s not clear yet how easy this system would be to build or even if it’s feasible with current technology, but the work shows that the approach is valid and worth exploring.

In addition, the work sheds lights on connections between pure mathematical theory, quantum physics, and prime numbers. How primes are distributed among all numbers is one of the toughest problems in pure mathematics. It is foundational to something called the Riemann hypothesis, a proof of which would win you a million dollars from the Clay Mathematics Institute. Interested? It’s worth taking a look at the quantum approach used here first.

The opportunities are exciting, but this work also carries a warning. It demonstrates a whole new way of factoring prime numbers, begging the question: Are there other ways to factor large numbers that we don’t know about? If so, the technology needed to break our current encryption systems could already exist. All the more reason to push quantum cryptography forward quickly!

Kendra Redmond

No comments:

Post a Comment