PIRANA: Faster Multi-query PIR via Constant-weight Codes

PIRANA: Faster Multi-query PIR via Constant-weight Codes

Speakers: Jian Liu; Jingyu Li; Di Wu; Kui Ren

Conference: IEEE S&P

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

Overview

This talk introduces PIRANA, a novel protocol designed to significantly accelerate Private Information Retrieval (PIR), particularly for multi-query scenarios. Presented by Jian Liu and co-authored with Jingyu Li, Di Wu, and Kui Ren, the work addresses the critical need for more efficient privacy-preserving data retrieval mechanisms. PIR is a foundational cryptographic primitive allowing a client to retrieve an item from a server's database by its index, without revealing which item was requested. This capability underpins a wide array of privacy-sensitive applications, including private contact discovery, secure browsing, and private navigation.

Despite its importance, the practical deployment of PIR has been hampered by its substantial communication and computation costs. Many existing solutions rely on Fully Homomorphic Encryption (FHE), which, while powerful, involves computationally intensive operations. PIRANA aims to overcome these limitations by leveraging constant-weight codes and a suite of sophisticated optimizations tailored for FHE. The research demonstrates remarkable performance improvements, making PIRANA a leading candidate for practical, high-throughput private data access, particularly in environments requiring frequent database updates.

The core innovation of PIRANA lies in its strategic use of constant-weight codes for query encoding, combined with advanced FHE optimization techniques such as Single Instruction Multiple Data (SIMD) features, optimized rotation strategies, and Probabilistic Bucket Compression (PBC) for multi-query support. By drastically reducing the number of expensive FHE multiplications and rotations, PIRANA pushes the boundaries of what is achievable in practical PIR, paving the way for broader adoption of privacy-preserving technologies in real-world systems.

Background

▶ Watch: Introduction to PIR and its challenges (0:00)

Private Information Retrieval (PIR) is a cryptographic protocol that allows a user to query a database hosted on a server and retrieve a specific record without the server learning which record was retrieved. This privacy guarantee is crucial for applications where client queries might reveal sensitive interests or intentions. Early PIR schemes, while conceptually sound, often suffered from prohibitively high communication or computation costs, rendering them impractical for large-scale deployment.

A significant class of modern PIR solutions, including schemes like SEAL PIR, Onion PIR, Spiral, Simple PIR, and Constant-Weight PIR (CWP), are built upon Fully Homomorphic Encryption (FHE). FHE is a cryptographic paradigm that enables computations on encrypted data without prior decryption. This means a server can perform operations like addition and multiplication directly on ciphertexts, producing an encrypted result that, when decrypted by the client, matches the result of the same operation performed on the plaintext. Key FHE features relevant to PIRANA include:

• Homomorphic Addition and Multiplication: FHE supports both addition and multiplication of ciphertexts with plaintexts, or between two ciphertexts.
• Single Instruction Multiple Data (SIMD): This feature allows a single FHE operation (e.g., multiplication or addition) to simultaneously process multiple data elements packed into a single ciphertext slot. This parallel processing capability is crucial for efficiency, as N elements can be computed in parallel, where N is the polynomial degree.
• SIMD Rotation: FHE also supports rotation operations on encrypted data, allowing elements within a ciphertext's slots to be shifted. While powerful, both ciphertext-to-ciphertext multiplication and SIMD rotation are known to be computationally expensive operations in FHE, often becoming performance bottlenecks in algorithm design.

Another critical preliminary for PIRANA is constant-weight codes (CWC). These are binary strings where all code words share the same Hamming weight k – meaning they all have exactly k '1's. For example, with a code length M of 8 and a Hamming weight k of 2, a code word might look like 01100000. CWC can be used to efficiently map original database indices to these binary code words. The size of such a code is M choose K, offering a compact representation. In the context of PIR, CWC can be used to encode query indices, enabling a client to express their desired item in a way that can be processed homomorphically.

The challenge in existing CWP-based PIR schemes often lies in the equality operator used to compare an encrypted query index with all possible plaintext indices. The original CWP required M-1 ciphertext-to-ciphertext multiplications for this comparison, which quickly becomes unmanageably expensive. The core problem PIRANA aims to solve is to drastically reduce these expensive FHE operations, thereby minimizing both communication and computation costs for practical PIR.

Key Findings

▶ Watch: PIRANA's core algorithm demonstration (3:25)

PIRANA introduces a paradigm shift in the efficiency of Private Information Retrieval, particularly for multi-query scenarios. Its key findings and contributions are primarily centered around unprecedented performance improvements and enhanced versatility:

1. Dramatic Performance Acceleration: PIRANA achieves a significant speedup over both existing constant-weight code-based PIR (CWP) and state-of-the-art batch PIR solutions. The talk highlights specific benchmarks:

• Up to 188.5 times faster than the original CWP scheme.
• For 256-byte payloads and 256 queries, PIRANA is 24.8 times faster than OnionPIR and an astounding 82 times faster than Spiral, two well-known PIR protocols.
• In comparison to the state-of-the-art batch PIR work, PIRANA can achieve a 40.4 times speedup in answer generation time under specific conditions, demonstrating superior performance in both communication and computation costs.
• When answering 496 queries with 256-byte payloads, PIRANA takes only 12.1 seconds, achieving an 812-fold amortization, showcasing its efficiency for high-throughput applications.

1. Efficient Multi-Query Support: A crucial contribution of PIRANA is its ability to support multiple queries with minimal additional cost. By integrating techniques like Probabilistic Bucket Compression (PBC), PIRANA effectively handles simultaneous requests, making it highly suitable for applications where clients need to retrieve several items privately. This multi-query capability is achieved without incurring the typical performance penalties associated with processing multiple independent PIR queries.

1. Novel FHE Optimization Strategies: The performance gains are largely attributed to PIRANA's innovative FHE optimization techniques. These include:

• Optimized Rotation Operations: By carefully designing rotation steps (e.g., rotating only one step per iteration instead of arbitrary steps, or rotating selection vectors with the plaintext database), PIRANA significantly reduces the number of expensive FHE rotation operations, which are often a bottleneck.
• Maximal Utilization of SIMD: The protocol fully leverages the SIMD capabilities of FHE to parallelize operations, allowing a single FHE multiplication or addition to process multiple elements concurrently, thereby reducing overall computation time.

1. Extensibility to Labeled Private Set Intersection (L-PSI): PIRANA's design is flexible enough to be easily extended to solve the Labeled Private Set Intersection (L-PSI) problem. This extension is particularly friendly for scenarios requiring frequent database updates. By integrating hashing for keyword queries and Oblivious Pseudorandom Functions (OPRF) for database protection, PIRANA offers a more efficient alternative to existing L-PSI methods that rely on expensive polynomial interpolation.

In summary, PIRANA represents a significant leap forward in the practical deployment of PIR, delivering unprecedented speed and efficiency for both single and multi-query operations, while also offering a robust framework for related privacy-preserving computations like L-PSI.

Technical Deep Dive

▶ Watch: Multi-query PIR extension with PBC and cuckoo hashing (6:00)

PIRANA's technical prowess stems from a meticulous integration of constant-weight codes with highly optimized Fully Homomorphic Encryption operations. The protocol begins by reorganizing the server's database and encoding client queries in a novel way to minimize expensive FHE operations.

Database Rearrangement and Query Encoding

The first step in PIRANA involves the server rearranging its database into a matrix structure, typically N rows and T columns. This matrix representation facilitates the subsequent homomorphic operations. When a client wishes to retrieve an item at a specific index, say the j-th item, they compute its corresponding row index and column index within this matrix.

The core of the query encoding relies on constant-weight codes (CWC). For example, if the desired item's column index is 1, the client uses a CWC to encode this index. A CWC of length M and Hamming weight k (e.g., k=2) would represent this index as a binary string with exactly k ones (e.g., 01100000). The client then takes a specific row of pre-computed CWC vectors corresponding to the desired row index and uses it to fill this code. This vector, containing the CWC representation of the column index, is then encrypted using Fully Homomorphic Encryption (FHE) and sent to the server as the query ciphertext.

Homomorphic Equality Operations with SIMD

Upon receiving the encrypted query vector, the server needs to identify the desired column. The original CWP approach would involve M-1 ciphertext-to-ciphertext multiplications to compare the encrypted query with all possible column indices. PIRANA significantly reduces this by leveraging FHE's Single Instruction Multiple Data (SIMD) capabilities and a more efficient equality check.

Instead of M-1 multiplications, the server performs T times equality operations to generate "selection vectors." These selection vectors are designed such that only the position corresponding to the desired item's column index contains a '1', with all other positions being '0'. This is achieved by multiplying the encrypted query vector (which contains the CWC encoding of the desired column) with a plaintext CWC representation of each possible column. For instance, if the encrypted query encodes column y, multiplying it by a plaintext CWC for column y would yield a '1' (or a value that decrypts to '1'), while multiplying it by a plaintext CWC for any other column y' would yield '0'.

The magic here is the use of SIMD. By packing multiple CWC comparisons into a single ciphertext, a single FHE multiplication operation can compute N elements in parallel, where N is the polynomial degree. This drastically reduces the number of expensive FHE multiplications required, moving from M-1 individual ciphertext multiplications to a more efficient set of operations that exploit SIMD parallelism.

