Paper on Private Information Retrieval Co-authored by CIS Lab Senior Scientist Daniel Wichs Recognized at ACM Symposium on Theory of Computing
Sunnyvale, Calif. – June 20, 2023 – NTT Research, Inc., a division of NTT (TYO:9432), today announced that a paper by NTT Research Cryptography & Information Security (CIS) Lab Senior Scientist Daniel Wichs that is being presented at the Association for Computing Machinery (ACM) Symposium on Theory of Computing (STOC) has won a Best Paper Award. It was one of two that the STOC 2023 program committee awarded this year. Dr. Wichs is also an Associate Professor of Computer Science in the Khoury College of Computer Sciences at Northeastern University. His co-authors are Dr. Wei-Kai Lin and Ethan Mook, post-doctoral fellow and doctoral student, respectively, at Northeastern. The paper, titled “Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE,” solves a longstanding open problem involving private information retrieval. A hypothetical use case of this work cited in the paper is an encrypted version of the Google search engine that would enable users to search the internet privately.
“We look forward to recognizing Daniel Wichs with a Best Paper Award at this year’s ACM STOC 2023,” said ACM STOC Program Committee Chair Rocco Servedio of Columbia University. “By introducing a new approach to constructing fully homomorphic encryption for random access machines, Wichs’ paper makes a significant contribution to the field of cryptography that will have lasting impact.”
Private information retrieval (PIR) is a type of fully homomorphic encryption (FHE), a technique that enables computation on encrypted data. A key limitation on PIR is that each encrypted search query requires a server (or single entity of servers) to read an entire database. This represents a significant computational tax, whether the database is the global internet or something less expansive. To reduce that burden, cryptographers proposed doubly efficient (DE)PIR, which would pre-process the database, making it much easier for client and server to use later. The open question was DEPIR’s actual construction, including secure grounding on the right assumption. To reach a solution, Wichs and his co-authors first constructed a standard PIR, where the server’s computation consists of evaluating a multivariate polynomial; then converted it to a DEPIR by preprocessing the polynomial, using the techniques introduced in a STOC 2008 paper by Kedlaya and Umans; and finally grounded their construction on the well-studied learning with errors over rings (RingLWE) hardness assumption. Once the authors realized that this combination of ideas and parameters solved DEPIR, they extended the solution to cover the superset category of random access machine, fully homomorphic encryption (RAM-FHE) computation. The achievement had an element of serendipity.
“We expected that the problem of DEPIR was too hard and were not even attempting to solve it,” Wichs said. “Instead, we were trying to use the Kedlaya and Umans preprocessing to solve a much less interesting problem and kept getting stuck. But then we had the idea that it may actually solve DEPIR. Initially, we were very skeptical and kept trying to find reasons why it shouldn’t work, until we finally convinced ourselves that it does.”
A Best Paper Award recognizes an innovative contribution and the importance of the research field. “The DEPIR problem has been open for many years and we were previously very far from having any satisfactory solution,” Wichs said. “The fact that this technique solves the DEPIR problem and then actually extends much further to solve all of RAM-FHE was quite surprising.”
His co-authors played essential roles. “Wei-Kai is an expert in data-structures and algorithms, while Ethan has a strong mathematical background and deep knowledge of ring algebra,” Wichs said. “Our result crucially relied on combining these areas of knowledge.”
Other members of the CIS Lab affirmed the paper’s significance. “This work is a surprising and beautiful departure that allows for achieving this powerful tool on solid cryptographic grounds,” said Dr. Elette Boyle, CIS Lab Senior Scientist.
“This work is a pretty astonishing breakthrough,” said Justin Holmgren, CIS Lab Scientist. “Previously we didn’t even have a candidate construction of DEPIR, or any good reason to think that doubly efficient PIR was possible. This paper not only contributes a candidate, but also proves that this candidate is secure under a standard cryptographic assumption (RingLWE).”
Sponsored by the ACM Special Interest Group on Algorithms and Computation Theory, the 55th ACM STOC will be held in Orlando, Fla., June 20-23, 2023. STOC 2023 is part of the ACM Federated Computing Research Conference, which encompasses other events, including the Symposium on Parallelism in Algorithms and Architectures (SPAA) and the Symposium on the Principles of Distributed Computing (PODC). This year’s STOC 2023 program committee, consisting of 74 cryptographic experts, selected 155 papers. Three other NTT-affiliated papers accepted for the event include one co-authored by NTT Social Informatics Laboratories (SIL) Research Scientist Takashi Yamakawa, one by CIS Lab Senior Researcher Mark Zhandry, and another by Wichs:
- Obfuscation of Pseudo-Deterministic Quantum Circuits – James Bartusek (UC Berkeley); Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa (NTT SIL)
- Commitments to Quantum States – Sam Gunn, Nathan Ju (UC Berkeley); Fermi Ma (Simons Institute and UC Berkeley); and Mark Zhandry (NTT Research and Princeton University)
- Boosting Batch Arguments and RAM Delegation – Yael Kalai (Microsoft Research and MIT); Alex Lombardi (Simons Institute and UC Berkeley); Vinod Vaikuntanathan (MIT); and Daniel Wichs (Northeastern and NTT Research)
As part of NTT Research Inc., founded in 2019 in Sunnyvale, California, the CIS Lab has assembled a team of world-class cryptographers. Their work has made landmark contributions in the field of cryptography through their prominent participation in leading international conferences, including STOC, Eurocrypt and Crypto. NTT SIL, part of NTT Group’s R&D team in Tokyo, collaborates with the CIS Lab across many areas of cryptography research to collectively advance future cybersecurity technologies.
About NTT Research
NTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advance technologies that promote positive change for humankind. Currently, three labs are housed at NTT Research facilities in Sunnyvale: the Physics and Informatics (PHI) Lab, the Cryptography and Information Security (CIS) Lab, and the Medical and Health Informatics (MEI) Lab. The organization aims to upgrade reality in three areas: 1) quantum information, neuroscience and photonics; 2) cryptographic and information security; and 3) medical and health informatics. NTT Research is part of NTT, a global technology and business solutions provider with an annual R&D budget of $3.6 billion.
###
NTT and the NTT logo are registered trademarks or trademarks of NIPPON TELEGRAPH AND TELEPHONE CORPORATION and/or its affiliates. All other referenced product names are trademarks of their respective owners. © 2023 NIPPON TELEGRAPH AND TELEPHONE CORPORATION
| NTT Research Contact: Chris Shaw Chief Marketing Officer NTT Research +1-312-888-5412 chris.shaw@ntt-research.com | Media Contact: Stephen Russell Wireside Communications® For NTT Research +1-804-362-7484 srussell@wireside.com |
