[Resource Topic] 2024/937: Distributed Point Function with Constraints, Revisited

Welcome to the resource topic for 2024/937

Distributed Point Function with Constraints, Revisited

Authors: Keyu Ji, Bingsheng Zhang, Hong-Sheng Zhou, Kui Ren


Distributed Point Function (DPF) provides a way for a dealer to split a point function f_{\alpha, \beta} into multiple succinctly described function-shares, where the function f_{\alpha, \beta} for a special input \alpha, returns a special output value \beta, and returns a fixed value 0 otherwise. As the security requirement, any strict subset of the function-shares reveals nothing about the function f_{\alpha,\beta}. However, each function-share can be individually evaluated on the common input x, and these evaluation results can then be merged together to reconstruct the value f_{\alpha, \beta}(x).

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 \beta. Next, we show how to reduce both the storage size of the constraint representation and the server’s computational overhead from O(N) to O(\log N), where N 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 \beta. Our benchmarks show that the amortized running time of our logarithmic storage scheme is 2\times - 3\times faster than the state-of-the-art when N=2^{15}. 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.

ePrint: https://eprint.iacr.org/2024/937

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .