Threshold Encrypted Search System from Function Secret Sharing

Abstract

We propose a novel multi-server threshold oblivious retrieval system (ThORY). Our construction extends DORY (a two-server non-threshold oblivious retrieval system proposed in USENIX OSDI 2020) to support arbitrary threshold access structures. The technical centrepiece of ThORY is threshold function secret sharing (TFSS) – an extension of traditional FSS that allows the key to be secret-shared across multiple servers following any arbitrary threshold access structure. We present novel constructions of TFSS based on either purely symmetric-key cryptoprimitives, or any seed-homomorphic pseudorandom generator (for the latter, we present two concrete instantiations from standard group-theoretic assumptions and plausibly quantum-safe lattice-based assumptions). Leveraging TFSS, ThORY achieves leakage-free keyword search and document identifier retrieval under a (t,p)-threshold model, hiding access, search, and volume patterns against any adversary corrupting fewer than t servers. We analyse and evaluate the security and performance of end-to-end implementations of ThORY based on each of these TFSS constructions. Our experiments demonstrate that ThORY scales efficiently with threshold size, outperforming state-of-the-art literature in query latency over large databases.