Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
STOC 2023, Best Paper Award.
Wei-Kai Lin, Ethan Mook, Daniel Wichs.
[eprint]
[STOC]
[video 1 (Ethan)]
[video 2 (Wei-Kai)]
[video (Daniel)]
[ + ]
Problem:
Consider the computation on a large public database of size $n$, say searching the index of the whole internet on Google. Can we privately search the internet but also ensure Google learns nothing about our query? We want to minimize the cost on Google and users while achieving privacy. The feasibility of this problem is proposed by Beimel, Ishai, and Malkin in 2000.
Ideally, we want privacy without extra cost: that is, Google takes time and space comparable to the insecure searching, and each user just sends and receives the query and result.
Result:
We show the feasibility assuming the hardness of Ring Learning-With-Errors (Ring LWE), which is a standard assumption adopted by NIST post-quantum encryption. The cost is $n^\epsilon$ on the server space and $poly \log n$ on query time (multiplicatively) for any constant $\epsilon$. Our result is an exciting breakthrough due to the strengthened functionality and the minimal assumption.
Optimal Single-Server Private Information Retrieval
Eurocrypt 2023.
Mingxun Zhou, Wei-Kai Lin, Yiannis Tselekounis, Elaine Shi.
[eprint]
[video (Charles River Crypto Day)]
[ + ]
Problem: We consider the offline-online setting of single-server PIR: in the offline phase, a client subscribes to the server and obtains a secret summary of the public database, and then in the online phase, the client queries a location in the database. We want to esure that the location is hidden from the server while the space, time, and communication are all small/short.
Result: Our scheme achieves $\widetilde O(\sqrt{n})$ in client space and server time but also $\widetilde O(1)$ communication, where the space is persistent for unbounded queries, the time and communication are per-query, $n$ is the size of the database, and $\widetilde O$ hides factors in $\log n$ and the security parameter. Our result is optimal up to logarithmic factors by the previous space-time tradeoff.
NanoGRAM: Garbled RAM with $\tilde{O}(\log N)$ Overhead
Eurocrypt 2023.
Andrew Park, Wei-Kai Lin, Elaine Shi.
[eprint]
[ + ]
Problem:
Garbled RAM (GRAM) schemes transform a pair of RAM program and input into an unintelligent garbling so that any adversary may evaluate the garbling and obtain the correct output but nothing else (about the program or the input). The goal of GRAM is to minimize the evaluation time (that is, without converting the program into huge circuits).
Result:
We construct a better and more practical GRAM scheme. It achieves $\widetilde O(\log n)$ blowup in garbling and evaluation time, where $n$ is the memory size of the RAM program, and $\widetilde O$ hides $poly \log\log n$ and the security parameter.
Optimal Sorting Circuits for Short Keys
Wei-Kai Lin, Elaine Shi.
SODA 2022.
[arXiv]
[slides]
[practice talk]
Optimal Oblivious Parallel RAM
SODA 2022.
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi.
[eprint]
[slides]
[practice talk]
A Logarithmic Lower Bound for Oblivious RAM (for all parameters)
Crypto 2021.
Ilan Komargodski, Wei-Kai Lin.
[eprint]
[Springer]
[video]
[slides]
Oblivious RAM with Worst-Case Logarithmic Overhead
Crypto 2021. JCrypto 2023.
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Elaine Shi.
[eprint]
[Crypto]
[Journal of Cryptology 23]
Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions
ITC 2021.
T-H. Hubert Chan, Elaine Shi, Wei-Kai Lin, Kartik Nayak.
[eprint]
[DROPS]
[video]
Sorting Short Keys in Circuits of Size $o(n \log n)$
SODA 2021, SICOMP 2022.
Gilad Asharov, Wei-Kai Lin, Elaine Shi.
[arXiv]
[SODA]
[SICOMP]
Oblivious Parallel Tight Compaction
ITC 2020.
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, Elaine Shi.
[DROPS]
[eprint]
[video (25 min)]
[video (short)]
[Bibtex]
OptORAMa: Optimal Oblivious RAM
Eurocrypt 2020, JACM 2022.
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, Elaine Shi.
[DOI]
[JACM]
[eprint]
[video (Gilad)]
[Bibtex]
[ + ]
Problem:
Oblivious RAM (ORAM) schemes transform any RAM program into a functionally equivalent one such that its accesses locations in the memory are unintelligible. ORAMs are capable of hiding the accesses in outsourced storage or in secure multi-party protocols. The main open problem is the overhead of ORMAs, that is, the per-access cost for the desired security.
Result:
We construct the first optimal ORAM scheme, OptORAMa, such that takes $O(\log n)$ overhead, where $n$ is the size of the memory. This result matches the lower bounds of $\Omega(\log n)$ and closed the problem of ORAM, which was initiated by Goldreich and Ostrovsky since 1987.
MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
ITCS 2020.
T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi.
[DOI]
[eprint]
[slides]
[video]
Can We Overcome the $n \log n$ Barrier for Oblivious Sorting?
SODA 2019.
Wei-Kai Lin, Elaine Shi, Tiancheng Xie.
[DOI]
[eprint]
Game Theoretic Notions of Fairness in Multi-Party Coin Toss
TCC 2018.
Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass, Elaine Shi.
[DOI]
[eprint]
[slides]
Cache-Oblivious and Data-Oblivious Sorting and Applications
SODA 2018.
T-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi.
[DOI]
[eprint]
[slides]
Oblivious Hashing Revisited, and Applications to Asymptotically Efficient ORAM and OPRAM
Asiacrypt 2017.
T-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi.
[DOI]
[eprint]
[slides]
Delegating RAM Computations with Adaptive Soundness and Privacy
TCC 2016-B.
Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin and Wei-Kai Lin.
[DOI]
[eprint]
Cryptography for Parallel RAM from Indistinguishability Obfuscation
ITCS 2016.
Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, and Hong-Sheng Zhou.
[DOI]
[eprint]
Co-evolvability of Games in Coevolutionary Genetic Algorithms
GECCO 2009.
Wei-Kai Lin and Tian-Li Yu.
[DOI]
Optimal Sampling of Genetic Algorithms on Polynomial Regression
GECCO 2008.
Tian-Li Yu and Wei-Kai Lin.
[DOI]
Disclaimer: In the following publications, the author "Wei-Kai Lin" is not me,
and I did not contribute to any of those works.
* A machine learning approach for predicting urine output after fluid administration (Computer methods and Programs in Biomedicine)
* Automation of the kidney function prediction and classification through ultrasound-based kidney imaging using deep learning (npj Digital Medicine)
