Another possible solution to an NP-complete problem?

Apr 23, 2014

A couple of days ago a research team comprised of faculty at Nanyang Technological University in Singapore, the University of Southampton in the UK, and IQFR-CSIC in Madrid, Spain published a paper containing a creative solution to a problem known to be NP-complete, namely a version of the traveling salesman problem. The TSP, in summary, postulates a scenario in which you have an arbitrary number of towns spread over a large area and an arbitrary number of paths connecting them. What is the shortest possible path one can take in which the traveler visits each town only once and returns to the point of origin? The answer is not a simple one, and in scenarios larger than a couple of towns (or nodes in a graph) the number of possible combinations rapidly balloons out of control. There are different strategies for finding the optimal path; brute force (trying every possible path) is guaranteed to work but the amount of time required to do so makes it prohibitive past a trivial number of nodes. Try it with a modest sized graph of only twenty towns and you may as well give up unless you want to try a more arcane technique like the Held-Karp or branch-and-bound algorithms. There are techniques to solve the TSP but several of the most feasible are very processor intensive (one required a 110 system cluster, and all of them count their CPU time in the tens of years). So, hamiltonian network problems are nothing to sneeze at.

The research team set up a network of optical fibres and couplers several kilometers in size which represented a set of five towns and the roads connecting them. The length of each optical fibre was precisely calibrated to introduce a unique and measurable delay in the transmission of light through the network. You could think of it like numbering vertices in a graph to identify them. After assembly, the experiment consisted of transmitting pulses of light into the network of optical fibers. As photons are wont to do, when presented with a set of possible paths they follow all of them simultaneously and thus traversed every coupler in the network. Due to the fact that you can add up the delays incurred by each path through the network the researchers successfully predicted when the first pulse would exit the network of optical fibers, which proved by performance that the network was Hamiltonian in nature, and that the most optimal solution had been determined for it. In a cryptographic sense the experiment is an oracle - put a question in, get an answer out that you can then do something useful with (like verify it).

But... why do we care? What's so important about being able to find the shortest path through a network? As I mentioned earlier, Hamiltonian paths are NP-complete, NP meaning "nondeterministic polynomial." Nondeterministic means that every time you try to find a solution you'll probably generate a different one; it may not be the most optimal solution and the specifics of the process might vary from solution to solution, but every possible solution is equally valid. Polynomial stands for polynomial time, or the amount of time an algorithm can take to run to completion when a particular set of inputs are taken into account. Without going into too much detail, the number of steps required to solve polynomial time problems can be estimated with the figure nk, where n is the complexity of the input. Verifying the answers is computationally easy. Actually arriving at the answers, however, is what mathematicians and computer scientists like to call hard. I spent some time trying to come up with a suitably hyperbolic way of expressing what hard means, and I can't think of one that doesn't do more harm than good to the point. Suffice it to say that "forget it" works. These are the sorts of problems that we ordinarily say would take sagans of years to solve by applying the best known available algorithms to them. Contrast this with problems in P (polynomial time), which means that it is relatively computationally easy to find the answers as well as check them.

