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-$k$ algorithm with complexity $O(d \log^2{k})$, which was later improved by Yao in 1980 for small $k \ll \sqrt{d}$. In this paper, we revisit the literature on oblivious Top-$k$ and propose another improvement of Alekseev's method that outperforms both for large $k = \Omega(\sqrt{d})$. 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 $k$. To demonstrate the efficiency of our combined Top-$k$ network, we implement a secure non-interactive $k$-nearest neighbors classifier using homomorphic encryption as an application. Compared with the work of Zuber and Sirdey (PoPETS 2021) where oblivious Top-$k$ was realized with complexity $O(d^2)$, our experimental results show a speedup of up to 47 times (not accounting for difference in CPU) for $d = 1000$.