Indistinguishable confusion is realized, and computer scientists have won the “jewel in the crown” of cryptography

iO (Indistinguishability Obfuscation) is the same as black technology in cryptography, but many people think it does not exist. Recently, some researchers have proposed a new iO protocol.

In 2018, Aayush Jain, a PhD student at the University of California, Los Angeles, went to Japan to give a lecture, introducing a powerful encryption tool he and his colleagues were developing. When he stated the team’s efforts in iO, an audience asked: “I don’t think iO exists.”

At that time, this view was more common.If iO does exist, it can not only hide the data collection, but also hide the internal working mechanism of the computer program, To create a powerful encryption tool. Boaz Barak, a professor of computer science at Harvard University, said that this is “the cryptographic primitive that controls everything,” and the power of this power makes people doubt whether iO really exists.

In 2013, computer scientists Sanjam Garg, Amit Sahai and others first proposed the candidate version of iO, and later other researchers figured out ways to attack its security. “Who will win, the makers or the breakers?”

Shafi Goldwasser, head of the Simmons Institute of Computational Theory at the University of California, Berkeley, said: “A lot of people were very enthusiastic about it at the time. They believed in the existence of iO and insisted on research. But then these people are getting fewer and fewer.”

Recently, Aayush Jain collaborated with Huijia Lin, an associate professor at the University of Washington, and Amit Sahai, Jain’s mentor, on a research called the maker platform. This paper, published online on August 18, shows for the first time how to build iO using only “standard” security assumptions.

Link to the paper: https://eprint.iacr.org/2020/1003.pdf

Aayush Jain

All encryption protocols rely on some assumptions. For example, the famous RSA algorithm is based on a generally accepted view: standard computers cannot factorize the product of two large prime numbers. The security of the encryption protocol is related to its assumptions. The previous iO is based on assumptions that have not been tested and eventually proved to be unreliable. The latest protocol relies on security assumptions that have been widely used and researched.

Although this agreement is still far away from actual deployment, it provides a theoretical way to build multiple encryption tools in real time, which was impossible before. For example, it allows the creation of “repudiation” encryption and “function” encryption.

Yuval Ishai, a professor at the Technion-Israel Institute of Technology, said: “No one should doubt the existence of iO now.”

　iO: Cryptography “the jewel in the crown”

For decades, computer scientists have been thinking about whether there is a safe and comprehensive way to achieve obfuscation of computer programs so that people can use them without knowing their internal secrets. Program obfuscation can support a large number of practical applications, such as using obfuscation programs to delegate tasks to others in a bank or e-mail account, without worrying about others abusing the program or reading your account password.

But so far, all attempts to build reality obfuscators have failed. In 2001, bad news also appeared at the theoretical level: the most powerful form of obfuscation “black box obfuscation” was difficult to achieve. (Black box obfuscation means that the attacker cannot understand the inside of the program, but can only see the use and output of the program.) Boaz Barak, Amit Sahai and five other researchers proved that some programs reveal internal secrets by themselves, and they cannot achieve complete obfuscation. .

However, these programs are specifically created to resist confusion and do not have much resemblance to real programs. Therefore, computer scientists hope that there is some other confusion, which is weak enough to be feasible, and strong enough to hide secrets that people really care about. The researcher who proved that black box confusion is impossible proposed a possible alternative in the paper: iO.

At first glance, iO is not a particularly useful concept. It does not require the secret of the program to be hidden, but only requires that the program is sufficiently obfuscated. For example, if you have two different programs that can perform the same task, you cannot distinguish which is the obfuscated version and which is the original.

　　Aayush Jain mentor, UCLA professor Amit Sahai, is also one of the proposers of the iO version candidate.

However, iO is actually much more powerful. For example, suppose you have a program that can perform some tasks related to bank accounts, but it contains unencrypted passwords and is therefore vulnerable to attacks. However, as long as there is a program that performs the same task but can hide the password, the indistinguishable obfuscator can successfully mask the password.

In recent years, computer scientists have proved that iO can be used as the basis of almost all encryption protocols (except for black box obfuscation), including classic encryption tasks (such as public key encryption) and emerging tasks (such as fully homomorphic encryption). It also covers encryption protocols that no one knows how to construct, such as denial encryption and functional encryption.