But what does this mean? There is a theorem (that I don't begin to understand more than the executive summary of) that proves that different kinds of NP-complete problems can be turned into other kinds of NP-complete problems by applying a polynomial-time reduction algorithm. For example, it is possible to convert a degree constrained spanning tree, or a string to string problem into a knapsack problem... If we can find a sufficiently elaborate solution to one kind of NP-complete problem, and it is feasible to turn other kinds of NP-complete problems into the kind of problem we have a clever solution for, then it stands to reason that we have a very good shot at solving the problem that we don't have a direct, clever solution for.

This has some security implications.

I'd like to pull in something that's been fascinating me for a while, something that gave me the notion to write this article called a zero knowledge proof. As the name implies, it is a way to prove that you know a secret without revealing what that secret is. The canonical example of this is a circular cave with a magick door at the farthest point, but there are others that are less well known, such as proving to someone who is color blind that two differently colored balls are, in fact, different colors withouts saying what they are or proving that n people know the same magick number by picking cards out of the same ordered pack with their hands in a bag. The ZKP I keep thinking of involves a Hamiltonian cycle for a very large graph: Say that you and I both know a very large graph called G (we wrote it on a napkin at the club last night and it has a couple of thousand vertices), and I want to prove that I know a Hamiltonian cycle to traverse that graph without giving away the graph. This, incidentally, would prove my identity if you were otherwise unable to recognize me. So, you and I agree to play ten rounds of a game. In each round I make a copy of the graph and change the names of all of the vertices. For the sake of argument instead of numbering them I give them all names of characters from Babylon-5 or Unicode characters and call the resultant graph H. The configuration of the graph doesn't change, just the names. I commit to using H irreversibly somehow (say, you hold a gun to my head). You ask me to either show you the corresponding Hamiltonian cycle through H (I do so, and because it's trivial to test the answer to an NP-complete problem you verify that it's a legit Hamiltonian cycle), or you ask me to show you how to turn the graph G that you already know into the graph H (which I do, because I remember how I renamed the vertices). At no time do either of us give away the specifics of the original Hamiltonian cycle for G. Due to the fact that Hamiltonian cycles are NP-complete, there is a vanishingly small chance that I can successfully lie to you each and every round (for n rounds of the game, the probability of successfully lying each and every time is 1/(2n)), and if you catch me in a lie, you shoot me. You and I might be able to do this ten rounds in a row if we're sufficiently motivated. Computers can do this thousands of times in a row, thus making the probability of an attacker lying successfully vanishingly small, indeed.

So what security related stuff might use zero knowledge proofs? Some authentication systems, for one thing. To prove your identity to a system you have to present an identity (like a username) and a secret that only that user and the system know. Normally we think of passwords when we think about this kind of secret but let's face it, even in 2013 people pick the worst passwords possible. Zero knowledge proofs are used in some authentication systems instead of passwords because they're much more difficult to guess, and at no time does the actual secret pass over the communication channel where an eavesdropper might overhear it. There are some protocols that use ZKPs to enforce correct behavior by all participants (i.e., no funny business) while maintaining a certain amount of privacy over their activities, such as electronic voting schemes (users can cast encrypted votes but the system enforces the condition that users can only vote for recognized candidates). There are digital signature algorithms built around ZKPs, but I'm tired and can't follow the math right now. ZKPs have also been used to build session key exchange systems ala Diffie-Hellman, which are great when you don't trust the communications channel and need to verify that the other party is in fact who you think it is and not an attacker playing monkey-in-the-middle.

Now to bring this back to crypto - AES, RSA, cypher modes, data in flight... scared? But complexity theory is a strange thing. There is some research and some scholarly conjecure that says that you can't actually base crypto algorithms on NP-complete or NP-hard problems even though it's been done in the past. There is also some pretty sound reasoning that says that even if some crypto-related problems are actually in P (meaning that they are supposed to be efficiently solvable in polynomial time) they might not be all that efficiently sovable in the real world. To put it another way, 'efficient' might mean for a particular problem "there is an algorithm to solve this that runs faster than any other algorithm we know that is in P; it'll take fifteen million years instead of forty billion." Efficiency is a parameter of the problem that has to be defined along with everything else, and it may not mean a magick wand that goes "Poof!" and ruins your day. It's also worth noting that there are problems in NP but are not NP-complete or NP-hard which form the basis of relatively robust crypto that we use every day. For example, the integer factorization problem upon which the cryptosystem RSA is constructed, or the discrete log problem upon which Diffie-Hellman key exchange depends. So, even if some NP-complete problems can be creatively solved in a reasonable period of time, it does not mean that we're particularly worse off security-wise than we were before.

It also does not mean that any of the creative solutions will scale. Solving the TSP for five cities required kilometers of optical fibre, lots of fiddly assembly, calibration and testing. Solving for more than five cities... I have no idea what sort of equipment it would take but it's a safe bet that it won't fit on top of your desk. Without having their numbers (or knowledge of optics) I can't even begin to scribble on the back of an envelope. It's one thing to throw hundreds of CPUs at a problem, we've been doing that for years, but when it requires a commodity that requires a certain amount of precision in placement (like optical fibre) and has a certain amount of mass (implying that it'll require a certain amount of space to set up) the game changes. So, while it's definitely worth being cognizant of advances like this the pillars of the sky remain sturdy and static, and you can probably go to bed and sleep soundly tonight.

Special thanks to the beta readers of this article for your time, comments, and criticisms. I really appreciate the help and hope I can return the favor in the future.