Privacy Preserving Computation in the Non-Colluding Two-Server Model

42 concepts38 papers1 proposal

In traditional cloud computing, we face a binary choice: either trust a single provider with our raw data or use heavy cryptographic tools like Fully Homomorphic Encryption (FHE) that are often too slow for real-world applications. The non-colluding two-server model offers a middle ground. By splitting trust between two independent entities, researchers have developed protocols that are orders of magnitude faster than single-server encryption while maintaining rigorous privacy guarantees.

The Core Mechanism: Splitting the Brain

The intuition behind this model is a "separation of concerns." Instead of one server holding both the data and the power to see it, the system is split into two roles. Typically, one entity acts as the Data Host (storing encrypted or shared data), while the other acts as a Cryptographic Assistant or Key Manager.

As long as these two servers do not collude—meaning they do not share their internal states or secrets with each other—neither can reconstruct the original information. Baldimtsi et al. demonstrated this by separating the storage of encrypted data from the possession of decryption keys, allowing for complex operations like private ranked search without revealing the underlying values.

This architecture is flexible. In the context of auctions, Chen et al. and Zhong et al. utilize an auctioneer and an independent agent to process bids. By distributing the computation, the auctioneer never learns the participants' sensitive bid values, yet the final result remains mathematically provable and economically truthful.

Why It Works: Efficiency Through Lightweight Primitives

The primary reason this model is gaining traction is performance. Single-server privacy often relies on FHE, which requires performing complex math on "noisy" ciphertexts. In contrast, the two-server model allows for much lighter cryptographic building blocks:

  1. Additive Secret Sharing: Instead of encrypting a number, a user splits it into two random-looking "shares." One share goes to Server A, the other to Server B. Only by adding them together can the original number be revealed. Zheng et al. used this to perform skyline queries, achieving an 813x speedup over previous methods.
  2. Linearly Homomorphic Encryption (LHE): By using encryption that only supports addition, and letting a second server handle the "masking" of intermediate results, researchers can avoid the overhead of full homomorphy. Giacomelli et al. achieved a 25x speedup in training ridge regression models using this "masking trick."
  3. Garbled Circuits: In this setup, one server "garbles" a computational circuit while the other executes it. Gilad-Bachrach et al. and Jin et al. show that this allows for a "secure marketplace" where data can be analyzed privately and persistently.

Scaling to Complex Analytics

The two-server model is not limited to simple arithmetic; it has been successfully applied to high-dimensional data and machine learning.

For instance, in Federated Learning (FL), where multiple clients train a model together, the two-server model prevents the central aggregator from seeing individual updates. Wang et al. and Chen et al. have shown that by using a second server for key management or secure aggregation, the system can remain robust even if clients drop out or attempt to "poison" the model.

Similarly, for large-scale data analysis, Gascón et al. and Cheu et al. developed protocols for computing sparse histograms and detecting "heavy hitters" (popular items) in massive datasets. Their approach ensures that individual user inputs remain hidden while the aggregate trends are revealed to the analyst.

The Non-Collusion Trade-off

The strength of this model is also its primary assumption: non-collusion. The security holds only as long as the two servers are operated by different entities with no incentive to cooperate maliciously.

To bolster this, researchers often combine the two-server architecture with Differential Privacy (DP). Chowdhury et al. introduced Crypte, which uses two untrusted servers to achieve the accuracy of centralized DP without a single trusted curator. Furthermore, Vadhan et al. have studied how these interactive protocols behave when an analyst queries multiple systems concurrently, ensuring that the privacy "budget" is managed correctly across the distributed architecture.

By moving from a "trust one" to a "trust they don't both cheat" model, these architectures provide a practical path forward for private, high-performance cloud computing.

Key Foundational Work

Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data (2014) — contributed 2 concept elements to this direction.
PS-TRUST: Provably Secure Solution for Truthful Double Spectrum Auctions (2013) — contributed 1 concept elements to this direction.
Private Database Queries Using Somewhat Homomorphic Encryption (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_distributed_trust_model_39607d3d,
  title = {distributed trust model},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-trust-model/rdr_39607d3d532843cf9c772bbe115138e8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_distributed_trust_model_39607d3d_v1,
  title = {distributed trust model},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-trust-model/rdr_39607d3d532843cf9c772bbe115138e8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake