Almost perfect computer security may be closer than you think.
In July 2013, two scientific papers were thrilled by the world of cryptography. They were published with a difference of several days in an online archive, and together they described a new, powerful method for hiding secrets in computer programs.
The method was called “obfuscation of indistinguishability” [indistinguishability obfuscation], or IO. The authors advertised it as the “core” of cryptography — a universal framework on which to reconstruct such well-known tools as public keys and selectively secure signatures. Also in the works demonstrated the mathematical apparatus behind the IO.
Research has attracted a lot of attention, but for two years of working with them, the specialists met with quite a lot of practical difficulties preventing the implementation of IO. For example, IO is too slow. Delays in obfuscation of programs are measured on modern computers for years. In addition, it turned out that the method is not as safe mathematically as one would like.
')
But over the past few months, works have appeared that demonstrate very important advances since the initial announcement of 2013. Some researchers believe that the working version of the system can be done in ten years, or even earlier. “Now it looks like there are no serious limitations,” said Amit Sahay, a programmer at the University of California, co-author of both scientific papers. “IO is a powerful system, and it can do everything we need.” In addition, researchers believe that even quantum computers will not be able to hack it.
Description IO 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 of both programs will be the same. IO claims that it is possible to encrypt programs in such a way that the user cannot determine which of the two programs is at his disposal.
The works of 2013 convinced many that IO can seriously expand the scope of cryptography. But in the works there were no examples of how this possibility could be applied in practice. The researchers had two problems - to speed up the process, and make sure that the IO is safe enough.
“It may take hundreds of years to obfuscate in this way, and then start the program,” says Vinod Vaikuntanathan, an MIT cryptographer involved in IO work. “And when the results are so ridiculous, you don’t follow specific numbers.”
Alison Bishop, programmer at Columbia University, demonstrated how to break IO into a sequence of small practical steps.
One of the approaches chosen by programmers to speed up the process is to obfuscate not one large program, but the smaller ones associated with it. Thus obfuscation will have to take place in two stages.
The first is the most difficult. Existing IO methods start with bootstrapping 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 obfusts everything that comes in and out, and as a result, hides the program itself.
But it is not yet clear how to obfuscate even a small program. “It’s like we’re trying to find the first slot in this armor,” says Sahai. “We are stuck on the bootstrap program.”
The second step gave way to researchers easier. When the bootstrap program is running, the next task is obfuscation of longer and more varied types of calculations. At the annual Symposium on Computation Theory (STOC), three teams of researchers presented papers on how to go from obfuscating any one contour to obfuscating calculations of an arbitrary type (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 calculations in advance. Computers are set up to receive any amount of input data 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 related to each other.
“The main technical achievement is to apply IO to the contours at local computing steps, and link everything together so that all the calculations are protected as a result,” said Allison Bishop, a programmer at Columbia University.
Increasing the efficiency of IO is a practical task, and the proof of the safety of the method is fundamental.
When Sahai and Brent Waters [Brent Waters], a programmer at the University of Texas, Austin, described using IO in 2013, it remained only to believe that this method would keep secrets inside programs. The initial work was similar to tying up a very complex knot - it may look like it is difficult to untie it, but without understanding its structure one cannot be sure that there is no simple method for this.
"At that moment there was only a certain construction - it wasn’t even clear how to prove its safety," says Vaikuntanathan.
Brent waters
Since then, the situation has become better. Any cryptography is based on mathematics, defining the tasks that an attacker must solve to break a code. RSA encryption, for example, uses the product of large integers. To start reading your emails, an attacker needs to determine two large integers, by multiplying which this value was obtained. This task at current computing power is considered impossible.
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 difficult as it seems.
“This should be a clear mathematical problem. Otherwise, as experience shows, it can be hacked, ”says Sahai.
In 2013, there were no practical assumptions about the safety of IO. The following year, researchers at IBM released a paper in which IO is reduced to several assumptions related to mathematical objects called "multilinear mappings." “We have shown that if a hacker hacks IO, he solves one of these problems,” explained Bishop, one of the authors of the paper.
Multilinear mappings appeared in cryptography in 2013. Experts have not yet fully studied the issue of their reliability. “So far, if you hack any candidate from the multilinear mappings, you are not much shocked by the public,” says Waters.
Currently, computer scientists are working to replace the multilinear mappings with something more understandable. The best candidate is still considered the concept of “learning with mistakes.” With multilinear mappings, it has common “ancestors” in an area called “cryptography on grids,” so there is a chance that the replacement can be made. But so far no one knows how.
Despite all the difficulties of IO, experts believe that its cryptography is already close. Sahay indicates that in cryptography, the path from idea to implementation can take 30 years. And taking into account the progress of the last two years, IO may need less time. "We hope it is 10-15," he says.
The main step will be the find of 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 that he “would not argue” with the fact that a set of simple mathematical installations would be found within ten years. Vaikuntanathan generally believes that it will take a couple of years.
Over the past two years there have been serious financial injections into the project. Sahay runs the Encryption Center at UCLA and received a grant of $ 5 million from the National Science Foundation. Agency DARPA has founded SafeWare's research program, whose goal is to create effective and universal methods of obfuscation programs.
The rush of developers trying to implement IO says both the attractiveness of this topic and the need to develop new cryptography methods. Developers of quantum computers are also not asleep, and after they appear, most cryptographic schemes will be compromised. Except, perhaps, IO.
The method was called “obfuscation of indistinguishability” [indistinguishability obfuscation], or IO. The authors advertised it as the “core” of cryptography — a universal framework on which to reconstruct such well-known tools as public keys and selectively secure signatures. Also in the works demonstrated the mathematical apparatus behind the IO.
Research has attracted a lot of attention, but for two years of working with them, the specialists met with quite a lot of practical difficulties preventing the implementation of IO. For example, IO is too slow. Delays in obfuscation of programs are measured on modern computers for years. In addition, it turned out that the method is not as safe mathematically as one would like.
')
But over the past few months, works have appeared that demonstrate very important advances since the initial announcement of 2013. Some researchers believe that the working version of the system can be done in ten years, or even earlier. “Now it looks like there are no serious limitations,” said Amit Sahay, a programmer at the University of California, co-author of both scientific papers. “IO is a powerful system, and it can do everything we need.” In addition, researchers believe that even quantum computers will not be able to hack it.
A mountain of small steps
Description IO 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 of both programs will be the same. IO claims that it is possible to encrypt programs in such a way that the user cannot determine which of the two programs is at his disposal.
The works of 2013 convinced many that IO can seriously expand the scope of cryptography. But in the works there were no examples of how this possibility could be applied in practice. The researchers had two problems - to speed up the process, and make sure that the IO is safe enough.
“It may take hundreds of years to obfuscate in this way, and then start the program,” says Vinod Vaikuntanathan, an MIT cryptographer involved in IO work. “And when the results are so ridiculous, you don’t follow specific numbers.”
Alison Bishop, programmer at Columbia University, demonstrated how to break IO into a sequence of small practical steps.
One of the approaches chosen by programmers to speed up the process is to obfuscate not one large program, but the smaller ones associated with it. Thus obfuscation will have to take place in two stages.
The first is the most difficult. Existing IO methods start with bootstrapping 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 obfusts everything that comes in and out, and as a result, hides the program itself.
But it is not yet clear how to obfuscate even a small program. “It’s like we’re trying to find the first slot in this armor,” says Sahai. “We are stuck on the bootstrap program.”
The second step gave way to researchers easier. When the bootstrap program is running, the next task is obfuscation of longer and more varied types of calculations. At the annual Symposium on Computation Theory (STOC), three teams of researchers presented papers on how to go from obfuscating any one contour to obfuscating calculations of an arbitrary type (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 calculations in advance. Computers are set up to receive any amount of input data 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 related to each other.
“The main technical achievement is to apply IO to the contours at local computing steps, and link everything together so that all the calculations are protected as a result,” said Allison Bishop, a programmer at Columbia University.
Mathematically proven safety
Increasing the efficiency of IO is a practical task, and the proof of the safety of the method is fundamental.
When Sahai and Brent Waters [Brent Waters], a programmer at the University of Texas, Austin, described using IO in 2013, it remained only to believe that this method would keep secrets inside programs. The initial work was similar to tying up a very complex knot - it may look like it is difficult to untie it, but without understanding its structure one cannot be sure that there is no simple method for this.
"At that moment there was only a certain construction - it wasn’t even clear how to prove its safety," says Vaikuntanathan.
Brent waters
Since then, the situation has become better. Any cryptography is based on mathematics, defining the tasks that an attacker must solve to break a code. RSA encryption, for example, uses the product of large integers. To start reading your emails, an attacker needs to determine two large integers, by multiplying which this value was obtained. This task at current computing power is considered impossible.
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 difficult as it seems.
“This should be a clear mathematical problem. Otherwise, as experience shows, it can be hacked, ”says Sahai.
In 2013, there were no practical assumptions about the safety of IO. The following year, researchers at IBM released a paper in which IO is reduced to several assumptions related to mathematical objects called "multilinear mappings." “We have shown that if a hacker hacks IO, he solves one of these problems,” explained Bishop, one of the authors of the paper.
Multilinear mappings appeared in cryptography in 2013. Experts have not yet fully studied the issue of their reliability. “So far, if you hack any candidate from the multilinear mappings, you are not much shocked by the public,” says Waters.
Currently, computer scientists are working to replace the multilinear mappings with something more understandable. The best candidate is still considered the concept of “learning with mistakes.” With multilinear mappings, it has common “ancestors” in an area called “cryptography on grids,” so there is a chance that the replacement can be made. But so far no one knows how.
Security rush
Despite all the difficulties of IO, experts believe that its cryptography is already close. Sahay indicates that in cryptography, the path from idea to implementation can take 30 years. And taking into account the progress of the last two years, IO may need less time. "We hope it is 10-15," he says.
The main step will be the find of 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 that he “would not argue” with the fact that a set of simple mathematical installations would be found within ten years. Vaikuntanathan generally believes that it will take a couple of years.
Over the past two years there have been serious financial injections into the project. Sahay runs the Encryption Center at UCLA and received a grant of $ 5 million from the National Science Foundation. Agency DARPA has founded SafeWare's research program, whose goal is to create effective and universal methods of obfuscation programs.
The rush of developers trying to implement IO says both the attractiveness of this topic and the need to develop new cryptography methods. Developers of quantum computers are also not asleep, and after they appear, most cryptographic schemes will be compromised. Except, perhaps, IO.
Source: https://habr.com/ru/post/275247/
All Articles