Private Aggregate Queries to Untrusted Databases

Private Aggregate Queries to Untrusted Databases

Speakers: Syed Mahbub Hafiz

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=ahv3du5LpoE

Overview

In an increasingly data-driven world, the tension between data utility and user privacy is at an all-time high. Companies and malicious entities frequently exploit sensitive user data, leading to significant privacy breaches involving information ranging from political affiliations to health records. This talk, "Private Aggregate Queries to Untrusted Databases," presented by Syed Mahbub Hafiz at the NDSS Symposium, tackles a critical facet of this challenge: enabling users to retrieve aggregated statistical information from an untrusted database without revealing the specific records or context of their query.

Traditional Private Information Retrieval (PIR) protocols, while effective at hiding specific item access, fall short when it comes to complex, aggregation-based queries. These protocols often demand the client to know the exact row index of the data, a requirement that is highly impractical for real-world analytical tasks involving functions like SUM, MEAN, MIN/MAX, COUNT, or Histograms. Furthermore, existing PIR solutions for keyword or SQL-like queries typically involve multiple interactions, adding complexity and latency. Hafiz's work introduces a novel, general-purpose Information-Theoretic PIR (IT-PIR) framework designed to bridge this gap, allowing users to fetch aggregated results while concealing all sensitive query sections from the hosting PIR server within a single round of interaction. This advancement is particularly crucial as databases are increasingly outsourced to untrusted cloud providers, who could otherwise monitor queries for targeted advertising or data compilation.

The significance of this research lies in its ability to empower privacy-preserving analytics over sensitive datasets. By enabling complex aggregate queries—such as calculating total positive reactions to a politician's posts, aggregating multi-city flight prices, or tracking stock market fluctuations—without revealing the underlying specific data points or user interests, the protocol fundamentally enhances data security. This not only protects individual privacy but also provides a robust solution for organizations handling sensitive data in untrusted environments, mitigating risks of inference and misuse by database providers or cloud hosts.

Background

▶ Watch: Introduction: Privacy challenges with untrusted databases and aggregation (0:00)

The evolution of privacy-enhancing technologies (PETs) is rooted in cryptographic techniques that provide strong privacy guarantees, either through assumptions of computational infeasibility or fundamental information theory. While computational complexity-based PETs rely on the premise that adversaries lack the computational resources to break the system within a reasonable timeframe, Information-Theoretic PIR (IT-PIR) protocols offer a more robust guarantee, resisting even adversaries with unlimited computational power. This superior security comes with a crucial assumption: the non-collusion of a certain number of parties, a concept prevalent in technologies like secret sharing and onion routing.

Single-server computational PIR, often relying on homomorphic encryption, typically incurs heavy overhead, making it impractical for large databases where a naive client-downloads-entire-database approach is infeasible. While offline-online PIR schemes attempt to improve single-server performance through precomputation, their query processing times still lag behind multi-server IT-PIR schemes. The efficiency of practical multi-server IT-PIR hinges on these non-collusion guarantees, often mitigated through strategies involving unknown side-channels. A key performance metric for practical PIR protocols is sublinear communication costs relative to the database size.

This protocol builds upon foundational IT-PIR work, specifically Chor et al.'s multi-server IT-PIR, which modeled databases as bit strings for fetching specific bits privately. Goldberg's robust IT-PIR further extended this by modeling databases as b-bit blocks, enabling oblivious fetching of multiple blocks, a more realistic approach for variable-length records. These prior works primarily focused on positional queries, where the client must know the physical location (row number) of the data block, an inconvenient and privacy-compromising requirement.

The proposed framework operates within the widely adopted vector-matrix model for PIR. In this model, the database D is represented as an r x s matrix (r rows/data blocks, s words/block). Traditionally, to fetch the i-th block, a user constructs an r-dimensional query vector e_i with a '1' at the i-th position and '0's elsewhere. The product e_i D yields the desired block Ď_i. To ensure privacy, linear secret sharing, specifically Shamir's (t+1, l)-threshold scheme, is employed, as proposed in Goldberg's IT-PIR. The user shares their query vector component-wise across 'l' servers. Each server multiplies its share with its copy of the database matrix, and the user reconstructs the data block from the combined responses. This scheme guarantees privacy as long as fewer than t+1 servers collude. A crucial precursor to this work is Hafiz-Henry's "indexes of queries" concept, which enabled expressive, contextual queries in a single round, minimizing communication costs—a foundation significantly leveraged by the new protocol.

