abstract
we present a deterministic oblivious lifo (stack), fifo, double-ended and double-ended priority queue as well as
an oblivious mergesort and quicksort algorithm. our techniques and ideas include concatenating queues end-to-end,
size balancing of multiple arrays, several multi-level partitionings of an array. our queues are the first to enable
executions of pop and push operations without any change of the data structure (controlled by a parameter). this
enables interesting applications in computing on encrypted data such as hiding confidential expressions. mergesort
becomes practical using our lifo queue, ie. it improves prior work (stoc ’14) by a factor of (more than) 1000 in
terms of comparisons for all practically relevant queue sizes. we are the first to present double-ended (priority) and
lifo queues as well as oblivious quicksort which is asymptotically optimal. aside from theortical analysis, we also
provide an empirical evaluation of all queues.
keywords: sorting, queues, complexity, oblivious algorithms, privacy preserving, computation on encrypted data,
secure computing, fully homomorphic encryption, secure multi-party computation