Author name cluster

Wei-Kai Lin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

STOC Conference 2023 Conference Paper

Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE

Wei-Kai Lin
Ethan Mook
Daniel Wichs

A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR) , the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O ( N 1+ε ), while the run-time and communication-complexity of each PIR query is poly log( N ). We also show how to update the preprocessed database in time O ( N ε ). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08). Building on top of our DEPIR, we construct general fully homomorphic encryption for random-access machines (RAM-FHE) , which allows a server to homomorphically evaluate an arbitrary RAM program P over a client’s encrypted input x and the server’s preprocessed plaintext input y to derive an encryption of the output P ( x , y ) in time that scales with the RAM run-time of the computation rather than its circuit size. Prior work only gave a heuristic candidate construction of a restricted notion of RAM-FHE. In this work, we construct RAM-FHE under the RingLWE assumption with circular security. For a RAM program P with worst-case run-time T , the homomorphic evaluation runs in time T 1+ε · (| x | + | y |).

Details

SODA Conference 2022 Conference Paper

Optimal Oblivious Parallel RAM

Gilad Asharov
Ilan Komargodski
Wei-Kai Lin
Enoch Peserico
Elaine Shi

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC '87 and J. ACM '96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT '20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead (in the balls and bins model). Despite the significant recent advances for constructing ORAM, there is still a significant gap for OPRAM: all existing OPRAM schemes incur a poly -logarithmic overhead either in total work or in depth. Our main result closes the aforementioned gap and provides an optimal OPRAM. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity N can be obliviously simulated in space O(N ), incurring only O (log N ) blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW (concurrent read, concurrent write) mode and the resulting simulation is in the CRCW mode as well.

Details

SODA Conference 2022 Conference Paper

Optimal Sorting Circuits for Short Keys

Wei-Kai Lin
Elaine Shi

A long-standing open question in the algorithms and complexity literature is whether there exist sorting circuits of size o(n log n ). A recent work by Asharov, Lin, and Shi (SODA'21) showed that if the elements to be sorted have short keys whose length k = o (log n ), then one can indeed overcome the n log n barrier for sorting circuits, by leveraging non-comparison-based techniques. More specifically, Asharov et al. showed that there exist O ( n ) · min( k, log n )-sized sorting circuits for k -bit keys, ignoring polylog∗ factors. Interestingly, the recent works by Farhadi et al. (STOC'19) and Asharov et al. (SODA'21) also showed that the above result is essentially optimal for every key length k, assuming that the famous Li-Li network coding conjecture holds. Note also that proving any unconditional super-linear circuit lower bound for a wide class of problems is beyond the reach of current techniques. Unfortunately, the approach taken by previous works to achieve optimality in size somewhat crucially relies on sacrificing the depth: specifically, their circuit is super- poly logarithmic in depth even for 1-bit keys. Asharov et al. phrase it as an open question how to achieve optimality both in size and depth. In this paper, we close this important gap in our understanding. We construct a sorting circuit of size O(n ) · min( k, log n ) (ignoring polylog∗ terms) and depth O (log n ). To achieve this, our approach departs significantly from the prior works. Our result can be viewed as a generalization of the landmark result by Ajtai, Komlós, and Szemerédi (STOC'83), simultaneously in terms of size and depth. Specifically, for k = o (log n ), we achieve asymptotical improvements in size over the AKS sorting circuit, while preserving optimality in depth.

Details

SODA Conference 2021 Conference Paper

Sorting Short Keys in Circuits of Size o ( n log n )

Gilad Asharov
Wei-Kai Lin
Elaine Shi

We consider the classical problem of sorting n elements, where each element is described with a k -bit comparison-key and a w -bit payload. A long-standing open problem is whether there exist ( k + w ) · o ( n log n )-sized boolean circuits for sorting. Ajtai, Komlós, and Szemerédi (STOC'83) constructed the famous AKS sorting network with ( k + w ) · O ( n log n ) boolean gates. Recently, Farhadi et al. (STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size w · o ( n log n ) do not exist for general k (while unconditional circuit lower bound is out of the reach of existing techniques). In this paper, we show that one can overcome the n log n barrier when the comparison-keys are short. Specifically, we construct a sorting circuit with ( k + w ) · O ( nk ) · poly(log∗ n – log∗( w + k )) boolean gates, asymptotically better than AKS sorting network if the keys are short, say, k = o (log n ) (ignoring poly log∗ terms). Such a result might be surprising since comparator-based techniques must incur Ω( n log n ) comparators even when the keys are only 1-bit long (e. g. , see Knuth's “Art of Programming” textbook). To the best of our knowledge, this is also the first non-trivial result on non-comparison-based sorting circuits. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring poly log∗ terms, for every k = O (log n ).

Details

SODA Conference 2019 Conference Paper

Can We Overcome the n log n Barrier for Oblivious Sorting?

Wei-Kai Lin
Elaine Shi
Tiancheng Xie

It is well-known that non-comparison-based techniques can allow us to sort n elements in o ( n log n ) time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort n elements from the domain [1‥2 k ] with o ( kn log n ) boolean gates. We consider weakened forms of this question: first, we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length; and second, we explore Oblivious RAMs and probabilistic circuit families, i. e. , computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort o(log n)-bit keys in o ( n log n ) time or o ( kn log n ) circuit complexity. Our algorithms work in the indivisible model, i. e. , not only can they sort an array of numerical keys — if each key additionally carries an opaque ball, our algorithms can also move the balls into the correct order. We further show that in such an indivisible model, it is impossible to sort Ω(log n )-bit keys in o ( n log n ) time, and thus the o (log n )-bit-key assumption is necessary for overcoming the n log n barrier. Finally, after optimizing the IO efficiency, we show that even the 1-bit special case can solve open questions: our oblivious algorithms solve tight compaction and selection with optimal IO efficiency for the first time.

Details

SODA Conference 2018 Conference Paper

Cache-Oblivious and Data-Oblivious Sorting and Applications

T. -H. Hubert Chan
Yue Guo
Wei-Kai Lin
Elaine Shi

Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost. We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotic IO-cost matches the best known cache-aware scheme. Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model.

Details