Further efficiency and privacy enhancements come from polynomial batch coding, inspired by Henry's work. This technique reduces the database size on servers by encoding buckets, using a rampification of Shamir's secret sharing. It transforms 'r' database blocks into 'u'-tuples, interpolates them component-wise to obtain polynomials, and then places a single component-wise evaluation of each polynomial vector into 'l' buckets. This allows batching multiple indexes for various queries into a single batch index of queries of polynomials, ensuring that all user queries pass through the same batch index, preventing information leakage about the specific query and drastically reducing storage, communication, and computation costs. This technique also enables aggregating multiple data blocks in a single request, facilitating top-K queries or histograms by batching multiple count queries.

The core of the "indexes of queries" technique relies on permutation matrices, which are constructed by permuting rows of an identity matrix based on specific information slices. Each row acts as a query filter, indicating database rows that satisfy a condition. While permutation matrices are suited for keyword searches (single '1' per row/column), the generalized index of queries can contain multiple '1's in each row, enabling aggregation over several database records. These matrices are pre-constructed and stored on PIR servers. The user only needs to know the number of rows in the index (to construct the query vector) and a keyword to identify the correct index, eliminating the need for positional knowledge—a significant advantage over most prior PIR schemes.

Key Findings

▶ Watch: Demonstrating practical performance with impressive benchmarking results (2:08)

The talk presents a robust framework for Private Aggregate Statistical Queries on untrusted databases, delivering provable PIR guarantees. The core contributions significantly advance the state of the art in privacy-preserving data analytics:

1. Novel Framework for Private Aggregate Statistical Queries: The primary contribution is a comprehensive framework that enables users to perform complex aggregate statistical queries (SUM, MEAN, MIN/MAX, COUNT, Histograms) on untrusted databases while maintaining strong Information-Theoretic PIR guarantees. This is achieved in a single round of interaction, a significant improvement over multi-round traditional PIR protocols for such queries.
2. Introduction of Standard Aggregate Vectors: The framework introduces a new type of standard aggregate vector. Unlike traditional basis vectors that contain a single '1' for fetching an individual item, these new vectors contain multiple 'ones' at specific indices, facilitating component-wise aggregation over multiple records. This is fundamental to enabling aggregate functions within the PIR paradigm.
3. Construction and Batching of Auxiliary Indexes: The protocol leverages the construction and batching of auxiliary indexes specifically designed for standard aggregate queries. This is achieved through the innovative combination of "querying for queries" and polynomial batch coding. This technique empowers the framework to support expressive queries that include searching, sorting, ranking, and various other constraints alongside aggregation, all while minimizing storage, communication, and computation costs.
4. GPU Implementation and Benchmarking: A key finding is the successful GPU implementation of the protocol, which parallelizes computations to achieve remarkable performance. For instance, an aggregate query on a 1-million tweet database, targeting 3,000 user handles, takes just 0.014 seconds for the PIR server to generate the result. This is a substantial speedup compared to Goldberg's regular IT-PIR (Oakland 2007), which takes 1.13 seconds for a much simpler positional query. The protocol demonstrated no additional overhead for complex queries compared to simpler ones when scaling to 300,000 user handles. Benchmarking showed the system supporting approximately 4000 queries per second for databases with over 16 million rows, and for queries aggregating up to 512 rows.
5. Compelling Case Studies: The practicality of the protocol is demonstrated through compelling case studies using real-world datasets like MIMIC3 Medical Database, a Twitter database of 1 million tweets, and the Yelp academic dataset. These studies validate the protocol's efficiency and applicability for diverse aggregate queries, from counting urgent admissions to calculating mean likes for politicians. For a database with a million records, the maximum server response time for Twitter queries was around 0.45 seconds. For a 40 GiB Twitter database, the protocol achieved response times as low as 0.1 seconds (GF(2^8) modulus), a 141x improvement over Goldberg's 16.8 seconds.
6. Open-Source Artifact and Reproducibility: The research provides an open-source artifact that has acquired 'available,' 'functional,' and 'reproduced' badges, ensuring transparency and enabling other researchers and practitioners to validate and build upon this work.

Technical Deep Dive

▶ Watch: Defining the threat model: Untrusted data providers, passive adversaries (2:47)

The core problem addressed by this framework is enabling private aggregate statistical queries on untrusted databases. This involves a sophisticated interplay of Information-Theoretic PIR (IT-PIR), secret sharing, novel indexing structures, and efficient batching techniques.

Threat Model

The threat model assumes an untrusted data provider. This means any server hosting the database can observe all executed queries, all computations on the server, and which database rows are accessed or untouched. The protocol specifically aims to prevent the database provider from learning any contextual information about a user's specific query. The adversary is primarily passive, meaning they eavesdrop but do not actively tamper with data or responses (v=0 for Byzantine robustness). A crucial assumption for IT-PIR is about collusion: privacy is maintained as long as a threshold t or fewer PIR servers collude. Information about the user's query is only revealed if t+1 or more servers collude, with t being a tunable parameter.

