Paper 2026/1495 Original: eprint.iacr.org/2026/1495 ↗
Oblivious Sorting under Fully Homomorphic Encryption: A Comprehensive Survey and Performance Analysis
Abstract
Outsourcing computations to cloud providers raises significant data privacy concerns, making Privacy-Preserving Computation via Fully Homomorphic Encryption (FHE) increasingly vital. However, adapting data sorting routines to the FHE domain introduces severe performance bottlenecks. This survey systematizes the state-of-the-art in FHE-based sorting algorithms. A novel complexity metric, FHE-Effort, is introduced to accurately evaluate homomorphic circuit efficiency. Eighteen algorithms are benchmarked across three major FHE schemes using a unified codebase. The analysis concludes that TFHE is currently the most efficient scheme for sorting applications, and sorting networks like Odd-Even Merge and Bitonic Sort offer the optimal algorithmic architectures.
Metadata
- Available format(s)
PDF- Category
- Implementation
- Publication info
- Preprint.
- History
- 2026-07-21: last updated
- 2026-07-21: published
- Short URL
- https://ia.cr/2026/1495
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/1495,
author = {Omar Ahmed and Rostin Shokri and Nektarios Georgios Tsoutsos},
title = {Oblivious Sorting under Fully Homomorphic Encryption: A Comprehensive Survey and Performance Analysis},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1495},
year = {2026},
url = {https://eprint.iacr.org/2026/1495}
}