Once the selection vectors are generated, the server multiplies them with the database matrix (specifically, the plaintext database rows corresponding to the query's row index) and adds the results together. This homomorphic operation effectively "selects" the desired item's value while keeping it encrypted. The final encrypted result is then sent back to the client for decryption.

Rotation Optimization for Large Payloads

For databases with large payloads or when processing multiple queries, the naive application of SIMD can still lead to an excessive number of FHE rotation operations, which are computationally expensive. PIRANA introduces sophisticated rotation optimizations:

1. Reduced Rotation Steps: Instead of rotating arbitrary steps, PIRANA optimizes rotations to only one step per iteration. This significantly reduces the overhead associated with FHE key switching operations, making each rotation more efficient. The speaker explicitly states that rotating Alpha-1 times can be optimized, and the total number of rotations can be represented by a specific formula.

1. Plaintext Database Interaction: When the payload size is large, PIRANA strategically rotates the selection vectors with the plaintext database values, rather than rotating only the multiplied ciphertexts. This approach reduces the total number of required rotations, as operations with plaintexts are generally less expensive than ciphertext-to-ciphertext rotations.

1. Hybrid Approach: In intermediate scenarios (where the number of elements is neither too small nor too large), PIRANA combines these two methods, rotating selection vectors with plaintext data and then further optimizing rotations of multiplied ciphertexts, to achieve optimal performance.

Multi-Query Support with Probabilistic Bucket Compression (PBC)

A key advancement in PIRANA is its efficient support for multiple queries. A naive approach might lead to multiple desired elements residing in the same row or slot, causing collisions. PIRANA addresses this using Probabilistic Bucket Compression (PBC), a technique based on three-way Cuckoo hashing.

PBC encodes S database elements into M code words distributed among B buckets, with a small failure probability. By ensuring that desired elements from different queries are distributed into different buckets (and thus different rows of the matrix), PIRANA avoids collisions. This allows the use of multiple FHE slots to batch more queries.

For multi-query PIR, the SIMD rotation steps need to be adjusted to B slots (where B is the number of buckets) instead of one. The rotation optimization described previously remains applicable, with adjustments for the bucket arrangement. If the number of buckets itself is close to N (the polynomial degree), the result is dense and may not require further compression, allowing direct use of multiple slots to encode queries for one bucket, further reducing rotation operations.

Extension to Labeled Private Set Intersection (L-PSI)

PIRANA is designed with extensibility in mind, particularly for the Labeled Private Set Intersection (L-PSI) problem. L-PSI allows two parties to find the intersection of their datasets while also retrieving associated labels (values) for the intersecting elements, all without revealing non-intersecting elements or their labels. Two primary challenges arise:

1. Keyword Queries: L-PSI often involves keyword-based queries rather than index-based ones. PIRANA incorporates hashing to efficiently map keywords to indices, allowing the underlying index-based PIR mechanism to function.
2. Database Protection: Classic PIR does not protect the server's database from the client learning which items are present, only which item was retrieved. For L-PSI, the server's database typically needs protection. PIRANA integrates Oblivious Pseudorandom Functions (OPRF). OPRF allows the client to obtain a pseudorandom value for an item if it's in the intersection, effectively making the database look like random strings to the client, who only learns the specific item it queried and its associated label.

Compared to existing L-PSI methods that rely on expensive polynomial interpolation, PIRANA's approach, leveraging its optimized PIR core, is significantly faster, especially in the setup phase. This makes it particularly friendly for scenarios requiring frequent database updates.

Demo / Proof of Concept

▶ Watch: Extending PIRANA to the L-PSI problem (7:15)

The talk presents a conceptual demonstration of PIRANA's core mechanism, illustrating how a client retrieves an item from a server's database using the proposed constant-weight code and FHE-based approach. This "simple demo" walks through the algorithmic steps rather than showcasing a live software execution, providing a clear understanding of the protocol's flow.

The demonstration begins with the server's database being conceptually rearranged into a matrix with N rows and T columns.

1. Client Query Encoding: If the client wishes to retrieve, for example, the second item in the database, they first determine its logical row index (e.g., 2) and column index (e.g., 1). The client then uses a constant-weight code (CWC) to encode this column index. For instance, if column index 1 is chosen, the client selects a CWC vector where only the first and second bits are '1' (e.g., 01100000). This CWC-encoded vector is then encrypted using homomorphic encryption and sent to the server as the query ciphertext.

1. Server-Side Processing:

• Selection Vector Generation: The server receives the encrypted query. It then performs T homomorphic equality operations. This involves multiplying the encrypted query vector with plaintext CWC representations of each possible column index. Due to the properties of FHE and CWC, only the multiplication with the correct plaintext CWC (matching the client's desired column) will yield a non-zero, or '1', result after decryption. All other multiplications will yield '0'. Crucially, these multiplications leverage Single Instruction Multiple Data (SIMD) features of FHE, allowing multiple comparisons to be processed in parallel within a single ciphertext, significantly speeding up the generation of the selection vectors.
• Data Retrieval: The result of these operations is a set of selection vectors where only the position corresponding to the desired item's column index contains a '1', and all others are '0'. The server then multiplies these selection vectors with the relevant row of the plaintext database (the row identified by the client's query) and homomorphically adds the results together. This effectively isolates the encrypted value of the desired item.

1. Client Decryption: The server sends the final encrypted result back to the client. The client then decrypts this ciphertext to obtain the desired item from the database.

The demonstration emphasizes how SIMD features are crucial for reducing the number of expensive FHE multiplications. It also highlights that for large payloads, additional rotation optimizations are necessary. If the raw multiplied result were simply rotated, it could lead to too many rotations, becoming a new performance bottleneck. This underscores the importance of PIRANA's optimized rotation strategies, such as rotating only one step per iteration or rotating selection vectors with the plaintext database, which were detailed in the technical deep dive.

Defensive Implications

▶ Watch: Conclusion: Summary of PIRANA's achievements (9:30)

PIRANA's advancements have significant defensive implications, primarily by making privacy-preserving data retrieval more practical and efficient for organizations and applications. Instead of defending against attacks on PIR itself (which is a privacy protocol), the implications focus on adopting and implementing PIR to enhance privacy and security.

1. Enabling Stronger Data Privacy: The most direct implication is the ability to implement stronger data privacy guarantees without incurring prohibitive performance costs. Organizations handling sensitive user data (e.g., contact lists, location data, browsing history) can now deploy PIR to allow users to retrieve specific information from centralized databases without revealing their queries. This directly reduces the risk of sensitive data leakage through query logs or server-side analysis.

1. Reduced Attack Surface for Query Data: By ensuring that the server never learns which specific item a client retrieves, PIRANA fundamentally changes the attack surface. Traditional systems where queries are plaintext or easily inferable present a clear target for adversaries seeking to profile users or discover sensitive interests. With PIRANA, even if an attacker compromises the server, they would not be able to link specific queries to individual items, thus protecting user intent and privacy.

1. Facilitating Privacy-Preserving Applications: PIRANA's speed and multi-query support make it a viable building block for a broader range of privacy-preserving applications that were previously too slow to be practical. This includes:

• Private Contact Discovery: Users can find contacts on a social network without revealing their entire contact list to the service.
• Private Navigation/Location Services: Users can query for points of interest or directions without revealing their current location or destination to the service provider.
• Secure Browsing/Malware Check: Clients can query blacklists or threat intelligence databases without revealing the URLs or files they are checking.
• Private Set Intersection (PSI) and Labeled PSI (L-PSI): For use cases like secure data collaboration or fraud detection, PIRANA's extension to L-PSI provides an efficient way for parties to find common elements and their associated data without revealing their full datasets.

1. Support for Dynamic and Frequently Updated Databases: The efficiency of PIRANA, particularly its L-PSI extension, makes it friendly for databases that require frequent updates. This is crucial for real-world applications where data is constantly changing, such as threat intelligence feeds or contact lists. Defenders can maintain up-to-date privacy-preserving services without excessive overhead for database re-encryption or re-computation.

1. Amortization for Batch Queries: The significant amortization factor (e.g., 812-fold for 496 queries) means that for applications where clients frequently make multiple related queries, the privacy cost per query drops dramatically. This encourages the adoption of privacy-preserving methods even in high-throughput scenarios.

In essence, PIRANA provides security architects and developers with a powerful, performant tool to embed strong privacy guarantees into their systems, shifting the defensive strategy from reactively protecting leaked query data to proactively preventing its exposure from the outset.

Key Takeaways

• PIRANA achieves unprecedented speed-ups for Private Information Retrieval (PIR), being up to 188.5 times faster than original constant-weight code-based PIR, 24.8 times faster than OnionPIR, and 82 times faster than Spiral for 256-byte payloads and 256 queries.
• Efficiently supports multi-query PIR with minimal additional cost, enabling clients to retrieve multiple items privately in a single interaction by leveraging Probabilistic Bucket Compression (PBC) and optimized SIMD operations.
• Introduces novel FHE optimization strategies, including refined rotation operations (e.g., one-step rotations, rotating selection vectors with plaintext databases) and maximal utilization of SIMD features, significantly reducing the number of expensive FHE multiplications and rotations.
• Leverages constant-weight codes (CWC) for efficient query encoding, combined with homomorphic equality checks, to precisely identify desired items within a database matrix structure.
• Easily extends to the Labeled Private Set Intersection (L-PSI) problem, making it a versatile tool for privacy-preserving computations, especially beneficial for frequently updated databases by using hashing for keyword queries and Oblivious Pseudorandom Functions (OPRF) for database protection.
• Offers a practical solution for deploying privacy-preserving applications such as private contact discovery, secure browsing, and private navigation, addressing the long-standing challenge of high computational and communication costs in PIR.

About the Speaker(s)

The primary speaker for this presentation is Jian Liu. At the time of this work, Jian Liu was a student at Zhejiang University, where this research on PIRANA was completed. He graduated in March with a master's degree. The work was co-authored by Jingyu Li, Di Wu, and Kui Ren, indicating a collaborative research effort within the academic setting.