Paper 2024/937
Distributed Point Function with Constraints, Revisited
Keyu Ji, Zhejiang University
Bingsheng Zhang, Zhejiang University
Hong-Sheng Zhou, Virginia Commonwealth University
Kui Ren, Zhejiang University
Abstract
Distributed Point Function (DPF) provides a way for a dealer to split a point function into multiple succinctly described function-shares, where the function for a special input , returns a special output value , and returns a fixed value otherwise. As the security requirement, any strict subset of the function-shares reveals nothing about the function . However, each function-share can be individually evaluated on the common input , and these evaluation results can then be merged together to reconstruct the value .
Recently, Servan-Schreiber et al. (S&P 2023) investigate the access control problem for DPF; namely, the DPF evaluators can ensure that the DPF dealer is authorized to share the given function with privacy assurance. In this work, we revisit this problem, introducing a new notion called DPF with constraints; meanwhile, we identify that there exists a subtle flaw in their privacy definition as well as a soundness issue in one of their proposed schemes due to the lack of validation of the special output value . Next, we show how to reduce both the storage size of the constraint representation and the server's computational overhead from to , where is the number of authorized function sets. In addition, we show how to achieve fine-grained private access control, that is, the wildcard-style constraint for the choice of the special output . Our benchmarks show that the amortized running time of our logarithmic storage scheme is - faster than the state-of-the-art when . Furthermore, we provide the first impossibility and feasibility results of the DPF with constraints where the evaluators do not need to communicate with each other.