A long-sought “holy grail” in crypto is poised to change the way we protect sensitive information.
Today’s standard encryption schemes take an all-or-nothing approach. Once encrypted, your data becomes inaccessible to anyone without the secret key.
This has enabled secure email communication, the proliferation of online transactions and digital signatures. It enables tax and medical records containing sensitive personal information to be transmitted more securely over the Internet. But if you give someone the secret key to access any of the data, all the data becomes vulnerable.
What if you could instead assign access to specific people to do very specific things with your data? Someone could get the information they need (information you want them to have) without unlocking all of the original data. Bank details, credit card numbers, account passwords – everything would remain hidden. That entirely different approach could also allow Netflix to make show recommendations without seeing your entire viewing history, for example. Google could classify your emails without knowing what they contain. And medical researchers could analyze the data to identify risk factors for a disease without accessing anyone’s health information.
This and other cryptographic wonders now seem possible through a masterful tool called indistinguishability obfuscation.
“It’s a new tool, a very powerful tool,” says cryptographer Huijia (Rachel) Lin of the University of Washington in Seattle, who showed with colleagues in 2020 how to build the tool. “Once you have this super strong power, many of the other tasks are special cases of it, or you can easily use this to perform [those tasks].”
Vinod Vaikuntanathan, a computer scientist at MIT who has worked with Lin on previous research, likens indistinguishability obfuscation, or iO, to a grand theory of physics that would unite gravity and quantum mechanics. “iO gives you a way to do a great unification of crypto in the sense that you can explain a lot of what crypto does in a very simple way.”
Indistinguishability obfuscation is a form of program obfuscation, an approach that seeks to hide the inner workings of a computer program, not just the message or data itself. Although proposed in 1976 in a document that laid the foundation for modern cryptography, obfuscation of the program proved difficult to achieve. For many years, people thought that it might not be possible.
And in 2001, researchers showed that complete program obfuscation, called black-box obfuscation, in which input and output data are known but nothing else about a program can be discovered, is impossible. However, the obfuscation of indistinguishability, proposed at the same time and shown to be incredibly powerful, does not require that. all about a program remain hidden. Instead, these are two programs that perform the same function. If the inner workings of those two programs can be hidden enough that they cannot be distinguished from each other, indistinguishability obfuscation has been achieved. By hiding the secret key within the program itself, iO enables the delegation of specific data and data tasks to specific people.
Still, proposal after proposal to make iO work proved fragile. The researchers couldn’t figure out how to keep it safe from an adversary’s attacks. Lin says that the approaches used did not appeal to him. The researchers relied on what appeared to be “good enough” ways of solving the problem that were not supported by rigorous mathematical proof.
Instead, Lin wanted to break the problem down so she could understand each component and how they worked together. She wanted to approach the problem like clockwork, with gears, nuts and bolts, instead of messing it up like “a bowl of spaghetti”.
Through this strategy, Lin, along with Amit Sahai of UCLA and Aayush Jain, Ph.D. UCLA student at the time, proved that iO is achievable. It would be safe under standard assumptions in the field, the team demonstrated, renewing hope in the tool.
“Of course, [Huijia] it’s brilliant,” says Vaikuntanathan, adding that her persistence is what really sets her apart. “It takes some guts to continue with an approach when essentially everyone else in the world thinks it’s not going to work.”
Lin says she didn’t grow up with computers or fall in love with computer programming at a young age. As a student, she was interested in physics and strove to be good at everything. She started with computer science in college; a cryptography class like Ph.D. Cornell University student “was really eye-opening,” she says. Her introduction to what is known as zero knowledge proofs stands out in his memory.
A zero-knowledge proof says that a person can convince another person that they know a secret without revealing the secret or any details about it. Let’s say, for example, that you knew that a number was the product of two prime numbers. Can you convince someone that the fact is true without revealing what the prime numbers are? How to demonstrate that such a task is possible fascinated Lin.
Cryptography includes many of these seeming paradoxes that prove to be possible. Indistinguishability obfuscation is another example, and Lin is working on others, including secure multiparty computing, which allows a computer task to run on multiple people’s data without any one person having to reveal their data to anyone else. the group or a third party.
“I’m very attracted to these magical concepts,” says Lin. “The fun is making this concept come true.”
Indistinguishability obfuscation is still far from real-world implementation. But Vaikuntanathan says it’s not unusual for early constructions of what will become major approaches to be impractical at first. “Wait a decade,” he says.
Do you want to nominate someone for the next SN 10 list? Send your name, affiliation and a few sentences about them and their work to firstname.lastname@example.org.