Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data

Foteini Baldimtsi, Olga Ohrimenko

Abstract

As data outsourcing to cloud environments grows, the need for privacy-preserving computation becomes critical. This paper introduces a novel protocol for sorting encrypted data and performing ranked multi-keyword searches without revealing plaintext values or sorted orders to service providers. By combining additively homomorphic encryption with data-independent sorting networks in a two-party non-collusion model, the authors achieve a practical balance between security and performance. The system supports relevance-based ranking (tf-idf) with $O(N \log^2 N)$ complexity, significantly outperforming fully homomorphic encryption approaches.

Introduction: The Privacy-Utility Trade-off

The fundamental challenge in cloud computing is performing complex operations, such as sorting search results by relevance, while maintaining data confidentiality. Existing solutions often fall into two extremes: Order-Preserving Encryption (OPE), which is efficient but leaks relative order, and Fully Homomorphic Encryption (FHE), which is theoretically robust but computationally impractical. This work bridges this gap by enabling "private outsourced sorting"—allowing a server to sort encrypted records without learning the plaintext values, the initial order, or the final sorted permutation.

System Architecture: The Two-Party Model

The proposed framework utilizes a two-party model involving a cloud server ($S_1$) and a secure coprocessor ($S_2$). In this "Brad and Angelina" setup, $S_1$ stores the encrypted data and performs the bulk of the homomorphic computations, while $S_2$ holds the decryption keys and provides minimal assistance for specific operations.

High-level architecture of the private outsourced sorting and searching system.

The security of this model rests on the assumption that $S_1$ and $S_2$ do not collude. By separating the data storage from the decryption capability, the system ensures that neither party can independently access the plaintext information.

Methodology: Private Sorting and Sub-protocols

The core of the system is a suite of cryptographic sub-protocols designed to perform oblivious operations.

Key Techniques

  1. Generalized Paillier Cryptosystem: The protocol uses a layered version of Paillier encryption. This allows a ciphertext to be treated as a plaintext for a second layer of encryption, facilitating complex homomorphic operations.
  2. Batcher’s Sorting Network: To prevent information leakage through execution patterns, the authors employ Batcher’s bitonic sort. Unlike data-dependent algorithms like Quicksort, bitonic sort is data-independent; the sequence of comparisons remains fixed regardless of the input values.
  3. Oblivious Sub-protocols: The system relies on several specialized protocols to handle encrypted comparisons and selections.
Summary of the core sub-protocols used for private data processing.

As shown in the table above, protocols like EncCompare and EncSelect allow the servers to compare encrypted values and swap them without knowing if a swap actually occurred. StripEnc is used to securely remove layers of encryption during the process.

Applications: Ranked Searchable Encryption

A primary application of this private sort is Multi-keyword Ranked Searchable Encryption (MRSE). By using homomorphic addition to aggregate encrypted relevance scores (such as tf-idf) and subsequently applying the private sort, the system can return ranked search results. This is the first system capable of ranking results by relevance without the server seeing the scores or the underlying keywords.

Performance and Security Analysis

The private sorting protocol achieves a computational and communication complexity of $O(N \log^2 N)$. While this introduces a polylogarithmic overhead compared to cleartext sorting ($O(N \log N)$), it remains orders of magnitude more efficient than FHE-based alternatives.

Security is formally proven in the "honest-but-curious" model. Provided the non-collusion assumption holds, neither the server nor the coprocessor learns anything about the plaintext data or the sorting permutation.

Conclusion and Future Work

This research provides a practical framework for private data processing in the cloud. While the non-collusion assumption and potential access pattern leakage are noted limitations, the authors suggest that integrating Oblivious RAM (ORAM) could further enhance privacy. Future directions include extending this framework to other database operations, such as joins on sorted tables and top-k query processing.

Summary updated

BibTeX
@article{baldimtsi2014sorting,
  author = {Foteini Baldimtsi and Olga Ohrimenko},
  title = {{Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
  url = {https://openreview.net/forum?id=KP8NAdorOT},
}
Figure