CoVault: Secure, Scalable Analytics of Personal Data

arXiv:2208.03784 · cs.CR, cs.DC · Submitted 2022-08-07 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "CoVault: Secure, Scalable Analytics of Personal Data".

Elias: Here's the gist of the paper. The paper presents CoVault, a secure analytics platform designed to enable large-scale analytics on sensitive personal data, such as mobility, financial, and health information, by addressing current limitations in securing this data for broad analysis.

Nadia: The primary challenge identified is the lack of an analytics platform capable of providing transparent, technical security—ideally through decentralized trust—to handle numerous distinct data sources and billions of records with acceptable query latencies.

Elias: CoVault bridges this gap by combining Secure Multi-Party Computation (MPC) with Trusted Execution Environment (TEE)-based delegation of trust to execute approved queries on encrypted data contributed by individuals within a single datacenter.

Nadia: CoVault supports complete (non-sampled) query results, operates across many data sources, and scales to big datasets utilizing the resources of a single data center.

Paper summary: Nadia: So we're looking at this paper called CoVault: Secure, Scalable Analytics of Personal Data. It tackles the problem that we have a lot of sensitive personal data—mobility, finances, health stuff—but there isn't really a platform out there that can secure it through transparent technical means.

Elias: Exactly. The authors say the main challenge is finding an analytics platform that can handle millions of distinct data sources and billions of records while running queries with acceptable speeds. They propose CoVault as a way to bridge that gap by combining secure multi-party computation, or MPC, with trusted execution environment, or TEE-based delegation of trust.

Priya: So what they claim is this system lets individuals contribute encrypted data shares to a query class defined by Q D te and then authorized analysts run those queries using a Query operation. It aims to give distributed trust and malicious security while improving performance, processing queries seven to over one hundred times faster than existing MPC-based platforms for small datasets and few sources.

Nadia: That speed improvement sounds pretty significant for real-world applications, especially when dealing with big datasets in a single data center setup. What's the core of how they build this system?

Elias: The core design uses secret sharing, MPC, and TEEs to achieve this. They have two main constructions: the strawman construction and a full construction. The full construction modifies the strawman by executing each of the parties inside a TEE of a different, independent design.

Priya: That sounds like they are trying to solve the problem of colocation while still getting those benefits, which is tough when you have many data sources involved. How do they ensure trust in these different TEEs?

Elias: Security is established through MPC with a three-of-n active security across TEE technologies from n different vendors, and these vendors are attested by community experts. This setup eliminates the need for physical separation between the data sources because of how they set up the delegation.

Nadia: So if I'm a data source, I contribute my encrypted shares to this API, and then someone authorized runs a query on that encrypted data? What does that actually mean for someone just listening to the show?

Elias: It means the system handles complete, non-sampled query results across many sources using only the resources of a single datacenter. They use MapReduce for running SQL filter groupby aggregate queries by converting them into small map and reduce circuits executed in two-party computation, or 2PC <ref:2208.03784#pg1>.

Priya: And for data that depends on the data itself, like filter groupby aggregate queries, they use an oblivious data retrieval scheme on previously shuffled tables to stop any secret leakage through how the database is accessed. That sounds like a specific way to handle access patterns.

Nadia: But what about scale? The paper mentions this scenario involving a country of eighty million people, and it uses a core pair for every twenty thousand people. What's the performance like at that level?

Elias: For that scale, running a complex query can take approximately two point two four hours on two core pairs in the setup described. A big advantage they point out is that because CoVault stays in a single datacenter, its ability to scale to big data isn't limited by wide area network bandwidth.

Priya: So for me, what this means is that we can do complex analytics on very sensitive health or financial data at this scale without worrying about the data having to travel across the internet constantly. But what are the specific technical hurdles they admit they have?

Nadia: The paper outlines their contributions, which include an MPC configuration where each party executes in a different, independent TEE to eliminate physical separation requirements. They also detail techniques for delegating trust to TEE-encapsulated parties while ensuring authentication, attestation, input integrity, confidentiality, and selective forward consent.

Elias: And they also designed CoVault as a secure analytics platform that scales to big data limited only by datacenter resources. On the technical side, they introduced a provably secure authenticated secret sharing scheme and an actively secure two-party computation protocol.

Priya: So what's the real impact of this for our world? If we can safely delegate control over encrypted data to colocated MPC parties, each running in a different TEE with malicious security, what does that unlock for personal privacy?

Nadia: It means individual data sources can safely give up some control over their encrypted information to these colocated parties. This enables big data analytics with distributed trust and malicious security.

Elias: The paper concludes that CoVault allows individual data sources to safely delegate control over their encrypted data to MPC parties running in different TEEs, which is a way to achieve big data analytics while maintaining distributed trust and malicious security.

Conclusion: Nadia: So we’ve talked about CoVault, this system designed to let you run big data analytics on your personal health or financial stuff securely using MPC and TEEs across a single data center.

Elias: Yeah, the authors are working on making this transparently secure through decentralized trust mechanisms. They’re proposing a way for individuals to share encrypted data with authorized analysts without having to worry about the security of the entire analysis process.

Nadia: It sounds like they’ve built something that handles massive amounts of data—billions of records—while keeping everything contained within one place, which is a big deal because usually, those kinds of distributed systems choke on network traffic.

Priya: From my angle, it’s about how the data actually shows up. They claim this lets you get complete results from all your sources without needing to sample anything out for privacy reasons. I want to see what those results actually look like before we trust the system that generated them.

Elias: Exactly, and they’re using a lot of technical mechanisms to make sure that delegation of trust works properly across different vendors running the TEEs. They’ve got this three-of-n active security setup across different technologies, which is how they’re managing the risk there.

Nadia: So, what does this actually mean for the people whose data goes into CoVault? It sounds like it gives them a way to participate in analytics without completely exposing their raw information.

Priya: It means they get to use powerful analytical tools on their own data, but only within the strict rules of that MPC and TEE setup. The benefit is the capability; the caveat is knowing exactly what controls they’re handing over and how well those controls hold up under real attack scenarios.

Elias: The paper boils down to this idea: you can delegate control over your encrypted data to multiple parties running in different secure environments, achieving distributed trust for big data analytics. It’s less about hiding the data and more about securely using it while keeping the computation private.

Nadia: So, the title CoVault—secure analytics of personal data—really captures that idea of a vault for your information that lets you use it safely for analysis.

Elias: Right, and what's interesting is how they’ve designed the technical components to handle everything from secret sharing to the actual two-party computation protocol. That’s where the real engineering challenge lies in making sure those individual pieces fit together securely.

Priya: It certainly seems like a lot of moving parts, but if this works as claimed, it opens up possibilities for things that are currently too sensitive or too complex to analyze because of the security hurdles involved.

Nadia: Exactly. So while we’re still figuring out how cheaply and easily we can exploit these systems, the underlying concept is about making big data analytics possible in a way that respects individual privacy through this layered approach of MPC and TEEs.

Max Planck Institute for Software Systems (MPI-SWS) · Max Planck Institute for Security and Privacy (MPI-SP) · Instituto Superior Tecnico (ULisboa), INESC-ID · University of Maryland · ETH Zürich

cs.CR, cs.DC

Submitted: 2022-08-07

Updated: 2026-11-07

Comments: Update: match version published at USENIX Security 2025 + technical appendix. 31 pages (20-page main paper, including references; 11-page technical appendix)

Journal ref: In Proceedings of the 34th USENIX Security Symposium (USENIX Security 25), pp. 567-586, USENIX Association, 2025

Code: https://github.com/emptoolkit/emp-agmpc

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 100/100

The gist: The paper presents CoVault, a secure analytics platform designed to enable large-scale analytics on sensitive personal data, such as mobility, financial, and health information…

Key concepts

Secure Multi-Party Computation (MPC)
A cryptographic technique that allows several parties to jointly compute a function over their private inputs without revealing the individual inputs to each other. In CoVault, this lets analysts run queries on combined encrypted data securely.
Trusted Execution Environment (TEE)
A secure area within a computer's processor that creates an isolated environment for running code. Parties in CoVault execute their parts of the computation inside different TEEs, ensuring their data remains confidential and protected from other parties.
Strawman (S1) and Full Construction (S2)
These are two designs for implementing the system's API. Strawman uses secret sharing for privacy but requires physical separation. The Full construction enhances this by running each party inside a separate TEE, allowing them to be colocated while maintaining confidentiality and trust.
Oblivious Data Retrieval (ODR)
A technique used to prevent data leakage when querying shuffled tables. It ensures that an analyst can retrieve the correct information without learning which specific rows or columns were accessed, protecting secret patterns.

Terminology

Summary

The paper presents CoVault, a secure analytics platform designed to enable large-scale analytics on sensitive personal data, such as mobility, financial, and health information, by addressing current limitations in securing this data for broad analysis. p. 0

