[Resource Topic] 2024/453: Verifiable Information-Theoretic Function Secret Sharing

Welcome to the resource topic for 2024/453

Verifiable Information-Theoretic Function Secret Sharing

Authors: Stanislav Kruglik, Son Hoang Dau, Han Mao Kiah, Huaxiong Wang, Liang Feng Zhang


A function secret sharing (FSS) (Boyle et al., Eurocrypt 2015) is a cryptographic primitive that enables additive secret sharing of functions from a given function family \mathcal{F}. FSS supports a wide range of cryptographic applications, including private information retrieval (PIR), anonymous messaging systems, private set intersection and more. Formally, given positive integers r \geq 2 and t < r, and a class \mathcal{F} of functions f: [n] \to \mathbb{G} for an Abelian group \mathbb{G}, an r-party t-private FSS scheme for \mathcal{F} allows a dealer to split each f \in \mathcal{F} into r function shares f_1, \ldots, f_r among r servers. Shares have the property that f = f_1 + \cdots + f_r and functions are indistinguishable for any coalition of up to t servers. FSS for point function f_{\alpha_1,\ldots,\alpha_l,\beta_1,\ldots,\beta_l} for different \alpha and l<}_{\alpha,\beta} that evaluate to \beta on inputs lesser than \alpha and to zero on all other inputs are known under the name of distributed comparison functions (DCF).

Most existing FSS schemes are based on the existence of one-way functions or pseudo-random generators, and as a result, hiding of function f holds only against computationally bounded adversaries. Protocols employing them as building blocks are computationally secure. Several exceptions mostly focus on DPF for four, eight or d(t+1) servers for positive integer d, and none of them provide verifiability.

In this paper, we propose DPF for d(t+l-1)+1 servers, where d is a positive integer, offering a better key size compared to the previously proposed DPF for d(t+1) servers and DCF for dt+1 servers, also for positive integer d. We introduce their verifiable extension in which any set of servers holding t keys cannot persuade us to accept the wrong value of the function. This verifiability notion differs from existing verifiable FSS schemes in the sense that we verify not only the belonging of the function to class \mathcal{F} but also the correctness of computation results. Our schemes provide a secret key size O(n^{1/d}\cdot s\log(p)) for DPF and O(n^{1/d}\cdot s\log(p)) for DCF, where p^s is the size of group \mathbb{G}.

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

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 .