For a user to interact with the system, they only require minimal semantic information: the number of rows in the permutation matrix data structures (which dictates the query vector dimension) and a keyword to identify the query. They do not need physical positional information about the data.

Vector-Matrix PIR Model and Extensions

The protocol builds on the vector-matrix PIR model, where the database D is an r x s matrix. To achieve privacy, the user's query vector is split into shares using Shamir's (t+1, l)-threshold secret sharing scheme and distributed among l servers. Each server j holds a share of the database D_j and a share of the query vector e_j. The server computes e_j D_j and sends the result back to the client. The client then reconstructs the desired data block from t+1 or more server responses. This setup guarantees perfect (information-theoretic) security as long as the collusion threshold t is not exceeded.

Indexes of Aggregate Queries Technique

At the heart of enabling expressive, contextual queries is the index of queries technique. This involves pre-constructed matrices stored on the PIR servers. While basic permutation matrices (with a single '1' per row/column) suffice for keyword searches, the framework introduces a more general form: simple indexes of aggregate queries (Definition IV.3), which are (0,1)-matrices Π where each row can be a standard aggregate vector (Definition IV.1). A standard aggregate vector e_I is a (0,1)-vector with a '1' at each index belonging to a set I. When e_I is multiplied by the database D, it yields a component-wise linear combination (sum) of the records indexed by I. This linearity is crucial for aggregation.

For example, to implement SELECT SUM(days_hospitalized) FROM daily_patient_records WHERE patient_id = 3, an index Π_patient is constructed where '1's correspond to all records associated with patient ID 3. For COUNT and Histogram queries (e.g., SELECT COUNT(*) FROM daily_patient_records WHERE gender_id = G), preprocessing might map categorical variables to integer IDs, and an index Π_population would be used. Histograms are created by batching multiple count queries for each category. MIN and MAX queries (e.g., SELECT MIN(date_time) FROM hospital_admission_records WHERE state_id = I) use specialized indexes like Π_latestadmission or Π_oldestadmission. MEAN queries are decomposed into SUM and COUNT queries, with the user performing local division.

The protocol ensures t-privacy for indexes of aggregate queries (Definition IV.6): a coalition of at most t servers cannot infer the requested index I.

Polynomial Batch Coding

To enhance efficiency and privacy, especially when handling multiple types of aggregate queries, polynomial batch coding is employed. This technique allows for the batching of multiple simple indexes of aggregate queries into a single structure. For example, two indexes, Π_duration (total days hospitalized for male patients before June 2022) and Π_population (count of female patients), can be batched using 2-ary polynomial batch codes to create Π_Iduration,population(x). By evaluating this polynomial component-wise at x=0, Π_duration is recovered; at x=1, Π_population is recovered. Each of the l servers holds an evaluation of this batched polynomial at distinct scalar values x_j.

When a client wants to retrieve a specific aggregate result (e.g., count of hospitalized female patients), they encode a standard basis vector e at the corresponding x value (e.g., x=1). To fetch both Π_duration and Π_population in a single round, the client encodes the same standard basis vector e at both x=0 and x=1 simultaneously. This mechanism drastically reduces storage, communication, and computation costs by presenting a unified interface to the servers, preventing them from differentiating between individual index accesses. The security and complexity analysis for this batching align with Hafiz-Henry's prior work.

General Protocol (Algorithm 1)

The overall protocol for private aggregate queries proceeds as follows:

1. Client Generates Secret Shares: The client generates secret shares of their query vector.
2. Client Generates Keyword Hint: The client also generates secret shares of a keyword hint, which is used to select the appropriate batch index of aggregate queries.
3. Server Isolation: Each server uses its share of the keyword hint to isolate the required batch index from its stored collection.
4. Server-side Query Processing (Index): Each server multiplies its share of the client's secret query vector with its selected batch index.
5. Server-side Query Processing (Database): Each server then multiplies the result from step 4 with its local copy of the database matrix.
6. Server Response: Servers send their computed results back to the user.
7. Client Reconstruction: The user reconstructs the desired aggregate query result from the server responses using the secret sharing reconstruction algorithm.

This entire process occurs in a single round of interaction, with an upload cost of O(p) (where p is the number of search terms or height of the index matrix) and a download cost of O(s) (where s is the number of words in a record), demonstrating high efficiency.

Demo / Proof of Concept