Where the paper says it

CoVault: Secure, Scalable Analytics of Personal Data Roberta De Viti1 , Isaac Sheff1 ∗ , Noemi Glaeser2,4, Baltasar Dinis3 , Rodrigo Rodrigues3 , Bobby Bhattacharjee4 , Anwar Hithnawi5 , Deepak Garg1 , and Peter Druschel1 1Max Planck Institute for Software Systems (MPI-SWS), Saarland Informatics Campus 2Max Planck Institute for Security and Privacy (MPI-SP) 3 Instituto Superior Tecnico (ULisboa), INESC-ID 4University of Maryland 5ETH Zürich Abstract Analytics on personal data, such as individuals’ mobility, financial, and health data can be of significant benefit to society. Such data is already collected by smartphones, apps and services today, but liberal societies have so far refrained from making it available for large-scale analytics.

The primary challenge identified is the lack of an analytics platform capable of providing transparent, technical security—ideally through decentralized trust—to handle numerous distinct data sources and billions of records with acceptable query latencies. p. 0
Where the paper says it

Such data is already collected by smartphones, apps and services today, but liberal societies have so far refrained from making it available for large-scale analytics. Arguably, this is due at least in part to the lack of an analytics platform that can secure data through transparent, technical means (ideally with decentralized trust), enforce source policies, handle millions of distinct data sources, and run queries on billions of records with acceptable query latencies.

CoVault bridges this gap by combining Secure Multi-Party Computation (MPC) with Trusted Execution Environment (TEE)-based delegation of trust to execute approved queries on encrypted data contributed by individuals within a single datacenter. p. 0
Where the paper says it

Arguably, this is due at least in part to the lack of an analytics platform that can secure data through transparent, technical means (ideally with decentralized trust), enforce source policies, handle millions of distinct data sources, and run queries on billions of records with acceptable query latencies. To bridge this gap, we present an analytics platform called CoVault, which combines secure multi-party computation (MPC) with trusted execution environment (TEE)-based delegation of trust to be able execute approved queries on encrypted data contributed by individuals within a datacenter to achieve the above properties.

CoVault supports complete (non-sampled) query results, operates across many data sources, and scales to big datasets utilizing the resources of a single data center. p. 1

Where the paper says it

In this paper, we present CoVault, a secure analytics platform that (1) supports complete (not sampled) query results (like cooperative analytics); (2) can operate on data from Table 1: CoVault versus state-of-the-art. System Federated analytics Cooperative analytics CoVault ( [65, 82]) ( [78]) Technology HE+MPC+ZKP MPC MPC+TEEs Malicious parties < 3% user devices m−1 of m aggregators 1 out of 2 TEEs Data sources Many individuals Few large aggregators Many individuals (offline) No No Yes Scaling ultimately Compute/network Wide-area network Resources of a limited by of user devices bandwidth/delay datacenter large numbers of individuals (like federated analytics); and (3) scales to big data sets by leveraging the resources and scalability of a single data center, while offering distributed trust and malicious security.

It achieves distributed trust and malicious security while offering performance improvements, processing queries 7 to over 100 times faster than existing MPC-based platforms for small datasets and few sources. p. 1
Where the paper says it

In this paper, we present CoVault, a secure analytics platform that (1) supports complete (not sampled) query results (like cooperative analytics); (2) can operate on data from Table 1: CoVault versus state-of-the-art. System Federated analytics Cooperative analytics CoVault ( [65, 82]) ( [78]) Technology HE+MPC+ZKP MPC MPC+TEEs Malicious parties < 3% user devices m−1 of m aggregators 1 out of 2 TEEs Data sources Many individuals Few large aggregators Many individuals (offline) No No Yes Scaling ultimately Compute/network Wide-area network Resources of a limited by of user devices bandwidth/delay datacenter large numbers of individuals (like federated analytics); and (3) scales to big data sets by leveraging the resources and scalability of a single data center, while offering distributed trust and malicious security.

The core design leverages secret sharing, MPC, and TEEs. p. 2

Where the paper says it

