Knapsack Code Reworked to Take on Quantum Computing
Creating an online defense system better equipped for future threats, mathematicians from Washington State University (WSU) have developed an encryption code that will be able to fend off the extraordinary hacking capabilities of a quantum computer. The project recently featured in The Fibonacci Quarterly journal and is considered to be relieving news by those who acknowledge how the inevitable arrival of quantum computers could render the defenses of silicon-based computers obsolete.
According to the journal, an old and well-recognized but essentially flawed cipher – the knapsack code – was reconfigured with the use of cryptography and high-level number theory. The WSU researchers were successful in reworking the code and brought it up to quantum level.
Nathan Hamlin, instructor and director of the Math Learning Center at WSU, along with former math professor William Webb began by constructing a new number system for the knapsack code in hopes of making it worthy of being used as a new sort of public encryption key and to set it at quantum standard. The numbers were represented using different methods which, in effect, successfully produced a digital system far more complex than conventional systems. The two researchers believe that their reworked version of the code could work as an effective defense at quantum computing level.
The knapsack code
The knapsack code first grew relevant in the seventies where it functioned very effectively as tool for public key encryption, but it was later broken by two other codes and lost its relevance as a result. It's actually based on a theoretical problem (the knapsack problem) which dates back to the late 19th century. Basically, the problem works like this: if you have one large number (the knapsack) and lots of small numbers (objects), what is the subset of “objects” that will perfectly fill “the knapsack”?
Many tech companies, including Google, are in the race to develop quantum computers. Theoretically, they would offer processing power that is billions of times faster than the most efficient silicon-based computer available today. This means they could breach current security codes – which protect exchanges by relying on public key encryption – with very little difficulty and could make light work for internet exchanges ranging from online purchases to simple emails.
Public key code operates on the basis of factoring incredibly large numbers. It basically uses a single public key for encryption and another for decryption. The system has worked exceptionally well at keeping hackers at bay. However, quantum computers could factor such large numbers in a matter of seconds, and problems like the knapsack code slow them down.
So even though quantum computers aren't a reality just yet, they soon will be, and it is important for us to start working on defenses and remedies in order to protect online information.
The researchers report that their effort to revive the knapsack code to its former glory was a challenging intellectual exercise. “We wondered if it could be fixed and redesigned to be secure,” they said. And although the reworked code still requires a field test, it promises to be great protection for future online exchanges.
Image: Flickr's Creative Commons