DDH-based schemes for multi-party Function Secret Sharing
This work addresses efficiency bottlenecks in multi-party DPFs, which are incremental improvements for applications like private information retrieval and machine learning.
The paper tackled the problem of large key sizes in multi-party Distributed Point Functions (DPFs), a type of Function Secret Sharing, by proposing a DDH-based technique that reduces key sizes to O(∛N) and achieves up to 10× smaller keys than state-of-the-art schemes on realistic problem sizes.
Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size. We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.