FABLE: Batched Evaluation on Confidential Lookup Tables in 2PC

FABLE: Batched Evaluation on Confidential Lookup Tables in 2PC

Speakers: Zhengyuan Su

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=PnybFO-ukuw

Overview

The FABLE protocol, presented by Zhengyuan Su, addresses a critical challenge in secure multi-party computation (2PC): efficiently evaluating confidential lookup tables while maintaining data privacy and scalability. This work, conducted during Su's undergraduate studies at Tsinghua University in collaboration with Ti Simon and Wing from CMU, introduces a novel approach that significantly improves the performance and practicality of secure lookup operations. FABLE stands for "Batched Evaluation on Confidential Lookup Tables in 2PC," highlighting its core innovations: processing multiple queries simultaneously (batching) and ensuring the secrecy of the lookup table itself within a two-party computation framework.

The talk underscores the growing importance of secure lookup table evaluation in diverse privacy-preserving applications. Key examples include secure embedding lookup in end-to-end 2PC inference workflows for machine learning, where client input tokens are matched against a server's confidential embedding table, and secure data analytics workloads, specifically the joining of a 2PC table with a large local table. FABLE aims to overcome the limitations of prior solutions, which often struggled with scalability, table confidentiality, or imposed heavy computational burdens on client devices. By providing a protocol that is scalable, ensures table confidentiality, supports lightweight client computation, and offers concrete efficiency for the server, FABLE makes significant strides towards enabling more practical and widespread adoption of privacy-preserving technologies in sensitive domains.

Background

▶ Watch: Introduction to FABLE and problem statement (0:00)

Secure lookup table evaluation is a fundamental primitive in two-party computation (2PC), where two mutually distrusting parties collaborate to compute a function on their private inputs without revealing those inputs to each other. In the specific setting addressed by FABLE, the server holds a confidential lookup table, and the client possesses a batch of secret-shared inputs. The objective is for both parties to jointly obtain the secret-shared outputs corresponding to the table values for the client's inputs, without either party learning the other's private data. The protocol assumes a semi-honest threat model, where parties follow the protocol honestly but may attempt to infer information from the data they observe.

The need for secure lookup tables is pervasive. In secure machine learning inference, a client might have private input tokens that need to be looked up in a server's confidential embedding table—part of an ML model's guard rails—before being fed into the model. This ensures that sensitive input data remains private while leveraging the server's proprietary model components. Another significant application is in secure data analytics, particularly when executing complex queries involving joining a previously generated 2PC table (viewed as a large batch of secret-shared inputs) with a large, confidential local table held by one party.

Prior research has explored secure lookup table evaluation through various lenses, each with inherent limitations that FABLE seeks to address. One line of work focuses on using lookup tables as 2PC primitive gates to simplify the logic of 2PC circuits. These approaches typically target small, public lookup tables and are not designed for scalability, often exhibiting communication complexities that are linear or superlinear in the table size. Consequently, they are unsuitable for large, confidential tables.

A second category of prior work stems from read operations in distributed Oblivious RAM (ORAM). While ORAM schemes are designed to conceal access patterns to a storage system, their application in a 2PC client-server model presents challenges. Distributed ORAMs often assume a two-server setting where both parties possess similar computational power, leading to protocols that distribute heavy workloads equally. In a client-server scenario, this translates to a heavyweight client, which is undesirable for many real-world applications where clients might be resource-constrained devices.

Given these drawbacks, FABLE was developed to answer a crucial question: can a secure lookup table evaluation protocol be designed that simultaneously scales to large tables, guarantees the confidentiality of the table, supports lightweight client computation, and offers concrete efficiency for the server? FABLE's affirmative answer to this question forms the core contribution of the work, building a robust solution atop Private Information Retrieval (PIR), symmetric security, and batching techniques.

Key Findings

▶ Watch: FABLE protocol: high-level idea and components (5:00)

FABLE successfully addresses the long-standing challenges in secure lookup table evaluation by proposing a protocol that is both theoretically sound and concretely efficient. The core findings and contributions of this work can be summarized as follows:

1. Comprehensive Property Achievement: FABLE is the first protocol to simultaneously achieve all desired properties for secure lookup table evaluation: scalability to large tables, guaranteed confidentiality of the lookup table, lightweight client computation, and concrete efficiency for the server. This combination was previously elusive in existing solutions.
2. Novel Protocol Foundation: The high-level idea behind FABLE is to build upon a synergy of established cryptographic primitives: Private Information Retrieval (PIR) for scalability and client lightweightness, symmetric security for ensuring the confidentiality of the table, and batching techniques for achieving significant concrete efficiency through amortized performance.
3. Asymptotic Efficiency: FABLE demonstrates superior asymptotic complexity compared to prior works. It is the only protocol that achieves both sublinear client computation and sublinear communication complexity, marking a significant theoretical advancement for this problem domain.
4. Concrete Performance Breakthroughs: Beyond theoretical improvements, FABLE delivers orders of magnitude speedup in practical applications. Benchmarking against motivating use cases revealed:

• For secure embedding lookup in ML inference, FABLE achieved more than 400 times speed up compared to the Crypton baseline, with Motion used for benchmarking multiplicative triples.
• For secure query execution involving table joins in data analytics, FABLE demonstrated a 15 times speed up over the sort-compare-shuffle circuit from Senate.

1. Innovative Techniques for Batch PIR Adaptation: To adapt batch PIR for secure lookup tables, FABLE introduces two key innovations:

• An efficient query translation mechanism in 2PC that utilizes a caching mechanism for input deduplication and expansion, leading to 84.1% communication savings compared to baselines.
• A method to protect the lookup table's confidentiality in state-of-the-art batch PIRs using database masking and noise flooding.

These findings collectively establish FABLE as a groundbreaking solution that significantly advances the state-of-the-art in privacy-preserving computations involving confidential lookup tables, opening doors for its practical deployment in sensitive ML and data analytics environments.

Technical Deep Dive

▶ Watch: The insight: batching is a common workload (7:30)

FABLE's technical innovation stems from its intelligent integration of Private Information Retrieval (PIR) with batching and symmetric security, specifically tailored to overcome the limitations of prior approaches in a client-server 2PC setting.

The starting point for understanding FABLE's design is a naive construction derived from 2P-DORM, a distributed ORAM work. In this construction, the secret-shared input X is split into shares X0 (for the client) and X1 (for the server). The server first "rotates" its table using its input share X1 and then masks it with a freshly sampled uniform random mask R01. The client then fetches an item from this masked, rotated table using its own input share X0 and symmetric PIR. The retrieved item, which is T(X) + R01, forms a secret sharing of the desired table value T(X) when combined with the server's mask R01. This symmetric PIR-based protocol offers several advantages: sublinear communication, lightweight client computation, and confidentiality for the lookup table. However, its major drawback is poor concrete performance because the entire table needs to be reprepared (rotated and masked) for every single input query, making it impractical for large batches.

The critical insight driving FABLE's efficiency is the recognition that batching is a common workload in real-world applications. For instance, secure embedding lookup in ML often involves hundreds of words per text, each represented by multiple tokens, leading to large batches of tokens for lookup. Similarly, secure query execution involving table joins frequently deals with thousands of rows, necessitating large input batches. Therefore, FABLE proposes building its lookup table evaluation protocol on top of batch PIR to achieve significantly better amortized performance.

An overview of Batch PIR involves several steps:

1. The server encodes its database into multiple buckets.
2. The client maps its input queries to queries for each bucket through a process called query translation, which typically involves cuckoo hashing.
3. The translated queries are then used to fetch corresponding items from each bucket using PIR.
4. Finally, the retrieved items are combined to recover the desired responses.

Adapting batch PIR to the specific requirements of secure lookup table evaluation in 2PC presents two main technical challenges, which FABLE addresses with novel protocols:

Challenge 1: Building Efficient Query Translation in 2PC.

Traditional batch PIR relies on clients performing complex query translation, often involving cuckoo hashing. Doing this directly in 2PC is computationally expensive. FABLE tackles this in two ways:

• A. Input Deduplication: Cuckoo hashing generally cannot tolerate duplicate inputs. This necessitates a deduplication protocol at the beginning to remove duplicates and an expansion protocol at the end to reintroduce them into the output. In prior baselines, these were treated as separate, often expensive, protocols. FABLE introduces a set of novel protocols that leverage a caching mechanism. The result from the first half of the deduplication protocol is cached and then reused in the later half, specifically during the expansion protocol. This innovative caching strategy leads to substantial efficiency gains, saving up to 84.1% in communication compared to baseline approaches for deduplication and expansion.
• B. Offloading Cuckoo Hashing: Performing cuckoo hashing directly in 2PC is impractical due to its complexity. FABLE intelligently offloads this computation to the client's pre-processing phase while still maintaining privacy. This is achieved by first obfuscating the input using an Oblivious Pseudo-Random Function (OPRF), transforming the client's private inputs into pseudo-random IDs. These IDs are then offloaded to the client, who performs the cuckoo hashing locally to generate the translated queries. These translated queries are subsequently used to query the lookup table using PIR by keywords. This design ensures that the client's raw input remains private, even though the client performs a computationally intensive part of the query translation.

Challenge 2: Protecting the Lookup Table's Confidentiality in Batch PIR.

State-of-the-art batch PIR protocols, while efficient, do not inherently ensure symmetric security, meaning they might leak information about the database itself beyond the specific queried items. This is a critical concern for confidential lookup tables. FABLE observes that modern batch PIRs primarily use homomorphic ciphertexts for interaction. Therefore, the primary task is to prevent information leakage from these ciphertexts. FABLE employs two specific techniques for this:

• Database masking: This technique protects the encrypted messages within the ciphertexts, ensuring that the underlying database content remains hidden.
• Noise flooding: This technique specifically protects the noise components within the homomorphic ciphertexts, preventing an adversary from deducing information about the database by analyzing changes in noise.

The culmination of these innovations is a protocol that, in terms of asymptotic complexity, stands out. FABLE is the only solution presented that achieves both sublinear client computation and sublinear communication complexity, a significant theoretical and practical improvement over prior works that often exhibit linear or superlinear scaling in one or both metrics.

Demo / Proof of Concept

▶ Watch: Overview of Batch PIR and adapting it to 2PC (8:30)

While the talk does not detail a live demonstration in the traditional sense, the authors provide compelling benchmarking results against existing state-of-the-art protocols in the context of the motivating applications. These benchmarks serve as a robust proof of concept, illustrating FABLE's concrete efficiency and practicality.

For the application of secure embedding lookup in machine learning inference, FABLE was benchmarked against Crypton as the baseline protocol. Crypton is a well-known framework for privacy-preserving ML. To accurately assess the performance, the cost of generating multiplicative triples, a common operation in 2PC, was benchmarked using Motion. The results were striking: FABLE achieved a speedup of more than 400 times compared to the Crypton baseline for this critical ML workload. This dramatic improvement highlights FABLE's potential to enable real-time or near real-time private ML inference where embedding lookups are bottleneck operations.

In the context of the second motivating application, secure query execution involving table joins in data analytics, FABLE was benchmarked against the sort-compare-shuffle circuit from Senate. Senate is another established framework for privacy-preserving data analytics. For this application, FABLE demonstrated a substantial 15 times speed up. This indicates that FABLE can significantly reduce the computational overhead associated with complex privacy-preserving data analytics queries, making it a viable solution for organizations dealing with large, sensitive datasets.

These performance figures are not merely incremental improvements; they represent orders of magnitude speedups, which are crucial for transitioning privacy-preserving technologies from theoretical constructs to practical deployments. The benchmarks effectively demonstrate that FABLE is not just an asymptotically efficient protocol but also concretely efficient, making it a powerful tool for building scalable and confidential systems in real-world scenarios.

Defensive Implications

▶ Watch: Challenge 2: Protecting lookup table confidentiality (11:55)

The FABLE protocol offers significant defensive implications for organizations and individuals concerned with data privacy and security, particularly in the realms of machine learning and data analytics. By providing a highly efficient and private method for confidential lookup table evaluation, FABLE enables a new paradigm for secure computation.

Firstly, FABLE directly addresses the challenge of data confidentiality during computation. In scenarios like secure embedding lookup for ML, sensitive client input tokens can be processed against a server's proprietary and confidential embedding table without either party revealing their private data. This minimizes the risk of data leakage and intellectual property theft, as the server's valuable model components (embedding tables) remain hidden, and the client's sensitive inputs are never exposed in plaintext. This capability is paramount for industries handling personally identifiable information (PII), medical records, or proprietary business data.

Secondly, the protocol's lightweight client computation and concretely efficient server computation mean that privacy-preserving applications built on FABLE are more accessible and practical. This allows for the deployment of confidential computing solutions on a wider range of client devices, potentially including mobile or edge devices, without imposing prohibitive computational burdens. For defenders, this means that security can be integrated earlier in the data processing pipeline, closer to the data source, enhancing the overall security posture.

Thirdly, FABLE's scalability to large tables makes it suitable for enterprise-level privacy-preserving analytics. Organizations can now perform complex data joins and analyses across mutually distrusting parties or on sensitive internal datasets without centralizing raw data, which often creates a single point of failure and a high-value target for adversaries. By reducing the need to expose sensitive datasets for analysis, FABLE inherently reduces the attack surface and the potential impact of a data breach.

Finally, FABLE's advancements in batching and optimized query translation contribute to improved system resilience. The ability to process large batches of queries efficiently means that privacy-preserving systems can handle higher throughput, reducing latency and making them more viable for operational use. This not only enhances user experience but also allows security measures to be integrated without compromising the system's performance, a common trade-off in security implementations. Defenders should consider integrating FABLE or similar batch PIR-based solutions into their privacy-preserving architectures to enhance data protection in distributed and multi-party computational environments.

Key Takeaways

• FABLE is a novel protocol designed for scalable and efficient confidential lookup table evaluation in a 2PC setting, addressing critical limitations of prior work.
• It uniquely achieves lightweight client computation, concretely efficient server computation, scalable communication, and lookup table confidentiality simultaneously.
• The protocol's core idea combines Private Information Retrieval (PIR) for scalability, symmetric security for table confidentiality, and batching techniques for amortized efficiency.
• FABLE introduces innovative solutions for efficient query translation in 2PC, including a caching mechanism for deduplication/expansion that saves 84.1% communication and offloading cuckoo hashing to client pre-processing using OPRF.
• It protects lookup table confidentiality in batch PIR by employing database masking and noise flooding to prevent information leakage from homomorphic ciphertexts.
• FABLE demonstrates significant practical performance gains, achieving over 400 times speed up for secure ML embedding lookup and 15 times speed up for secure data analytics table joins compared to existing baselines.

About the Speaker(s)

Zhengyuan Su presented the FABLE protocol. At the time of this work, Zhengyuan Su was an undergraduate student at Tsinghua University. This research was a collaborative effort, undertaken as a joint work with Ti Simon and Wing from Carnegie Mellon University (CMU). The presentation highlighted Su's contributions to developing a scalable and efficient protocol for confidential lookup table evaluation within a two-party computation framework.