Jesper Buus Nielsen

Riko Jacob, Kasper Green Larsen, Jesper Buus Nielsen

An oblivious data structure is a data structure where the memory access patterns reveals no information about the operations performed on it. Such data structures were introduced by Wang et al. [ACM SIGSAC'14] and are intended for situations where one wishes to store the data structure at an untrusted server. One way to obtain an oblivious data structure is simply to run a classic data structure on an oblivious RAM (ORAM). Until very recently, this resulted in an overhead of $ω(\lg n)$ for the most natural setting of parameters. Moreover, a recent lower bound for ORAMs by Larsen and Nielsen [CRYPTO'18] show that they always incur an overhead of at least $Ω(\lg n)$ if used in a black box manner. To circumvent the $ω(\lg n)$ overhead, researchers have instead studied classic data structure problems more directly and have obtained efficient solutions for many such problems such as stacks, queues, deques, priority queues and search trees. However, none of these data structures process operations faster than $Θ(\lg n)$, leaving open the question of whether even faster solutions exist. In this paper, we rule out this possibility by proving $Ω(\lg n)$ lower bounds for oblivious stacks, queues, deques, priority queues and search trees.

Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi et al.

We propose a new approach to practical two-party computation secure against an active adversary. All prior practical protocols were based on Yao's garbled circuits. We use an OT-based approach and get efficiency via OT extension in the random oracle model. To get a practical protocol we introduce a number of novel techniques for relating the outputs and inputs of OTs in a larger construction. We also report on an implementation of this approach, that shows that our protocol is more efficient than any previous one: For big enough circuits, we can evaluate more than 20000 Boolean gates per second. As an example, evaluating one oblivious AES encryption (~34000 gates) takes 64 seconds, but when repeating the task 27 times it only takes less than 3 seconds per instance.