Efficient Ranking, Order Statistics, and Sorting under CKKS

Efficient Ranking, Order Statistics, and Sorting under CKKS

Speakers: Federico Mazzone

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=R-ZtdCEggYc

Overview

This talk, presented by Federico Mazzone from the University of Trento, introduces novel algorithms for efficiently performing ranking, order statistics, and sorting operations on encrypted data using the CKKS (Cheon-Kim-Kim-Song) homomorphic encryption scheme. In an era where privacy-sensitive data is increasingly processed in outsourced cloud environments, homomorphic encryption (FHE) offers a compelling solution by allowing computations to be performed directly on encrypted data without prior decryption. This eliminates the need for the server to ever see the plaintext, thereby preserving data confidentiality.

However, a significant challenge in FHE, particularly with schemes like CKKS, lies in the computational expense of certain fundamental operations, most notably comparisons. Traditional comparison-based algorithms, such as sorting or finding minimum/maximum values, become bottlenecks due to the high "multiplicative depth" required for approximating comparisons using polynomials. Mazzone's work directly addresses this by proposing a paradigm shift that exploits the Single Instruction, Multiple Data (SIMD) capabilities inherent in CKKS, enabling these operations to be performed with a constant comparison depth, a marked improvement over prior state-of-the-art methods which typically incurred a logarithmic squared depth.

The significance of this research is profound, particularly for applications dealing with privacy-sensitive data where comparison-heavy computations are common. While existing FHE sorting methods often mirror plaintext complexities, their practical performance under FHE is hampered by the cost of comparisons. By achieving constant comparison depth, this work offers substantial speedups for small to medium-sized datasets, making previously impractical privacy-preserving computations feasible. This has direct implications for fields like machine learning, where tasks such as clustering or change point detection often involve ranking or finding extrema over small vectors, allowing for more secure and private data analysis.

Background

▶ Watch: Introduction to homomorphic encryption and comparison challenges (0:00)

The concept of homomorphic encryption (FHE) underpins this entire discussion. In a typical outsourced computation scenario, a client possesses sensitive data they wish to process on a cloud server. Without FHE, the client would either have to trust the server with their plaintext data or perform the computation locally, negating the benefits of cloud outsourcing. FHE provides a cryptographic solution: the client encrypts their data using a public key, sends the ciphertext to the server, which then performs computations directly on this encrypted data. The server returns the encrypted result to the client, who can then decrypt it using their secret key. The server never learns the original data or the result in plaintext.

The specific FHE scheme considered in this work is CKKS, an approximate homomorphic encryption scheme designed for computations on vectors of real or complex numbers, specifically floating-point values. A key characteristic of CKKS is its SIMD nature: an entire vector of values is encrypted into a single ciphertext, and operations are performed component-wise across all elements of the vector simultaneously. CKKS natively supports three fundamental operations on ciphertexts:

1. Component-wise addition: Adding two ciphertexts results in a ciphertext encrypting the sum of their respective plaintext vectors.
2. Component-wise multiplication: Multiplying two ciphertexts results in a ciphertext encrypting the product of their respective plaintext vectors.
3. Vector rotation: Shifting the elements of the encrypted vector by a plaintext-specified index.

Any operation not directly supported by these three primitives must be expressed as a composition of them. This is where the primary challenge for comparison-based algorithms arises. A simple comparison, such as determining if x > y, is not a native CKKS operation. Instead, it must be approximated. The standard approach is to represent the comparison x > y as evaluating the sign function of their difference, sign(x - y). The sign function, being non-linear, is then approximated using a polynomial, often a Chabyshev approximation. The higher the degree of the polynomial, the more accurate the approximation, but also the more multiplications and additions are required to evaluate it homomorphically. This directly translates to a higher multiplicative depth of the FHE circuit, making the comparison computationally very expensive.

This high cost of homomorphic comparisons is a significant bottleneck for many FHE algorithms, particularly those that rely heavily on comparisons, such as sorting, finding minimum or maximum values, or calculating ranking and order statistics. Unlike plaintext algorithms, where a comparison is a constant-time operation, under CKKS, it can be the dominant cost factor. Furthermore, directly transporting plaintext algorithms (like merge sort, quick sort, or bitonic sort) to work with CKKS is inefficient because CKKS operates on vectors, not individual values. Comparing two individual values would incur the same cost as comparing two entire vectors. Existing FHE sorting solutions, while often having similar overall complexities to their plaintext counterparts (e.g., O(N log N) or O(N log^2 N)), are primarily bottlenecked by their comparison depth, which measures the longest sequence of dependent comparisons that must be executed sequentially. State-of-the-art FHE sorting algorithms typically exhibit a comparison depth of O(log^2 N). The explicit goal of this research is to significantly reduce this comparison depth for comparison-based algorithms under FHE, ideally to a constant value.

