Paper 2026/1495
Oblivious Sorting under Fully Homomorphic Encryption: A Comprehensive Survey and Performance Analysis
, University of Delaware, University of Delaware, University of DelawareAbstract
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.
- Keywords
- Fully Homomorphic EncryptionPrivacy-Preserving ComputationOblivious SortingAsymptotic Analysis
- Contact author(s)
- tsoutsos @ udel edu
- History
- 2026-07-25: approved
- 2026-07-21: received
- See all versions
- Short URL
- https://ia.cr/2026/1495
- License
-
CC BY
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}
}
