Self-destructing algorithms could usher in a new era of cyber security

Imagine two millionaires, you and your better half, or alternatively two random strangers called Alice and Bob, who want to figure out who’s richer but without revealing their wealth to each other, an insolvable problem? This is the crux of what’s known famously as “Yao’s Millionaire Problem,” and it was devised by the computer scientist Andrew Yao in 1982.

One potential solution to Alice and Bob’s problem is to create what’s known as a “One Time Computer Program.” This program allows Alice and Bob to enter their data privately, performs the calculation once, gives the answer and then destroys itself. This ensures that nobody can access the original data, and equally as important, figure out how it was processed to reverse engineer the answer. It also gives Alice and Bob their answer without compromising their financial details.

However, as interesting as this quirky little game of “Guess who’s richer” might sound it actually has real world implications, and cyber security experts say that one time programs are a hugely important tool in cybersecurity. Or they would be if anybody could build them, because as it turns out so far it’s seemed impossible to build an ideal one time program that runs once and then destroys itself. For example, a classical computer of this kind would have to be physically destroyed to ensure it can’t be used again, and, of course, there is no known way of guaranteeing this.

That said though a quantum computer might seem to offer more potential, since quantum information is easily destroyed and impossible to copy, but, dang it, it turns out that a quantum computer cannot give a deterministic answer to a one off calculation. So the dream of a one time program that destroys itself after a single calculation seems doomed.

Now enter Marie-Christine Roehsner at the University of Vienna and Joshua Kettlewell at the National University of Singapore and a couple of colleagues who not only say they’ve found a way to build a one time program, but have actually managed to build a proof of concept.

The new method relies on a different way of thinking about one time programs performed by quantum computers. Until now, security experts have always expected a definitive solution, such as Bob’s worth is either more or less than Alice’s. But quantum mechanics is an inherently probabilistic process, and that means it can only give the correct answer within certain limits of probability, say 75 percent of the time. As long as Alice and Bob are willing to accept the possibility of an error in the calculation, then it is possible to guarantee that their information will remain secure, and that the program runs once and then destroys itself.

“We relaxed the definition of one time programs to allow some probability of error in the output to show that quantum mechanics offers security advantages over purely classical resources,” said the researchers.

The approach is straightforward. Alice secretly encodes her wealth in the states of a set of qubits stored in a quantum computer. This computer is programmed to compare this number with one entered by Bob and to tell him whether his wealth is greater or less than Alice’s.

This quantum processing is itself an irreversible process, and this prevents Bob from entering other numbers to determine Alice’s wealth. So good so far, but the hardware is fixed and as such a potential weakness of this approach is that Bob can reverse engineer the program by working out how the logic gates are wired.

Roehsner has a trick to prevent this, though. Although they can’t hide the physical wiring, they can hide the truth tables that govern the behaviour of each logic gate.

“This is because our approach is to encode the truth table for individual gates as a one time program in its own right,” said Roehsner.

This allows Alice’s information to be encoded in the precise choice of logic gates and not on the connections between them, and thus it remains hidden from Bob.

Roehsner the team have tested their idea in a proof of concept that encodes information in the polarisation of photons and processes it using various kinds of optical logic gates. The average probability of success for each of the gates is 75 percent, which the team says is in good agreement with the expected value.

The team then used their new set up to solve Yao’s Millionaire problem for numbers consisting of four bits that differ by a single bits, and the program works by comparing each bit to decide which is larger.

The results make for interesting reading. The team says the probability of success increases with the number of bits used for error correction, but this also reduces the security of the system. So there is a clear trade off between accuracy and security. Nevertheless, the team says the security is better than can be achieved with classical computing alone.

“Our results demonstrate that quantum physics allows for better security trade offs for certain secure computing tasks than are possible in the classical world, even when perfect security cannot be achieved,” they said.

What’s more, the method is workable using current technology, and even and relatively modest advances would increase the security of the system even more.

“We believe the presented work strongly hints at a rich area of quantum protocols to enhance the security of classical computation, even before large scale quantum computers can be realised,” added Roehsner, and it’ll be interesting to see how the work is received.

Their paper, “Quantum Advantage for Probabilistic One-Time Programs” was published in arxiv.org/abs/1709.09724.