▶ Watch: Background: IT-PIR advantages over computational PIR for efficiency (4:00)

The practical viability and efficiency of the proposed framework were rigorously demonstrated through extensive benchmarking experiments and real-world case studies, leveraging a GPU implementation for parallelizable computations. The artifact, including the codebase, is publicly available, allowing for reproduction of results.

Benchmarking Experiments

Experiments were conducted on a server with 256 GB RAM and 5 GPUs, using Barrett Reduction for modulo arithmetic and compressed column storage (CCS) for matrices. All reported values are the mean of 100 trials.

• VspM (Vector-sparse Matrix) Throughput on GPU: This metric measures the number of client queries processed per second, including data transfer to and from the GPU.
• Varying Database Rows (r): As the number of database rows r increased from 2^14 to 2^24, throughput monotonically decreased. However, for databases with over 16 million rows, the protocol still supported approximately 4000 queries per second. Larger modulus bit sizes (128, 256, 512 bits) consistently reduced throughput.
• Varying Index Rows (p): Varying the number of rows in the index p from 2^1 to 2^17 showed no major impact on throughput until p increased from 2^16 to 2^17, where a slight drop was observed.
• Varying Aggregation Rows: For queries aggregating up to 512 rows, the protocol maintained approximately 4000 queries per second, roughly half the throughput of non-aggregate queries on an identical database, showcasing its efficiency even for complex aggregations.
• Varying Batched Indexes (u): Batching 1000 files took about 32 seconds, with batching time monotonically increasing with u.

Practical Applications (Case Studies)

Three real-world databases were used to validate the protocol's practicality:

1. MIMIC3 Medical Database: This sensitive clinical database was used for queries batched by admission type (e.g., Count urgent admissions, Mean hospital stay) and patient level (e.g., Total drug doses, Total hospitalization duration). Index dimensions varied, with the largest being 1,400x4,156,450.
2. Twitter Database: Approximately 1 million politically relevant tweets (400 MB) were scraped. Queries included total likes by a user, count of tweets with no retweets, mean likes by a politician, and histograms of likes. The maximum time for a Twitter query was around 0.45 seconds. Performance was further optimized by filtering users (e.g., those with >=100 likes) to reduce the search space.
3. Yelp Database: An experiment from Splinter was recreated using the Yelp academic dataset for queries like COUNT(*) WHERE category=Thai, TOP 10 restaurant WHERE category=Mexican ... ORDER BY stars, and MAX(stars) WHERE category=Mexican OR category=Chinese ... GROUP BY category.

Performance Summary for Case Studies:

• Index generation time: Ranged from seconds to about 30 seconds for the longest indexes (e.g., 1,400x4,156,450 for MIMIC3). This is typically a one-time setup activity.
• Storage requirements: Nominal, with the largest MIMIC3 queries requiring about 34 MB.
• Server response generation times: For a database with a million records, the maximum response time was around 0.45 seconds (Twitter queries).

Comparison with Baseline and Larger Databases

A direct comparison with Goldberg's IT-PIR (28) demonstrated significant improvements. For a 4-million record MIMIC-3 database, this protocol generated a server response in a fraction of a second, whereas Goldberg's required over 7 seconds. Crucially, Goldberg's protocol requires multiple interactions for expressive aggregate queries, while this new framework achieves it in a single round.

Further scalability validation involved augmenting Twitter and MIMIC3 databases to 40 GiB and 64 GiB. For the 40 GiB Twitter Filt. database, the protocol achieved response times as low as 0.1 seconds (using a GF(2^8) modulus), compared to Goldberg's 16.8 seconds (GF(2^8)), representing a 141x improvement. For the 40 GiB MIMIC3 Filt. database, response times were 0.6 seconds (GF(2^8)) versus Goldberg's 17.5 seconds (GF(2^8)), a 31x improvement. This superior performance is attributed to exploiting the sparsity of derived data structures.

While the primary focus was on GPU, CPU benchmarking was also performed. With a 27-bit modulus and 2^16 records, the CPU-based system served 8 queries per second, dropping to 5 queries per second for a 29-bit modulus and 2^20 records. While lower than GPU, this still yields sub-second response times, confirming its viability.

Defensive Implications

▶ Watch: Technical foundation: The Vector-Matrix PIR Model explained (4:50)

The "Private Aggregate Queries to Untrusted Databases" framework offers profound defensive implications for organizations and individuals concerned with data privacy in an increasingly outsourced and cloud-centric world. The core problem this work addresses is that even when data is stored on untrusted third-party servers (like cloud providers), performing analytical queries can leak sensitive information about what is being searched for, allowing the server to infer user interests, business strategies, or even personal attributes.

Here's how defenders can leverage this information:

1. Enabling Private Analytics on Untrusted Infrastructure: Organizations can confidently outsource their databases to untrusted cloud providers without fearing query pattern leakage. This protocol allows for aggregate statistical queries (SUM, COUNT, MEAN, MIN/MAX, Histograms) to be performed privately. This means a company can analyze sales trends, customer demographics, or operational metrics without revealing the specific products, customer segments, or timeframes they are investigating to the cloud provider.
2. Mitigating Passive Adversaries and Collusion: The protocol's Information-Theoretic PIR (IT-PIR) guarantees protection against adversaries with unlimited computational resources, a stronger assurance than complexity-based methods. Defenders should understand and configure the t-collusion threshold to match their risk tolerance. By distributing database shares across l servers and setting t, they can ensure that privacy is maintained even if up to t servers collude. This is critical for environments where multiple cloud providers or internal departments might be compromised or tempted to collude.
3. Protecting Sensitive User Data from Inference Attacks: For applications like social networking, flight booking, or stock market analysis, the protocol prevents untrusted platforms from inferring user interests (e.g., political affiliation, travel plans, investment strategies) based on their query patterns. Defenders building such applications can integrate this framework to offer stronger privacy guarantees to their users, enhancing trust and compliance with privacy regulations.
4. Single-Round Efficiency for Real-World Use Cases: The ability to perform complex aggregate queries in a single round of interaction is a significant advantage. This minimizes communication overhead and latency, making privacy-preserving analytics practically feasible for real-time or near real-time applications. Defenders can implement this without incurring the performance penalties often associated with multi-round cryptographic protocols.
5. Leveraging Existing Data Structures with Enhanced Privacy: The use of indexes of aggregate queries and polynomial batch coding means that complex queries can be supported without requiring a complete re-architecture of existing databases. The indexes, though novel, are derived from the database, allowing organizations to overlay this privacy layer onto their current data management strategies.
6. Scalability and Performance for Large Datasets: The demonstrated performance on large databases (e.g., 40 GiB Twitter data with 0.1-second response times, 141x improvement over baseline) confirms that this is not just a theoretical solution. Defenders working with big data can consider this for scalable private analytics, especially when leveraging GPU-accelerated infrastructure.
7. Considerations for Database Updates and Byzantine Robustness: While the protocol primarily obfuscates read access patterns, defenders must account for database updates, which typically require regenerating indexes. The mention of extending the model to a v-Byzantine-robust model (tolerating v malicious servers) offers a future pathway for even stronger integrity guarantees against active adversaries, which is a critical consideration for highly sensitive systems.

In essence, this work provides a powerful tool for defenders to achieve a critical balance: deriving valuable insights from data through aggregation, while simultaneously protecting the privacy of the underlying individual records and the intent of the queries from untrusted data custodians.

Key Takeaways

• Enables Private Aggregate Queries: The framework allows users to perform complex aggregate statistical queries (SUM, MEAN, MIN/MAX, COUNT, Histograms) on untrusted databases without revealing the specific records or context of their queries to the server.
• Single-Round Information-Theoretic Privacy: Achieves provable Information-Theoretic PIR (IT-PIR) guarantees, robust against computationally unbounded adversaries, within a single round of interaction, significantly improving efficiency over prior multi-round approaches for aggregate queries.
• Novel Indexing and Batching Techniques: Introduces standard aggregate vectors and indexes of aggregate queries with multiple '1's per row, combined with polynomial batch coding, to support expressive queries (searching, sorting, ranking, aggregation) while minimizing storage, communication, and computation costs.
• High Performance and Scalability: A GPU implementation demonstrates remarkable performance, achieving approximately 4000 queries per second for databases over 16 million rows and for queries aggregating up to 512 rows. It delivered up to a 141x speedup over Goldberg's IT-PIR for 40 GiB databases.
• Practical Applicability: Validated through case studies on real-world datasets (MIMIC3, Twitter, Yelp), demonstrating feasibility and efficiency for diverse analytical tasks with server response times as low as 0.1 seconds for large databases.
• Open-Source and Reproducible: The availability of an open-source artifact with 'available,' 'functional,' and 'reproduced' badges promotes transparency and facilitates further research and adoption.

About the Speaker(s)

Syed Mahbub Hafiz is the speaker for this presentation. The transcript mentions his prior contributions to the field, specifically "Hafiz-Henry's work 7," indicating his involvement in foundational concepts like the "indexes of queries" technique which are significantly leveraged and extended in this new framework. This suggests a sustained research focus on privacy-enhancing technologies and Private Information Retrieval.