Abstract
This paper introduces Secure Data Exchange (SDE), a practical framework designed to facilitate a secure marketplace for encrypted data in the cloud. By integrating Secure Multi-Party Computation (MPC) with a semi-honest cloud model, SDE enables third-party evaluators to perform complex computations—such as statistical tests and machine learning—on encrypted datasets without compromising data privacy. The protocol utilizes a novel Three-party Oblivious Receiver OT extension (OROT-e) to ensure data integrity and authorization while maintaining storage efficiency comparable to standard AES encryption. Experimental results demonstrate near-native performance for large-scale statistical analysis and practical runtimes for machine learning tasks, offering a scalable solution for private data collaboration.
Introduction
Cloud storage has become the backbone of modern data management, yet it presents a persistent "utility vs. privacy" dilemma. To perform meaningful analysis, such as training machine learning models or conducting multi-institutional medical research, data must typically be decrypted by the cloud provider, exposing it to potential breaches. Existing cryptographic solutions often fall short of practical requirements: Fully Homomorphic Encryption (FHE) remains computationally prohibitive, and standard Multi-Party Computation (MPC) usually requires all data owners to remain online during the entire computation process, which is unfeasible for large-scale, asynchronous cloud environments.
This research presents the Secure Data Exchange (SDE) protocol, a system that allows data owners to upload encrypted data once and authorize multiple private computations by third parties over time. By leveraging a semi-honest cloud model, SDE achieves high efficiency and low storage overhead, effectively creating a secure marketplace for data analysis.
The SDE Framework
The SDE protocol is built upon a novel adaptation of Yao’s Garbled Circuits within a server-aided setting. The architecture involves three primary stakeholders:
- Data Owners ($P_i$): Entities that encrypt their data using standard AES-CTR and upload it to the cloud.
- Cloud Service ($C$): A provider that stores the encrypted data and assists in the computation by acting as the "garbler" of the circuit.
- Evaluator ($Q$): A third party authorized to run a specific computation on the data and receive the final result.
Technical Innovations
The primary technical contribution of this work is the Three-party Oblivious Receiver OT extension (OROT-e). In traditional MPC, a malicious evaluator might attempt to use unauthorized inputs. OROT-e prevents this by forcing the Evaluator to use the specific data authorized by the owner. The Data Owner performs a one-time offline phase to commit to the cryptographic state of their data. Subsequently, they only need to send a 128-bit key to the Evaluator to authorize a specific computation, allowing the owner to remain offline during the heavy lifting.
To ensure storage efficiency, SDE stores data as standard AES-CTR ciphertexts rather than the bulky "wire labels" used in previous MPC iterations. This keeps storage costs identical to standard encrypted cloud storage. Furthermore, the protocol utilizes Merkle trees of commitments to enable random access, allowing the Evaluator to prove they are accessing the correct subset of a massive database without processing the entire file.
Experimental Evaluation
The authors evaluated the SDE protocol using synthetic datasets across various scenarios, testing performance in both Local Area Network (LAN) and Wide Area Network (WAN) environments.
Statistical Analysis
- Anova Test: In a simulation involving four hospitals and approximately 16.7 million patient records, the protocol completed the statistical comparison in just 0.25 seconds (LAN) and under 2 seconds (WAN). The total communication overhead for this massive dataset was remarkably low at 20 MB.
- Chi-Squared Test: For datasets containing $2^{14}$ records, the computation was completed in approximately 71 seconds in a LAN setting.
Machine Learning
The protocol was also tested on a Ridge Regression task involving three participants with datasets of 1 million records (24 features each). Training the model took approximately 6.5 hours. While significantly slower than plaintext computation, this represents a practical timeframe for high-value, private data analysis that was previously impossible to perform securely at this scale.
Discussion and Limitations
The efficiency of SDE relies on the "Semi-Honest Cloud" assumption. The system assumes that major cloud providers (e.g., AWS, Google, Azure) will follow the protocol correctly and will not collude with the Evaluator. While this is a realistic risk model for many business applications, the security of the system collapses if collusion occurs.
Additionally, the current implementation of random access via Merkle trees may leak access patterns (i.e., which parts of the database are being queried). To mitigate this, future iterations could incorporate Oblivious RAM (ORAM), though this would introduce significant computational overhead. Finally, the current protocol does not detect "active malicious" behavior by the cloud (such as providing a garbled circuit that computes the wrong function) without the use of "cut-and-choose" techniques, which would currently result in a ~40x performance penalty.
Conclusion
Secure Data Exchange provides a scalable, efficient framework for private data computation in the cloud. By decoupling storage from computation and minimizing the required online presence of data owners, SDE moves closer to a viable "secure marketplace" where sensitive data can be analyzed without ever being exposed in the clear.
Summary updated