Reproduce “Efficient Ranking, Order Statistics, and Sorting under CKKS” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Federico Mazzone, Maarten Everts, Florian Hahn, Andreas Peter
This work introduces a suite of Fully Homomorphic Encryption (FHE) algorithms for ranking, order statistics, and sorting under the CKKS scheme, achieving a constant comparison depth of 1 or 2. The methods utilize a novel re-encoding strategy for simultaneous comparisons, resulting in performance improvements, such as calculating argmin/argmax for 128 elements in 12.83 seconds, outperforming prior methods for small to medium-sized inputs.
Key insights
- Achieving constant comparison depth (1 or 2) for fundamental operations like ranking and sorting under FHE is possible, leading to high intrinsic parallelizability.
- A quadratic increase in comparison tasks occurs when scaling to multiple ciphertexts, which, despite parallelization, limits overall scalability for very large input sizes.
- Tie-correction mechanisms can be effectively integrated into homomorphic ranking algorithms to ensure surjective rank assignments, albeit with an associated computational overhead.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.