Science News has named professor Huijia (Rachel) Lin, a founding member of the Allen School’s Cryptography group, as one of its SN 10: Scientists to Watch. Each year, Science News recognizes 10 scientists who are making a mark in their respective fields while working to solve some of the world’s biggest problems. Lin earned her place on the 2022 list for achieving a breakthrough on what has been alternately referred to as the “holy grail” or “crown jewel” of cryptography by proving the security of indistinguishability obfuscation.
“I’m very attracted to these magical concepts,” Lin told Science News. “The fun of it is to make this concept come to realization.”
While Lin explores a variety of fundamental problems — from black-box constructions for securing multiparty computation to zero-knowledge proofs — her work on iO has been celebrated for answering an open question that had vexed cryptographers for more than 40 years: How to prove the security of this potentially powerful “master tool” for securing data and computer programs while maintaining their functionality and bring it into the mainstream. According to the article, previous attempts at proving iO were generally geared toward obtaining a result that would be deemed “good enough” — and one by one, those attempts would unravel under further scrutiny.
Lin aimed for more than “good enough” by seeking a generalizable solution grounded in sound mathematical theory. Rather than approaching iO like “a bowl of spaghetti,” as she put it, Lin preferred to attack the problem by untangling it into its component parts, working alongside University of California, Los Angeles professor Amit Sahai and his then-Ph.D. student and NTT Research intern Aayush Jain, now a professor at Carnegie Mellon University. After two years, the team had a theoretical framework for provably secure iO that was based on a quartet of well-founded assumptions: Symmetric External Diffie-Hellman (SXDH) on pairing groups, Learning with Errors (LWE), Learning Parity with Noise (LPN) over large fields, and a structured-seed Boolean Pseudo-Random Generator (sPRG). The result was first reported in Quanta Magazine in the summer of 2020; Lin and her collaborators subsequently earned a Best Paper Award at the Association for Computing Machinery’s 53rd Symposium on Theory of Computing (STOC 2021) for their contribution — one that Lin is eager to see progress from theory to reality.
“These are ambitious goals that will need the joint effort from the entire cryptography community,” she observed at the time. “I look forward to working on these questions and being part of the effort.”
In other words, watch this space.
Lin is the second member of the Allen School’s Theory of Computation group to be recognized on the SN 10 list, after her colleague Shayan Oveis Gharan was highlighted in 2016.
Read Lin’s profile in Science News here, and the Quanta article on the i/O breakthrough here.
Photo: Dennis Wise/University of Washington