University of Twente Student Theses
Towards Efficient Order Statistics in CKKS : A Study of Robustness and Efficiency Through Non-Continuous Function Approximation.
Rikkers, V. (2025) Towards Efficient Order Statistics in CKKS : A Study of Robustness and Efficiency Through Non-Continuous Function Approximation.
This is the latest version of this item.
|
PDF
2MB |
| Abstract: | This thesis explores methods to improve ranking, order statistics, and sorting algorithms within the CKKS encryption scheme, with a focus on approximating discontinuous functions such as the sign function. Fully Homomorphic Encryption (FHE) ensures data privacy by enabling computations directly on encrypted data, but its high computational complexity poses significant challenges. To address these challenges, this study analyzes the balance between accuracy and computational efficiency in two key approximation techniques: the Tchebycheff and Composite Minimax approximation algorithms. Our experimental results show that composite minimax polynomials outperform polynomials created using Tchebycheff approximation in memory usage and computational efficiency, making them more suitable for high-performance applications. To increase their robustness against approximation errors, this thesis also presents a revised algorithm for determining the (arg)min and (arg)max of a vector, which substitutes the usage of the comparison function with the usage of the max or min function. Our findings indicate that using the max or min function instead of the comparison function improves robustness against approximation errors when determining the smallest value in a vector. However, the opposite is the case when computing the argmin, as then the robustness decreases. These results contribute to the development of more robust and efficient privacy-preserving algorithms for the CKKS encryption scheme, with potential applications in secure cloud computing, encrypted machine learning, and privacy-conscious data analysis. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics, 54 computer science |
| Programme: | Computer Science MSc (60300) |
| Link to this item: | https://purl.utwente.nl/essays/105233 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page