Paper 2021/580

Lightweight, Verifiable Function Secret Sharing and its Applications

Leo de Castro and Antigoni Polychroniadou

Abstract

In this work, we present a lightweight construction of verifiable two-party function secret sharing (FSS) for point functions and multi-point functions. We use these verifiable FSS schemes to construct two-server private information retrieval and private set intersection that are secure \& verifiable in the face of any one malicious corruption. Our verifiability method is lightweight in two ways. Firstly, it is concretely very efficient, making use of only symmetric key operations and no MPC or linear PCP techniques. For security parameter $\lambda$, our verification procedure is simply to check if two $2\lambda$-bit strings match. Secondly, our verification procedure is essentially unconstrained. It will verify that distributed point function (DPF) shares correspond to some point function irrespective of the output group size, the structure of the DPF output, or the set of points on which the DPF must be evaluated. This is in stark contrast with prior works, which depended on at least one and often all three of these factors. In addition, we give a novel method for packing DPFs into shares of a multi-point function that allows for the number of nonzero points in the multi-point function to grow without growing the evaluation time. We also show how our verification scheme carries over to the multi-point setting. We give an implementation of our verifiable distributed point functions and our verifiable distributed multi-point function.