Welcome to the resource topic for 2024/823
Title:
Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing
Authors: Lucas Piske, Jaspal Singh, Ni Trieu
Abstract:A function secret sharing (FSS) scheme (\mathsf{gen},\mathsf{eval}) for a class of programs \mathcal{F} allows a dealer to secret share any function f \in \mathcal{F}, such that each function share hides the function, and the shares can be used to non-interactively compute additive shares of f(x) for any input x. All FSS related applications often requires the dealer to generate and share secret sharings for a batch of functions.
We initiate the study of batched function secret sharing - where the objective is to secret share a set of functions from the class \mathcal{F} while minimizing the size of the collection of FSS keys.
We use standard homomorphic secret sharing (HSS) schemes, variant of the Learning with Parity Noise assumption and the Quadratic Residuosity assumption to construct batched FSS schemes for point functions with single-bit and multi-bit output. Our scheme is asymptotically superior than naively batching state of the art FSS schemes for point functions. Concretely our batch key sizes are smaller by a factor of 3-80\times as batch size is increased from 2^{13} to 2^{19}. Although our protocol relies on public key operations, it exhibits inefficiency in a LAN setting. However, it demonstrates up to a 120-fold improvement in a WAN setting with slow network bandwidth.
As a building block in our protocols, we introduce a new HSS ciphertext compression algorithm, that can decompress a short compressed ciphertext to give low noise ciphertexts of array of input message bits. This primitive might be of independent interest for other HSS related applications.
ePrint: https://eprint.iacr.org/2024/823
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 .