FABLE: Batched Evaluation on Confidential Lookup Tables in 2PC
Zhengyuan Su
34th USENIX Security Symposium (USENIX Security '25) · Day 1 · Crypto 1: Zero Knowledge and Multi-Party Computation
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.
AI review
Solid USENIX-caliber cryptographic systems paper presenting a genuinely novel protocol that simultaneously hits properties prior work couldn't combine. The 400x speedup on embedding lookup and 15x on table joins aren't marketing numbers — they reflect real amortization gains from a well-engineered batch PIR adaptation. The OPRF-based cuckoo hash offloading and caching trick for dedup/expansion are clever contributions that will matter to anyone building production 2PC systems.