called indistinguishability obfuscation
has for years seemed too good to be true.
Three researchers have figured out
that it can work...
As he detailed the team's approach to indistinguishability obfuscation (iO for short), one audience member raised his hand in bewilderment.
At the time, such skepticism was widespread.
Indistinguishability obfuscation, if it could be built, would be able to hide not just collections of data but the inner workings of a computer program itself, creating a sort of cryptographic master tool from which nearly every other cryptographic protocol could be built.
But to many computer scientists, this very power made iO
seem too good to be true.
As the attacks piled up,
But as the years went by, she said,
In a paper posted online on August 18, the three researchers show for the first time how to build indistinguishability obfuscation using only "standard" security assumptions.
a graduate student at the
University of California, Los Angeles,
All cryptographic protocols rest on assumptions - some, such as the famous RSA algorithm - depend on the widely held belief that standard computers will never be able to quickly factor the product of two large prime numbers.
A cryptographic protocol is only as secure as its assumptions, and previous attempts at iO were built on untested and ultimately shaky foundations.
The new protocol, by contrast, depends on security assumptions that have been widely used and studied in the past.
While the protocol is far from ready to be deployed in real-world applications, from a theoretical standpoint it provides an instant way to build an array of cryptographic tools that were previously out of reach.
For instance, it enables the creation of "deniable" encryption, in which you can plausibly convince an attacker that you sent an entirely different message from the one you really sent, and "functional" encryption, in which you can give chosen users different levels of access to perform computations using your data.
The new result should definitively silence the iO skeptics, Ishai said.
The Crown Jewel
For decades, computer scientists wondered if there is any secure, all-encompassing way to obfuscate computer programs, allowing people to use them without figuring out their internal secrets.
But so far, all attempts to build practical obfuscators have failed.
In 2001, bad news came on the theoretical front too:
Called black box obfuscation, it demands that attackers should be able to learn absolutely nothing about the program except what they can observe by using the program and seeing what it outputs.
Some programs, Barak, Sahai and five other researchers showed, reveal their secrets so determinedly that they are impossible to obfuscate fully.
These programs, however, were specially concocted to defy obfuscation and bear little resemblance to real-world programs.
So computer scientists hoped there might be some other kind of obfuscation that was weak enough to be feasible but strong enough to hide the kinds of secrets people actually care about.
The same researchers who showed that black box obfuscation is impossible proposed one possible alternative in their paper: indistinguishability obfuscation.
On the face of it, iO doesn't seem like an especially useful concept. Instead of requiring that a program's secrets be hidden, it simply requires that the program be obfuscated enough that if you have two different programs that perform the same task, you can't distinguish which obfuscated version came from which original version.
Amit Sahai of UCLA.
But iO is stronger than it sounds.
For example, suppose you have a program that carries out some task related to your bank account, but the program contains your unencrypted password, making you vulnerable to anyone who gets hold of the program.
Then - as long as there is some program out there that could perform the same task while keeping your password hidden - an indistinguishability obfuscator will be strong enough to successfully mask the password.
After all, if it didn't, then if you put both programs through the obfuscator, you'd be able to tell which obfuscated version came from your original program.
Over the years, computer scientists have shown that you can use iO as the basis for almost every cryptographic protocol you could imagine (except for black box obfuscation).
That includes both classic cryptographic tasks like public key encryption (which is used in online transactions) and dazzling newcomers like fully homomorphic encryption, in which a cloud computer can compute on encrypted data without learning anything about it.
And it includes cryptographic protocols no one knew how to build, like deniable or functional encryption.
In 2013, Sahai and five co-authors proposed an iO protocol that splits up a program into something like jigsaw puzzle pieces, then uses cryptographic objects called multilinear maps to garble the individual pieces.
If the pieces are put together correctly, the garbling cancels out and the program functions as intended, but each individual piece looks meaningless.
The result was hailed as a breakthrough and prompted dozens of follow-up papers. But within a few years, other researchers showed that the multilinear maps used in the garbling process were not secure.
Other iO candidates came along and were broken in their turn.
People started to feel, he said, that,
Hiding Less to Hide More
In 2016, Lin started exploring whether it might be possible to get around the weaknesses of multilinear maps by simply demanding less of them.
Multilinear maps are essentially just secretive ways of computing with polynomials - mathematical expressions made up of sums and products of numbers and variables, like 3xy + 2yz2.
These maps, Jain said, entail something akin to a polynomial calculating machine connected to a system of secret lockers containing the values of the variables.
A user who drops in a polynomial that the machine accepts gets to look inside one final locker to find out whether the hidden values make the polynomial evaluate to 0.
For the scheme to be secure, the user shouldn't be able to figure out anything about the contents of the other lockers or the numbers that were generated along the way.
But in all the candidate multilinear maps people could come up with, the process of opening the final locker revealed information about the calculation that was supposed to stay hidden.
Huijia Lin of the
University of Washington.
Since the proposed multilinear map machines all had security weaknesses, Lin wondered if there was a way to build iO using machines that don't have to compute as many different kinds of polynomials (and therefore might be easier to build securely).
Four years ago, she figured out how to build iO using only multilinear maps that compute polynomials whose "degree" is 30 or less (meaning that every term is a product of at most 30 variables, counting repeats).
Over the next couple of years, she, Sahai and other researchers gradually figured out how to bring the degree down even lower, until they were able to show how to build iO using just degree-3 multilinear maps.
On paper, it looked like a vast improvement. There was just one problem: From a security standpoint, "degree 3 was actually as broken" as the machines that can handle polynomials of every degree, Jain said.
The only multilinear maps researchers knew how to build securely were those that computed polynomials of degree 2 or less. Lin joined forces with Jain and Sahai to try to figure out how to construct iO from degree-2 multilinear maps.
Eventually, though - together with Prabhanjan Ananth of the University of California, Santa Barbara and Christian Matt of the blockchain project Concordium - they came up with an idea for a sort of compromise:
The researchers envisioned a system in which some of the lockers have clear windows, so the user can see the values contained within.
This frees the machine from having to protect too much hidden information.
To strike a balance between the power of higher-degree multilinear maps and the security of degree-2 maps, the machine is allowed to compute with polynomials of degree higher than 2, but there's a restriction: The polynomial must be degree 2 on the hidden variables.
The researchers were able to show that these hybrid locker systems can be constructed securely.
But to get from these less powerful multilinear maps to iO, the team needed one last ingredient:
That's what Jain, Lin and Sahai have figured out how to do in their new paper.
The result is an iO protocol that finally avoids the security weaknesses of multilinear maps.
The scheme's security rests on four mathematical assumptions that have been widely used in other cryptographic contexts.
And even the assumption that has been studied the least, called the "learning parity with noise" assumption, is related to a problem that has been studied since the 1950s.
There is likely only one thing that could break the new scheme: a quantum computer, if a full-power one is ever built.
One of the four assumptions is vulnerable to quantum attacks, but over the past few months a separate line of work has emerged in three separate papers by Pass and other researchers offering a different potential route to iO that might be secure even from quantum attacks.
These versions of iO rest on less established security assumptions than the ones Jain, Lin and Sahai used, several researchers said.
But it is possible, Barak said, that the two approaches could be combined in the coming years to create a version of iO that rests on standard security assumptions and also resists quantum attacks.
Jain, Lin and Sahai's construction will likely entice new researchers into the field to work on making the scheme more practical and to develop new approaches, Ishai predicted.
Computer scientists still have much work to do before the protocol (or some variation on it) can be used in real-world applications.
But that is par for the course, researchers said.
The road from a theoretical breakthrough to a practical protocol can be a long one, Barak said.