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 $2lambda$-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.