For decades, computer scientists have sought to verify whether there exists an absolutely secure method to encrypt computer programs, rendering them uncrackable during use.
At the end of 2020, several scholars successfully discovered an encryption method that prevents computer users from cracking programs by obtaining the code.
First, It Must Be Obfuscated
Indistinguishability obfuscation (IO) is a powerful encryption algorithm that can not only hide data sets but also conceal the program itself, thereby enabling nearly all encryption protocols.
To understand what indistinguishability obfuscation is, let’s first look at what obfuscation means.
For programmers, the most valuable asset is naturally the code. Once the source code is obtained by someone, it essentially nullifies the effort spent by the programmer in writing the code and may involve intellectual property disputes. To protect their code, some programmers take measures to obfuscate the program before exporting it.
Currently, there are two methods of program obfuscation. The first method is to replace all keywords in the entire code with numbers (for example, replacing ui_controller with a0123456); the second method is to output the compiled code directly, converting human-readable source code into machine code that computers can understand, making it impossible for others to directly open the file and see the original code.
Both methods aim to remove identifiable symbols when exporting the program, thereby not exposing source code information.
However, these two methods do not truly represent obfuscation because, although humans may find it difficult to understand what this string of code is doing, if such code is placed into a compiler, allowing it to analyze the syntax structure of the programming language, it becomes easy to infer what each line of instruction is intended to do.
True obfuscation is referred to as Virtual Black Box (VBB) obfuscation, which essentially embeds a program C into a black box. We can input x on one end of the black box, and the other end will output C(x). Since the entire program is hidden within the black box, we cannot discern any construction information of C, nor can we reverse-engineer the input from the output.
If we can achieve a virtual black box, users can utilize the program without understanding its inner workings, making it impossible for the developed program to be cracked, and the process of encrypting the program will also be highly efficient.
However, shortly after the concept of the virtual black box was proposed, it was met with skepticism. In 2001, seven researchers collaborated to present a specially constructed program and proved that universal VBB obfuscation is absolutely impossible.
Nevertheless, among the findings of these seven researchers, a new definition of obfuscation was introduced—if two programs A and B have the same functionality, can a new obfuscation algorithm be devised such that a third party cannot distinguish between the two programs? This type of obfuscation is referred to as IO.
The principle it utilizes is: if the same value is input into programs A and B, resulting in O(A)=P and O(B)=P, it is computationally infeasible to determine whether P came from A or B without accessing either program.
With the powerful indistinguishability obfuscation, we can perfectly encrypt existing programs, ensuring they are never cracked.
But Still Vulnerable to Quantum Computing
In 2013, Professor Amit Sahai from UCLA, along with five other scholars, proposed an IO protocol that splits a program into several pieces, much like a puzzle. Each individual piece appears meaningless, but if the pieces are correctly assembled using multilinear pairing methods, the program can function normally.
Multilinear pairing is essentially a method of computation utilizing polynomials, which are mathematical expressions composed of different variables and numbers, such as 3xy + 2yz². To ensure security, users must not be privy to any parameters throughout the process.
Within the multilinear pairing method, an important concept called “degree” can be understood as the order of variables in the operational formula. For example, 3xy + 2yz² is a polynomial of degree 2; 3xy + 2yz⁴ is a polynomial of degree 4. The higher the degree, the poorer the security of the multilinear pairing.
In 2016, Associate Professor Lin Huijia from the University of Washington began exploring whether IO could be achieved by reducing the degree of multilinear pairing. Initially, she figured out how to construct IO using 30 layers of multilinear pairing. Subsequently, she and other researchers gradually achieved the construction of IO using only 3 layers of multilinear pairing.
On the surface, this seems like a significant advancement. However, there is a problem— from a security standpoint, 3-layer multilinear pairing is just as insecure as any other multilinear pairing with more than 3 layers.
Previously, researchers only knew that linear pairings of 2 layers or fewer were absolutely secure. Lin Huijia and Amit Sahai collaborated to find a way to construct IO using 2-layer linear pairing, but for a long time, their research did not yield breakthroughs. Ultimately, they devised a compromise: since achieving IO requires 3 layers of linear pairing, but to ensure security it needs to be reduced to 2 layers, is there a possibility of 2.5 layers?
The researchers envisioned a system that allows users to see the values of certain variables, thereby not requiring too many variables to be encrypted. However, the hidden variables in the polynomial must not exceed degree 2, meaning that in the formula 3x²y + 2yz⁴, the value of z can be visible to the user, while the degrees of variables x and y are hidden since they do not exceed degree 2. Thus, the researchers successfully achieved IO while ensuring the security of linear pairings.
Although several scientists collaborated to prove the existence of IO, the supercomputing power of quantum computers would render the vast majority of current encryption algorithms ineffective, meaning that all encrypted information would be exposed to quantum computers. Researchers are now attempting to develop a new potential pathway to IO that can withstand quantum attacks.
Source: Science and Technology Daily
Everyone Loves to Read》》》
[Notice] Notice on Collecting Annual Fees for 2021
[Notice] Notice on the First Batch of Credit Evaluations for Chinese Software and Information Service Companies in 2021
