Understanding Quantum-Safe Cryptography Through the Knapsack Problem

The easiest example that gives you a taste of the kind of mathematical problems quantum-safe cryptography is based on is the famous knapsack problem. Suppose that you pick 1,000 random numbers of 1,000 digits each and then sum up a random subset of 500 of these numbers and publish the sum together with your original 1,000 numbers. The hard problem is for someone else to figure out which of the 500 numbers you used in the sum.

Interestingly, people tried to use this type of problem for cryptography back in the 1970s, when public-key cryptography was first invented. Unfortunately, they could not figure out how to do it right, and so the schemes that we use today, based on number theory problems, became the standards instead.

This problem actually has many applications outside of cryptography. For the past two decades, the knapsack problem has been one of the prime targets for researchers working on quantum algorithms as well. But there has been virtually no algorithmic progress in the area since the early 1980s. This is why the industry believes that this is a very good problem to use as a base for quantum-safe cryptography.