International Association
for Cryptologic Research

Homomorphic Secret Sharing (HSS) allows clients to split their inputs among several servers, and supports the servers to homomorphically evaluate public functions over their local shares, such that the function value of the inputs can be efficiently reconstructed from the output shares of the servers. For all existing schemes, all servers are required to participate in the reconstruction process, and the reconstruction will fail even if one server is missing. In this work, we study HSS that supports threshold reconstruction, where the reconstruction still works even if a few servers fail. We first formalize the syntax and security notions of threshold HSS in the public-key setup model, which is a popular model in the literature. Then we present a new generic construction of HSS, which is the first construction that enjoys both threshold reconstruction and public reconstruction. To this end, we introduce a refined version of functional encryption, named HSS-friendly functional encryption. Furthermore, we instantiate our construction with quadratic functional encryption schemes modified from existing works. Compared with the state-of-the-art, our concrete scheme achieves the threshold reconstruction at the expense of slightly increasing the communication complexity.

Private set intersection (PSI) allows Sender holding a set \(X\) and Receiver holding a set \(Y\) to compute only the intersection \(X\cap Y\) for Receiver. We focus on a variant of PSI, called fuzzy PSI (FPSI), where Receiver only gets points in \(X\) that are at a distance not greater than a threshold from some points in \(Y\). Most current FPSI approaches first pick out pairs of points that are potentially close and then determine whether the distance of each selected pair is indeed small enough to yield FPSI result. Their complexity bottlenecks stem from the excessive number of point pairs selected by the first picking process. Regarding this process, we consider a more general notion, called fuzzy mapping (Fmap), which can map each point of two parties to a set of identifiers, with closely located points having a same identifier, which forms the selected point pairs. We initiate the formal study on Fmap and show novel Fmap instances for Hamming and \(L_\infty\) distances to reduce the number of selecte