Search papers, labs, and topics across Lattice.
This paper introduces a new Distributed Point Function (DPF) construction for the multi-party setting that leverages the Decisional Diffie-Hellman (DDH) assumption to reduce key sizes. The proposed scheme achieves an $O(\sqrt[3]{N})$ key size for honest-majority DPFs, a significant improvement over existing schemes with $O(\sqrt{N})$ or exponential key sizes. Benchmarks demonstrate up to a 10x reduction in key size compared to state-of-the-art methods on realistic problem instances, and the technique is extended to support comparison functions.
Multi-party function secret sharing just got a whole lot more practical: a new DDH-based scheme slashes key sizes by up to 10x.
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.
