Almost perfect computer security might be closer than you think

Original author: Kevin Hartnett
  • Transfer
In July 2013, the world of cryptography was thrilled by two scientific papers. They were published with a difference of a few days in the online archive, and together they described a new, powerful method that allows you to hide secrets in computer programs.

The method was called “indistinguishability obfuscation”, or IO. The authors touted it as the “core core” of cryptography — a universal framework on which to reconstruct such well-known tools as public keys and selectively secure signatures. Also, the mathematical apparatus behind IO was demonstrated in the works.

The studies attracted a lot of attention, but over two years of working with them, specialists met with a rather large number of practical difficulties that impede the implementation of IO. For example, IO is too slow. Program obfuscation delays have been measured on modern computers for years. In addition, it turned out that the method is not as mathematically safe as we would like.

But over the past few months, works have appeared that demonstrate very important progress from the time of the initial announcement in 2013. Some researchers believe that a working version of the system can be made in ten years, or even earlier. “Now it looks as if there are no serious limitations,” says Amit Sahai, a programmer at the University of California, co-author of both scientific papers. “IO is a powerful system, and can do everything we need.” In addition, researchers believe that even quantum computers will not be able to crack it.

Mountain of small steps


The IO description begins with an example of two programs that get the same result in different ways. For example, calculating two equivalent functions f (x) = x (a + b) and f (x) = ax + bx. For any set of three variables, a, b and x, the result for both programs will be the same. IO claims that it is possible to encrypt programs in this way so that the user cannot determine which of the two programs is at his disposal.

The 2013 work convinced many that IO can seriously expand the scope of cryptography. But in the works there were no examples of how this possibility can be put into practice. Researchers had two problems - speeding up the process, and making sure that IO is safe enough.

“It may take hundreds of years to obfuscate in this way and then run the program,” says Vinod Vaikuntanathan, a cryptographer at MIT involved in IO work. “And when the results are so funny, you don’t follow the concrete numbers.”

image
Alison Bishop, a Columbia University programmer, demonstrated how to break an IO into a series of small practical steps.

One of the programmers’s approaches to speed up the process is to obfuscate not one large program, but smaller ones related to it. Thus, obfuscation will have to take place in two stages.

The first is the most difficult. Existing IO methods start with the bootstrap of a fairly small program. This program interacts with a large "target" program. The bootstrap program works like a security shell around the input and output of the target program - it obfuscates everything that enters and exits, and as a result, hides the program itself.

But it is still unclear how to obfuscate even a small program. “It's like we're trying to find the first gap in this armor,” Sahai says. “We are stuck on a bootstrap program.”

The second step succumbed to the researchers easier. When the bootstrap program is running, the next task is to obfuscate longer and more varied types of computations. At the annual Symposium on Computational Theory (STOC), three research teams presented papers on how to go from obfuscating any one contour to obfuscating computations of any kind (Turing machine).

This is a big step. To hide the outline, researchers need to know the size of the input and each step of the calculation in advance. Computers are configured to receive any amount of data at the input and do additional calculations as data arrives. The work presented at the symposium showed how to use a special technique called “punctured programming” to obfuscate calculations over a long data set in the form of a series of discrete steps connected to each other.

“The main technical achievement is to apply IO to the contours at the local steps of the calculations, and to tie everything together so that as a result all the calculations are protected,” says Allison Bishop, a programmer at Columbia University.

Mathematically Proven Safety


Increasing the effectiveness of IO is a practical task, and proving the safety of the method is fundamental.

When Sahai and Brent Waters, a University of Texas programmer at Austin, described the use of IO in 2013, all that was left to believe was that this method would keep secrets within the programs. The initial work was like tying a very complex knot - it may look like it is difficult to untie it, but without understanding its structure you cannot be sure that there is no simple method for this.

"At that moment there was only a certain construction - it was not even clear how to prove its safety," says Vaikuntanatan.

image
Brent Waters

Since then, the situation has improved. Any cryptography is based on mathematics that defines the tasks that an attacker must solve in order to crack the code. RSA encryption, for example, uses the product of large integers. To start reading your emails, the attacker needs to identify two large integers, by multiplying which this value was obtained. This task with current computing power is considered impossible.

The mathematical calculations underlying the cryptographic scheme must be strong, as well as simple, well-tested and understandable - so that cryptographers are sure that the task is really as complex as it seems.

“It should be a mathematical problem that we understand. Otherwise, experience shows that it can be hacked, ”Sahai says.

In 2013, there were no practical assumptions about IO security. The following year, IBM researchers released a paper in which IO reduced to a few assumptions related to mathematical objects called “multilinear mappings”. “We showed that if a hacker breaks into IO, he solves one of these problems,” explained Bishop, one of the authors of the work.

Multilinear mappings appeared in cryptography in 2013. Experts have not yet fully studied the question of their reliability. “So far, if you hack into any candidate from multilinear mappings, you won't really shock the public,” says Waters.

Currently, computer scientists are working to replace multilinear displays with something more understandable. The best candidate so far is the concept of "learning with mistakes." She has multilinear mappings with common “ancestors” in an area called “cryptography on gratings,” so there is a chance that a replacement can be made. But so far no one knows how.

Security rush


Despite all the difficulties of IO, experts believe that cryptography based on it is already close. Sahai points out that in cryptography, the path from idea to implementation can take 30 years. And given the progress of the past two years, IO may need less time. “We hope 10-15,” he says.

The main step will be finding a less complex mathematical basis for IO security. Now the best minds in this area believe that work should go at an accelerated pace. Bishop said he “would not argue” that a set of simple mathematical settings would be found within ten years. Vaikuntanatan generally believes that it will take "a couple of years."

Over the past two years there have been serious financial injections into the project. Sahai runs the UCLA Encryption Center and received a $ 5 million grant from the National Science Foundation. DARPA has founded the SafeWare research program, which aims to create effective and universal methods for obfuscating programs.

The rush of developers trying to implement IO shows both the attractiveness of this topic and the need to develop new cryptography methods. The developers of quantum computers are also not asleep, and after their appearance, most cryptographic schemes will be compromised. Except, possibly, IO.

Also popular now: