Secure Full-Text Search Using Function Secret Sharing
Tomoki Uchiyama, Kana Shimizu · 2023
Secure full-text search enables searching for a string within a collection of documents while maintaining privacy. Despite recent studies on secure full-text search having achieved efficient round complexity, searches on large-scale databases remain impractical due to the significant communication overhead. Function Secret Sharing (FSS) is a recent paradigm that enables efficient secure two-party computations (2PC) in the preprocessing model with low communication overhead. In this study, we developed FssFMI, a communication-efficient full-text search protocol based on FSS. Compared to the state-of-the-art protocol, which requires O(l N) communication at the beginning of the online phase where l is the query length and N is the database length, our protocol requires only O(l) communication size while maintaining O(l) communication round complexity. The low communication overhead of FssFMI is achieved by evaluating functions for a full-text search using an FSS-based 2PC protocol, whereas the previous study computes the functions by referencing a precomputed lookup table based on the use of a large amount of correlated randomness. The O(l N) local computation required in FssFMI is the performance bottleneck, but its parallel-friendly nature easily scales to a large database. Our experimental results demonstrate that in a WAN environment, our protocol can search a database larger than 130 million letters for a query of length 16 in only 55 seconds using a single CPU core, with an online communication size of only 0.49 KB. Compared to the latest method, our protocol reduces communication overhead by more than seven orders of magnitude and achieves search speeds that are more than two orders of magnitude faster.