Key Findings

▶ Watch: Current FHE sorting limitations; goal: constant comparison depth (4:30)

The central contribution of this work is the design and implementation of novel algorithms for ranking, extracting order statistics, and sorting vectors under CKKS with a constant comparison depth. This represents a substantial improvement over prior approaches, which typically incurred a logarithmic squared comparison depth (O(log^2 N)).

The core idea behind this breakthrough is to ingeniously exploit the SIMD capabilities of the CKKS scheme. Instead of directly comparing individual elements (which would be inefficient), the proposed method transforms the input vector into two specific re-encodings. These encodings are constructed such that a single SIMD comparison operation between them simultaneously yields information about all possible pairwise comparisons between elements of the original input vector.

Specifically, the key findings include:

• Constant Comparison Depth: The developed algorithms achieve a comparison depth of O(1), making them significantly more efficient for comparison-heavy tasks in FHE.
• Novel Encoding Strategy: The technique relies on transforming an input vector X into two matrices: one where the vector X is replicated entirely across rows, and another where each element of X is replicated across columns. A single SIMD comparison between these two structures then provides the necessary pairwise comparison results.
• Efficiency for Small Inputs: For applications with small input vector sizes (where the square of the number of elements N fits within a single CKKS ciphertext's slot capacity, i.e., N <= sqrt(number_of_slots)), these algorithms demonstrate considerable speedups compared to existing solutions.
• Scalability Limitations and Parallelization Potential: While highly efficient for small inputs, the solution faces scalability challenges when input sizes exceed the single-ciphertext capacity. However, its constant comparison depth makes it highly amenable to parallelization across multiple ciphertexts or using hardware accelerators like GPUs, potentially extending its beneficial range.
• Practical Applications: The approach is particularly well-suited for machine learning tasks where computations on small vectors are common, such as k-clustering (argmin over K centroids) or change point detection in time series (ranking over small sliding windows).

Technical Deep Dive

▶ Watch: Core idea: exploit SIMD for efficient all-pairs comparison (6:00)

The efficiency of the proposed algorithms hinges on a clever exploitation of CKKS's SIMD nature and its native operations. As previously established, CKKS natively supports component-wise addition, component-wise multiplication, and vector rotation. Any other operation, especially comparisons, must be approximated using polynomials, leading to high multiplicative depth. The goal is to minimize the number of such costly polynomial evaluations in sequence.

The foundation of the new approach involves working with encrypted matrices, even though CKKS strictly operates on vectors. To achieve this, a matrix is encoded into a single vector using a row-wise encoding, where rows are concatenated sequentially. This allows standard matrix operations to be simulated using CKKS vector operations. The speakers describe how several useful matrix operations can be implemented recursively using only log N additions and rotations (where N is the dimension of the matrix):

• Summing rows or columns and storing the result in the first row/column.
• Transposing a row vector into a column vector and vice versa.
• Replicating a row vector's values across all other rows.
• Replicating a column vector's values across all other columns.

These matrix operations are crucial for constructing the specific re-encodings required for the constant-depth comparison.

The Ranking Algorithm

The ranking algorithm is the core component, as it forms the basis for order statistics and sorting. Given an input vector X = [X1, X2, ..., XN], the objective is to compute the rank of each element, i.e., its position if the vector were sorted. The main strategy is to count, for each element Xi, how many other elements it is greater than.

Here's a detailed breakdown of the steps:

1. Matrix Encoding: The input vector X is first encoded as the first row of a new N x N matrix. For example, if X = [20, 30, 10, 40], the initial matrix (conceptually, as it's still a vector in ciphertext) would be:

(Other rows are initially zero or irrelevant for this step).

1. First Re-encoding (Replicate Whole Vector): A new matrix M_replicated_whole is created where the original input vector X is replicated across all rows. This is achieved using the "replicate values in other rows" matrix operation.

1. Second Re-encoding (Replicate Individual Values): Another matrix M_replicated_blocks is created where each individual value from X is replicated across a corresponding column. This involves two steps: first, transposing the original vector X into a column vector, and then using the "replicate values in other columns" matrix operation.

1. Single SIMD Comparison: Now, a single component-wise comparison operation is performed between M_replicated_whole and M_replicated_blocks. This comparison is the costly polynomial approximation, but it's executed only once on the entire N x N matrix structure. The result is a new matrix where each cell (i, j) contains the outcome of comparing Xi (from M_replicated_blocks) with Xj (from M_replicated_whole).

The approximated comparison function yields:

• 1 if Xi > Xj
• 0 if Xi < Xj
• 0.5 if Xi == Xj (a characteristic of the polynomial approximation)

For our example X = [20, 30, 10, 40]:

1. Compute Ranks: To get the rank of each element Xi, we sum the values in the i-th row of the resulting comparison matrix. Each 1 indicates Xi is greater than another element, and 0.5 indicates equality with itself.

• For X1 (20): 0.5 + 0 + 1 + 0 = 1.5. To adjust for the 0.5 self-comparison, we subtract 0.5 and add 1 (if we want 1-based ranking). Or simply, the count of elements it's strictly greater than, plus one for itself if equal. If X has unique elements, the rank is simply the sum of 1s. For non-unique elements, a more sophisticated adjustment is needed, but the principle holds. In the talk, the speaker implies a direct mapping: 1.5 for X1 (20) means rank 1 (if 0-indexed) or 2 (if 1-indexed after sorting [10, 20, 30, 40]). Let's assume the sum S_i directly gives the number of elements Xi is bigger than plus 0.5 if Xi is unique. For sorted [10, 20, 30, 40], ranks are 0, 1, 2, 3.
• X1=20: 0.5 + 0 + 1 + 0 = 1.5. The element 10 is smaller than 20. Rank is 1 (0-indexed).
• X2=30: 1 + 0.5 + 1 + 0 = 2.5. Elements 10, 20 are smaller than 30. Rank is 2.
• X3=10: 0 + 0 + 0.5 + 0 = 0.5. No elements smaller than 10. Rank is 0.
• X4=40: 1 + 1 + 1 + 0.5 = 3.5. Elements 10, 20, 30 are smaller than 40. Rank is 3.

By summing over the rows (using a matrix operation), we obtain the full ranking vector: [1.5, 2.5, 0.5, 3.5]. After adjusting for the 0.5, these correspond to the 0-indexed ranks [1, 2, 0, 3] for [20, 30, 10, 40].

Order Statistics

Once the ranking vector is computed, extracting order statistics (e.g., minimum, maximum, median) becomes straightforward. To find the k-th order statistic (e.g., maximum, which is the N-th order statistic), an indicator function centered around the target rank k is applied to the ranking vector. Similar to the comparison function, this indicator function (valued 1 in a neighborhood of k and 0 otherwise) is approximated using a polynomial, incurring a similar cost. The output of this operation is a one-hot encoding of the position of the k-th order statistic. For example, to find the maximum in [20, 30, 10, 40], which has rank 3.5 (adjusted to 3 for 0-indexed), the indicator function centered around 3 would produce [0, 0, 0, 1], indicating the maximum is at the last position.

Sorting

Sorting is essentially equivalent to extracting all N order statistics simultaneously in the correct order. The constant comparison depth property means that extracting all these statistics can be highly parallelized. The remaining slots within the encrypted matrix can be leveraged to extract multiple order statistics in parallel with only minor overhead compared to extracting a single one. This allows for sorting the entire vector with the same constant comparison depth.

Scalability and Limitations

A crucial aspect discussed is the scalability. The efficiency of this method is heavily dependent on the assumption that the input vector's size N is small enough such that N^2 (the size of the comparison matrix) fits within the number of slots available in a single CKKS ciphertext. Mathematically, this means N <= sqrt(number_of_slots_in_ciphertext). If this limit is exceeded, the original vector must be encoded into multiple ciphertexts, which introduces scalability issues and diminishes the performance advantage.

Performance charts presented in the talk illustrate this point: for small input sizes, the proposed solution (shown in green) is significantly faster than existing solutions (shown in blue). However, beyond a certain threshold, the existing solutions catch up or even surpass the new method. This is because the proposed solution has a very small constant cost for operations within a single ciphertext, but its performance degrades when multiple ciphertexts are required due to the overhead of inter-ciphertext operations.

Despite this limitation, the constant comparison depth offers a significant advantage in parallelization. If a system has multiple cores or a GPU, the computations involving multiple ciphertexts can be executed in parallel, effectively pushing the threshold at which the new solution remains beneficial to much larger input sizes. This makes the approach highly suitable for specific use cases where input vectors are inherently small but privacy is paramount.

Demo / Proof of Concept

▶ Watch: Efficient operations on encrypted matrices using CKKS (6:20)

While a live code demonstration was not explicitly part of the presentation, the speakers provided compelling performance charts to demonstrate the efficacy and limitations of their proposed algorithms. These charts graphically compared the runtime of their solution for computing the maximum element and for sorting, against existing state-of-the-art FHE solutions, across an increasing number of vector points.

The visual evidence clearly showed that for small input sizes, the new algorithms (represented by the green line) were "sensibly faster" than previous methods (blue line). This empirical data served as a strong proof of concept for the theoretical claims of constant comparison depth translating into practical speedups. The charts also transparently highlighted the scalability threshold, where the performance advantage diminished as the number of elements exceeded the capacity of a single ciphertext, validating the discussed limitations. The existence of a public repository on GitHub, mentioned at the end of the talk, further implies that the code implementation is available for review and reproduction, acting as an implicit demonstration of the practical realization of these algorithms.

Defensive Implications

▶ Watch: Step-by-step ranking algorithm, the core of the approach (8:00)

The defensive implications of this research are not about traditional cybersecurity measures like patching vulnerabilities or detecting malware. Instead, they lie squarely in the realm of privacy-preserving computation and data confidentiality. By making fundamental operations like ranking, order statistics, and sorting significantly more efficient under homomorphic encryption, this work empowers organizations to process sensitive data in outsourced environments without exposing it to the cloud provider.

Here's how this translates into defensive benefits:

• Enhanced Data Confidentiality: The primary benefit is that data remains encrypted throughout its lifecycle – in transit, at rest, and most crucially, during computation. This drastically reduces the attack surface for data breaches, as even if a server is compromised, the attackers would only gain access to unreadable ciphertexts.
• Compliance with Privacy Regulations: Regulations like GDPR, CCPA, and HIPAA mandate strong privacy protections for personal and health data. FHE, especially with performance improvements like those presented, offers a robust technical solution to meet these compliance requirements by ensuring that sensitive data never leaves the client's control in plaintext.
• Secure Outsourced Analytics: Many machine learning and data analytics tasks require operations like sorting, finding min/max, or ranking. With this improved FHE capability, companies can outsource these computationally intensive analytics to cloud providers without compromising the privacy of their datasets. This enables new paradigms for secure data collaboration and analysis across different entities.
• Robustness Against Insider Threats: Even trusted cloud administrators or employees with access to server infrastructure cannot infer sensitive information from encrypted data, mitigating the risk of insider threats.
• Applications in Sensitive Domains: The talk specifically highlights applications in machine learning (e.g., k-clustering, change point detection in time series) where privacy is critical. In healthcare, for instance, sorting patient records by certain metrics or finding specific health statistics can now be done while preserving individual patient privacy. In finance, sensitive transaction data can be analyzed for fraud detection or market trends without exposing individual transactions.
• Enabling New Secure Services: The ability to perform complex, comparison-based computations efficiently on encrypted data opens the door for entirely new classes of privacy-preserving services and applications that were previously impractical due to the performance overhead of FHE. This fosters innovation in secure computation.

In essence, the defensive implication is the strengthening of the "confidentiality" pillar of cybersecurity, particularly for data in use, by providing a practical pathway for secure outsourced computation on sensitive information.

Key Takeaways

• Homomorphic Encryption (FHE), specifically the CKKS scheme, enables computations on encrypted vectors of floating-point values, crucial for privacy-preserving outsourced computation.
• Traditional comparison-based algorithms (sorting, min/max, ranking) are a major bottleneck in FHE due to the high multiplicative depth required for polynomial approximation of comparisons.
• New algorithms achieve a constant comparison depth for ranking, order statistics, and sorting under CKKS, a significant improvement over prior O(log^2 N) methods.
• The efficiency gain is realized by ingeniously exploiting CKKS's SIMD capabilities through novel matrix re-encodings, allowing a single SIMD comparison to yield all pairwise comparison results.
• The proposed solution offers substantial speedups for small input sizes (where N <= sqrt(number_of_slots_in_ciphertext)), making certain privacy-preserving computations practically feasible.
• This work has direct applications in machine learning (e.g., k-clustering, change point detection) and other domains where privacy is paramount and operations on small vectors are common.

About the Speaker(s)

Federico Mazzone is a researcher from the University of Trento. His work focuses on advancing the state-of-the-art in homomorphic encryption, particularly in developing efficient algorithms for fundamental data processing tasks under FHE. His presentation at USENIX Security highlights his expertise in cryptographic schemes like CKKS and their practical application to real-world privacy-preserving computation challenges.