I am interested in cryptography and theoretical computer science in general.

My research focuses on performing random accesses in cryptographic protocols. My work OptORAMa constructs an ORAM that takes only a logarithmic overhead—it is the first optimal ORAM scheme asymptotically, and it closes the thirty-year old problem. Very recently, my coauthors and I constructed doubly efficient PIR and FHE for RAM programs —it not only strengthens the functionality/security but also minimizes the cryptographic assumption. In both of above results (and almost all my research), I amalgamate cryptography with algorithms.

I am an assistant professor in the Computer Science Department at University of Virginia. Earlier, I was a postdoctoral researcher at Northeastern University, advised by Professor Daniel Wichs. I got my Ph.D. in Computer Science at Cornell and then worked as a postdoc at CMU, both advised by Professor Elaine Shi. Prior to that, I worked with Dr. Kai-Min Chung as a research assistant in Academia Sinica. I got my B.S. and M.S. degrees from National Taiwan University, and subsequently I was a software engineer. My publications and teaching experience are listed below (also in my DBLP, Google Scholar). Additionally, my CV includes my detailed education and experiences.

Publications

Efficient Garbled Pseudorandom Functions and Lookup Tables from Minimal Assumption

TCC 2025. Wei-Kai Lin, Zhenghao Lu, Hong-Sheng Zhou.

[eprint]

MegaBlocks: Breaking the Logarithmic I/O-Overhead Barrier for Oblivious RAM

CCS 2025. Gilad Asharov, Eliran Eiluz, Ilan Komargodski, Wei-Kai Lin.

[eprint] [CCS 2025]

Black Box Crypto is Useless for Doubly Efficient PIR

Eurocrypt 2025. Wei-Kai Lin, Ethan Mook, Daniel Wichs.

[eprint] [Eurocrypt]

Doubly Efficient Cryptography: Commitments, Arguments and RAM MPC

Crypto 2024. Wei-Kai Lin, Ethan Mook, Daniel Wichs.

[eprint] [Crypto]

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 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. SICOMP 2025. Ilan Komargodski, Wei-Kai Lin. [eprint] [Springer] [video] [slides] [SICOMP]

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]

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: There are some papers authored by "Wei-Kai Lin" in my DBLP, but the author is not me, and I did not contribute to any of them. Some of them are listed here.

Teaching Experiences

Undergraduate Students

Liran Li, Alice Wanner, Mikhail Kornilov.

CS 3120: Theory of Computation (UVA)

Instructor. Undergraduate requirement, also called Discrete Math and Theory 2. [Spring 2025]

CS 4501: Cryptography (Undergrad, Spring 2024, UVA)

Instructor. [website]

CS 5660: Signal Processing (Fall 2016, Cornell)

Teaching assistant. Instructor: Prof. Charles Johnson. [website]

2016 Summer School of Cryptography (Institute of Mathematics, Academia Sinica)

Co-instructor, supervised by Dr. Yu-Chi Chen, Dr. Kai-Min Chung, Dr. Chia-Liang Sun, and Dr. Julie Tzu-Yueh Wang.

2015 Summer School of Cryptography (Institute of Mathematics, Academia Sinica)

Co-instructor, supervised by Prof. Jiun-Ming Chen, Dr. Yu-Chi Chen, Dr. Kai-Min Chung, Prof. Anly Li, Dr. ChiaLiang Sun, and Dr. Julie Tzu-Yueh Wang. [website]

Get In Touch