Knapsack Code Reworked to Take on Quantum Computing

Knapsack Code

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”?

Quantum Computers

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

Recommended Posts | IT News

 Malware Used by Cyber Thefts

Malware Used By Cyber-Criminals To Attack Airlines

Worrying news has emerged concerning cyber-attacks against energy companies, telecoms firms, government agencies and even airlines. Iranian hackers are accused of a 2 year campaign using malware to target the systems of airlines, hospitals, education facilities, energy companies, defence contractors ...
Net Neutrality

Net Neutrality: What if a Fast Lane Does Scare Investors?

There seems to be a fundamental disgreement between writers at MIT Technology Review and Ars Technica. If the FCC creates a “fast lane” by altering net neutrality rules, some venture capitalists may shy away from funding startups if their businesses will require fast broadband connections ...
Microsoft Windows 10 Unleashed

Microsoft Windows 10 Unleashed

Microsoft is all set to release its most promising and comprehensive operating system Windows 10. With a greater focus on enterprise and desktop/laptop features, this version aims at addressing user interface, start menu and virtual desktop problems encountered in the previous version ...
UK Improved connection speed

UK Businesses All Set to Benefit in Future from Improved Connectivity

Biggest online businesses concerns that connection speed would be top of problems. Most businesses are now online with dedicated websites, but the Web presence is not enough – if customers need to wait a long time for pages to download it may increase the chance of losing business ...