Abstract
Traditional private database search protocols often suffer from a linear-time bottleneck, requiring the server to process every item in the dataset to maintain privacy. This paper presents a novel approach that breaks this limitation by introducing a precomputation model. By shifting the $O(N)$ computational load to an offline phase, the proposed scheme achieves $O(\log N)$ query-time complexity, making private searches practical for significantly larger datasets.
Introduction
In Secure Multi-party Computation (SMC), privacy typically incurs a high performance cost. For a client to search a server's database without revealing the query, and without the client learning anything beyond the specific result, standard protocols necessitate that the server "touch" every record. If the server only accessed a subset of the data, it would leak information about the query's value or location. Consequently, most existing solutions scale linearly ($O(N)$) with the database size, rendering real-time queries on massive datasets unfeasible. This research aims to bridge this gap by enabling sublinear, specifically logarithmic, search times.
The Precomputation Model
The core innovation of this work is the bifurcation of the search process into two distinct phases:
- Precomputation Phase: Before a specific query is known, the server performs the necessary linear work on its dataset. It generates a "precomputation message"—which may be substantial in size—and transmits it to the client.
- Query Phase: Once the client initiates a query, the interaction with the server is optimized for speed. This phase is designed to be highly efficient, achieving $O(\log N)$ complexity.
Technical Implementation: Chained PEGLTs
To facilitate this model, the authors combine traditional structures with new cryptographic tools. The database is organized into a sorted Binary Search Tree. Private comparisons at each node are handled via Yao’s Garbled Circuits, while Oblivious Transfer (OT) allows the client to retrieve initial keys without revealing query bits.
The primary technical contribution is the development of Chained Permuted Encrypted Garbled Lookup Tables (PEGLTs). While linking garbled circuits for a search tree is inherently complex, Chained PEGLTs allow the client to "unlock" subsequent levels of the tree based on the output of the current comparison. Crucially, this process keeps the specific search path hidden from both the client and the server.
Comparative Performance Analysis
The proposed scheme was evaluated against a "Naive Scheme" (standard circuit-based Secure Function Evaluation) and traditional keyword search methods. As shown in Table 1, the proposed scheme significantly outperforms the naive approach in query-phase computation.
The results demonstrate that while the server's initial computation and the precomputation message size remain $O(N)$, the interactive query phase is reduced to $O(\log N)$ for the client. In empirical tests with datasets of up to 50,000 items (16-bit integers), the query evaluation time was less than 0.002 seconds, representing a near-flat growth curve compared to the linear growth of naive methods. Furthermore, the scheme minimizes expensive modular exponentiations during the query phase, maintaining $O(1)$ complexity for the server.
Limitations and Future Directions
Despite its efficiency, the current protocol has limitations. The precomputation is currently "one-time," meaning a new precomputation message is required for each subsequent query. Furthermore, the security model assumes "honest-but-curious" participants; future work is needed to address "malicious" actors who might deviate from the protocol. The authors suggest that future iterations could explore sharing precomputation across multiple queries or integrating Fully Homomorphic Encryption (FHE) for further optimization.
Summary updated