Huijia Lin says she is drawn to “magical concepts” – seeming paradoxes that turn out to be possible.
Dennis Wise/University of Washington
A long-sought “holy grail” in cryptography is poised to change the way we protect sensitive information.
Today’s standard encryption schemes take an all-or-nothing approach. Once scrambled, your data become inaccessible to anyone without the secret key.
This has allowed for secure e-mail communication, the proliferation of online transactions and digital signatures. It allows tax and medical records with sensitive personal information to be passed more safely across the internet. But if you give someone the secret key to access any of the data, all of the data become vulnerable.
What if instead you could assign specific people access to do very specific things with your data? Someone could get the information they need (the info you want them to have) without unlocking all of the original data. Bank details, credit card numbers, account passwords – all would remain hidden. That wholly different approach could also allow Netflix to make show recommendations without seeing your full viewing history, for example. Google could sort your e-mails without knowing what’s in them. And medical researchers could analyze data to identify risk factors for a disease without accessing any individual’s health information.
This and other cryptographic wonders now appear possible through a master 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 construct the tool. “Once you have this superstrong power, then a lot of the other tasks are either special cases of it, or you can easily use this to realize [those tasks].”
Vinod Vaikuntanathan, a computer scientist at MIT who has worked with Lin on previous research, compares indistinguishability obfuscation, or iO, to a grand theory in physics that would unite gravity and quantum mechanics. “iO gives you a way to do a grand unification of cryptography in the sense that you can explain much of what cryptography does in a very simple way.”
Standout research
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. Though proposed in 1976 in a paper that set the foundation for modern cryptography, program obfuscation proved difficult to achieve. For many years, people thought 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. Yet indistinguishability obfuscation, proposed at the same time and shown to be incredibly powerful, doesn’t demand that everything about a program remain hidden. It instead deals with two programs that perform the same function. If the inner workings of those two programs can be hidden enough that the two can’t 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 for making iO work proved breakable. Researchers couldn’t figure out how to keep it safe from an adversary’s attacks. Lin says the approaches being used didn’t appeal to her. Researchers were leaning on what appeared to be “good enough” ways of getting at the problem that weren’t backed by rigorous mathematical proofs.
Lin instead wanted to break the problem down so she could understand each component and how they worked together. She wanted to approach the problem like a clock, with gears and nuts and bolts, instead of tangled like “a bowl of spaghetti.”
Through this strategy, Lin, along with Amit Sahai of UCLA and Aayush Jain, a Ph.D. student at UCLA at the time, demonstrated that iO is achievable. It would be secure based on standard assumptions in the field, the team proved, renewing hope in the tool.
“Of course, [Huijia] is brilliant,” Vaikuntanathan says, adding that her persistence is what really sets her apart. “It takes some guts to continue with an approach when essentially all the rest of the world thinks that it is not going to work.”
Backstory
Lin says she didn’t grow up with computers or fall in love with computer programming at an early age. As a student, she was interested in physics and strived to be good at everything. She started with computer science in college; a class in cryptography as a Ph.D. student at Cornell University “was really mind-opening,” she says. Her introduction to what are known as zero-knowledge proofs stands out in her memory.
A zero-knowledge proof says that a person can convince someone else that they know a secret without revealing the secret or any details about it. Say, for example, you knew that a number was the product of two prime numbers. Can you convince someone that fact is true without revealing what the primes are? How to prove that such a task is possible fascinated Lin.
Cryptography includes a lot of these seeming paradoxes that prove to be possible. Indistinguishability obfuscation is yet another example – and Lin works on others, including secure multiparty computation, which allows a computer task to run across multiple people’s data without any person having to reveal their data to anyone in the group, or to a third party.
“I’m very attracted to these magical concepts,” Lin says. “The fun of it is to make this concept come to realization.”
Indistinguishability obfuscation is still far from real-world implementation. But Vaikuntanathan says it’s not unusual for first constructions of what will become important approaches to be impractical at first. “Wait for a decade,” he says.
Want to nominate someone for the next SN 10 list? Send their name, affiliation and a few sentences about them and their work to sn10@sciencenews.org.