5 Contributions Our contributions include (a) an MPC configuration where each party executes in a different, independent TEE, which obviates the need for administrative and physical separation of parties and enables MPC within a single datacenter with high bandwidth links; (b) a set of techniques that allow the delegation of trust to a set of TEE-encapsulated parties while ensuring authentication, attestation, input integrity, confidentiality, and selective forward consent; (c) the design of CoVault, a secure analytics platform where data sources upload encrypted data to a small set of diverse TEEs, which compute analytics queries using MPC. The design enables secure analytics on encrypted data contributed by individuals at a scale that is limited only by the resources of a datacenter; (d) two technical components of possibly independent interest: A provably secure authenticated secret-sharing scheme (§4.

The system utilizes an API where data sources contribute encrypted data shares to a query class defined by [Q, D, te]. p. 6
Where the paper says it

1 CoVault Databases So far, we have not discussed how the encrypted data shares, denoted C in § 3–§ 4, are managed. In our prototype, the encrypted data shares C returned by the Contribute API are forwarded to the respective DPs by the data sources.

Authorized analysts execute queries using the Query operation. p. 4
Where the paper says it

A data source contributes data to a query class only if it is comfortable with the instance’s Q, D and te. Data sources contribute data to a query class using the Contribute operation, and authorized analysts may execute queries using the Query operation.

CoVault implements two main constructions:

  1. Strawman (S1): Implements the API using secret sharing and n-party MPC, which provides selective forward consent and confidentiality but requires physical separation between parties due to colocation constraints.

  2. Full construction (S2): Modifies S1 by executing each of the n parties inside a TEE of a different, independent design, thereby providing colocation in addition to Selective Forward Consent (SFC), confidentiality, and integrity.

Security is established through MPC with t-of- n active security across TEE technologies from n different vendors, which are attested by community experts. p. 3

Where the paper says it

CoVault relies on MPC with t-of-n active security in a static corruption model. The code of the n parties runs inside the TEE technologies of n different vendors.

For scalable analytics, CoVault employs MapReduce for executing SQL filter-groupby-aggregate (FGA) queries by converting them into small map and reduce circuits executed in 2PC. p. 7

Where the paper says it

Instead, inspired by MapReduce [37], CoVault converts FGA queries into a set of small map and reduce circuits, each of which fits one machine. Since queries tend to be highly data parallel, most map and reduce circuits are data independent, and can be executed in parallel 2PCs using all available cores and servers in a datacenter.

Data ingress is handled by dedicated Ingress Processors (IPs) that perform batch append and merge sorted batches in 2PC to create materialized views. p. 8
Where the paper says it

While this increases the data transmitted or stored by a factor of 256x in our prototype (128x for the garbled coding of each bit and 2x for DualEx), we have empirically found this to be faster than verifying and creating a MAC in each mapper/reducer. Our design reduces in-2PC MACs to the minimum possible in the common case: we verify one MAC for every batch of data uploaded by a data source, create per-column MACs when storing data in the database after data ingress, verify these MACs when the data is read for a query, and create one MAC for every query’s output.

For data-dependent FGA queries, CoVault uses an Oblivious Data Retrieval (ODR) scheme on previously shuffled tables to prevent secret leakage through database access patterns. p. 7
Where the paper says it

Another option is to randomly permute secret-shared tables [23, 51, 61], but these techniques either have substantial overhead or work only with semi-honest adversaries. CoVault instead relies on an oblivious data retrieval (ODR) scheme, which achieves constant-time lookup at the expense of off-line work.

In an epidemic analytics scenario involving a country of 80 million people, CoVault can continuously process data using a core pair for every 20,000 people. p. 0

Where the paper says it

For example, CoVault can process data relevant to epidemic analytics for a country of 80M people (about 11. 85B data records/day) on a continuous basis using a core pair for every 20,000 people.

The end-to-end query latency estimation shows that for this scale, running a complex query can take approximately 2. p. 3
Where the paper says it

The appendix offers more details on CoVault’s community approval process (§A), oblivious mapreduce technique (§B), ingress processing (§C), and epidemic analytics scenario (§D), with additional evaluation material. Furthermore, the appendix includes our algorithm to estimate end-to-end query latency (§E) and proofs of security of the primitives we use in CoVault (§F).

24 hours on two core pairs in the setup described. p. 6
Where the paper says it

We could also have used other schemes [33, 41]. protocol concurrently on separate core pairs, with the roles of the two parties, conventionally called generator and evaluator, reversed.

A key advantage is that CoVault's single-datacenter colocation means its scale-out to big data is not limited by WAN bandwidth, unlike distributed MPC solutions.

The contributions include: (a) an MPC configuration where each party executes in a different, independent TEE, eliminating the need for physical separation; (b) techniques for delegating trust to TEE-encapsulated parties while ensuring authentication, attestation, input integrity, confidentiality, and selective forward consent; and (c) the design of CoVault as a secure analytics platform scalable to big data limited only by datacenter resources. p. 2

Where the paper says it

5 Contributions Our contributions include (a) an MPC configuration where each party executes in a different, independent TEE, which obviates the need for administrative and physical separation of parties and enables MPC within a single datacenter with high bandwidth links; (b) a set of techniques that allow the delegation of trust to a set of TEE-encapsulated parties while ensuring authentication, attestation, input integrity, confidentiality, and selective forward consent; (c) the design of CoVault, a secure analytics platform where data sources upload encrypted data to a small set of diverse TEEs, which compute analytics queries using MPC. The design enables secure analytics on encrypted data contributed by individuals at a scale that is limited only by the resources of a datacenter; (d) two technical components of possibly independent interest: A provably secure authenticated secret-sharing scheme (§4.

Furthermore, it introduces two technical components: (d) a provably secure authenticated secret-sharing scheme and (e) an actively secure 2PC protocol. p. 2
Where the paper says it

The design enables secure analytics on encrypted data contributed by individuals at a scale that is limited only by the resources of a datacenter; (d) two technical components of possibly independent interest: A provably secure authenticated secret-sharing scheme (§4. 2) and an actively secure 2PC protocol that reveals information to a third entity, not the computing parties (§4.

The conclusion is that CoVault allows individual data sources to safely delegate control over their encrypted data to colocated MPC parties, each running in a different TEE, enabling big data analytics with distributed trust and malicious security. p. 1

Where the paper says it

In this paper, we present CoVault, a secure analytics platform that (1) supports complete (not sampled) query results (like cooperative analytics); (2) can operate on data from Table 1: CoVault versus state-of-the-art. System Federated analytics Cooperative analytics CoVault ( [65, 82]) ( [78]) Technology HE+MPC+ZKP MPC MPC+TEEs Malicious parties < 3% user devices m−1 of m aggregators 1 out of 2 TEEs Data sources Many individuals Few large aggregators Many individuals (offline) No No Yes Scaling ultimately Compute/network Wide-area network Resources of a limited by of user devices bandwidth/delay datacenter large numbers of individuals (like federated analytics); and (3) scales to big data sets by leveraging the resources and scalability of a single data center, while offering distributed trust and malicious security.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Decentralized Trust for Data Contribution: CoVault enables individual data sources to safely delegate control over their encrypted data to a set of colocated MPC parties, each executing in a TEE of a different type. This allows large-scale analytics without requiring individuals to trust a single intermediary aggregator.

  2. Scalability for Big Data Analytics: The platform scales to billions of records by leveraging the resources and scalability of a single data center, overcoming limitations imposed by wide-area network bandwidth that restrict existing MPC platforms.

  3. Enhanced Query Performance: CoVault can process queries 7 to over 100 times faster than state-of-the-art MPC platforms, demonstrating high efficiency even when scaling up to many data sources and big data sets.

  4. Secure Data Access via Oblivious Retrieval: The platform employs an oblivious data retrieval (ODR) scheme that achieves constant time lookup at the expense of off-line work, protecting against secret-dependent database accesses while maintaining integrity and confidentiality.

  5. Efficient Large Scale Query Execution: FGA queries are converted into a set of small map and reduce circuits, allowing them to be executed in parallel across all available cores in a datacenter, achieving near-linear horizontal scaling with the number of core pairs.

  6. Data-Dependent Trajectory Queries: CoVault supports complex data-dependent queries like q3 and q4 by using previously shuffled tables and Bloom filters to securely traverse device trajectories without revealing sensitive information about database content.

Abstract

There is growing awareness that the analysis of personal data, such as individuals' mobility, financial, and health data, can provide significant benefits to society. However, liberal societies have so far refrained from such analytics, arguably due to the lack of secure analytics platforms that scale to billions of records while operating in a very strong threat model. We contend that one fundamental gap here is the lack of an architecture that can scale (actively-)secure multi-party computation (MPC) horizontally without weakening security. To bridge this gap, we present CoVault, an analytics platform that leverages server-aided MPC and trusted execution environments (TEEs) to colocate the MPC parties in a single datacenter without reducing security, and scales MPC horizontally to the datacenter's available resources. CoVault scales well empirically. For example, CoVault can scale the DualEx 2PC protocol to perform epidemic analytics for a country of 80M people (about 11.85B data records/day) on a continuous basis using one core pair for every 30,000 people.

Sources

Related papers