Cornell University professor Rafael Pass said: “This is the jewel in the crown. Once it is achieved, we can get everything.”

In 2013, Sanjam Garg, Amit Sahai and others proposed a candidate version of iO, dividing a program into multiple “puzzle pieces”, and then using multiple linear mapping to confuse a single “puzzle piece”. After putting all the puzzle pieces together, all confusion cancels each other out, and the program runs as usual, but each individual “puzzle piece” seems meaningless. At that time, this research result was regarded as a major breakthrough and led to a large number of follow-up related papers. However, a few years later, other researchers discovered that multiple linear mappings were not safe. Later, other iO candidate versions appeared, but they were all breached.

At the time, many people worried that iO might just be an unattainable miracle.

less is more

In 2016, Huijia Lin began to study whether the shortcomings of multiple linear mapping can be solved by simply reducing polynomial calculations. Multilinear mapping is essentially an encryption method for polynomial calculations. Jain said: “These mappings are similar to polynomial calculators and are connected to a secret locker containing variable values.” The machine accepts the polynomial input by the user, and the user can view the final locker to see whether the hidden value can make the polynomial value 0.

In order to ensure the security of the program, users should not know the information about other lockers or any numbers generated in the process. Sahai said: “We hope this is true,” but in all the candidate multilinear mappings proposed by the researchers, the process of opening the final locker always reveals the calculation information that should be hidden.

　　Huijia Lin, associate professor at the University of Washington and second author of the study.

The multiple linear mappings proposed by the researchers all have security vulnerabilities. Lin wants to know if there is a way to construct iO without having to calculate so many different kinds of polynomials (so it is easier to construct safely).

Four years ago, Lin discovered a way to construct iO using only certain types of multiple linear mappings, which calculate polynomials with a “degree” of 30 or less (this means that each term is a maximum of 30 variables). Product). In the next few years, Lin, Sahai and other researchers worked on how to reduce the order even lower. Until the third-order multiple linear mapping can be used to construct iO.

In theory, this seems to be a huge improvement. But it still has a problem: from a safety point of view, third-order is actually as bad as any polynomial processing machine.

The only multilinear mapping that researchers understand how to safely construct is a second-order or lower-order polynomial processing machine. Lin, together with Jain and Sahai, tried to find a way to construct iO with second-order multiple linear mapping. They struggled with this problem for a long time.

Although the exploration process was full of hardships, they finally came up with a new idea: Since iO requires a third-order mapping, and computer scientists can only safely construct a second-order mapping, is there a compromise between the two? For example, 2.5-order mapping?

The researchers envisioned a system in which some lockers have clear windows so that users can view the values ​​contained in them. This makes the machine do not need to protect too much hidden information. In order to strike a balance between the ability of high-order multiple linear mapping and the security of second-order mapping, the machine can use polynomials higher than the second order for calculation, but there is a limitation: the polynomials of hidden variables must be second-order. Researchers said they tried not to hide too much information and proved that they can safely build this type of hybrid locker system.

To convert these weaker multiple linear mappings into iO, one last element is needed: a new type of pseudo-random number generator. It can expand a string of random bits into a longer string and still have randomness.

　The final result of this research is the iO protocol that can avoid multiple linear mapping security weaknesses.

The security of this scheme is based on four mathematical assumptions that are widely used in other encryption environments. These assumptions have a long history and the issues related to the assumptions with the shortest research time can be traced back to the 1950s.

There is only one situation that will break the new iO protocol proposed by the study, and that is a full-power quantum computer. One of the four hypotheses is vulnerable to quantum attacks, but some recent studies have provided another potential way to iO, ensuring that it is safe even if it is subjected to quantum attacks, but the assumptions it relies on are not that strong. Some researchers said that in future research, the two methods can be combined to create a version of iO that is based on standard security assumptions and can withstand quantum attacks.

This may attract new researchers to join. When there is theoretical feasibility, then more people will be willing to join the research team. There is no doubt that there is still a lot to do in the field of computer science before the protocol (or its variants) is used in practical applications.