Paper 2025/978

Multi-Party Distributed Point Functions with Polylogarithmic Key Size from Invariants of Matrices

Abstract

Distributed point functions (DPFs), introduced in 2014, are a widely used primitive in secure computation for a wide variety of applications. However, until recently, constructions for DPFs with polylogarithmic keys were known only for the two-party setting, multi-party schemes have key sizes exponential in the number of parties or the domain size. We generalize the efficient tree-based two-party DPF approach and get a scheme for a polylogarithmic-size DPF for an any number of parties. We use a technique where we have the invariant for off-path leaves such that secret-shared vector is mapped to secret submodules by public matrices. We show, using a technique by Shamir, that these vectors are hard to compute over $\mathbb{Z}_{pq}$ if factoring is hard. Our scheme is a secure DPF under two new assumptions related to Generic Group Model and the Linear Code Equivalence. The output of our scheme is in the exponent in some group where Diffie-Hellman type problems are hard which limits the usability of the scheme. Still, it is the first multi-party DPF generalizing the tree-based two-party DPF approach. Our scheme is the first where the key is polylogarithmic in the domain size and independent of the number of parties and the key generation and evaluation can be computed efficiently independently of the number of parties.

Note: This version considers updates to the proposed scheme, including updates to the underlying hardness assumptions. A longer description of the changes appears at the beginning of the paper file.