Paper 2023/852

Revisiting Oblivious Top-$k$ Selection with Applications to Secure $k$-NN Classification

Abstract

An oblivious Top-$k$ algorithm selects the $k$ smallest elements from $d$ elements while ensuring the sequence of operations and memory accesses do not depend on the input. In 1969, Alekseev proposed an oblivious Top-$$ algorithm with complexity $$, which was later improved by Yao in 1980 for small $$. In this paper, we revisit the literature on oblivious Top-$$ and propose another improvement of Alekseev's method that outperforms both for large $$. Our construction is equivalent to applying a new truncation technique to Batcher's odd-even sorting algorithm. In addition, we propose a combined network to take advantage of both Yao's and our technique that achieves the best concrete performance, in terms of the number of comparators, for any $$. To demonstrate the efficiency of our combined Top-$$ network, we implement a secure non-interactive $$-nearest neighbors classifier using homomorphic encryption as an application. Compared with the work of Zuber and Sirdey (PoPETS 2021) where oblivious Top-$$ was realized with complexity $$, our experimental results show a speedup of up to 47 times (not accounting for difference in CPU) for $$.