Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing
Lucas Piske, Arizona State University
Jaspal Singh, Purdue University West Lafayette
Ni Trieu, Arizona State University
Abstract
A function secret sharing (FSS) scheme () for a class of programs allows a dealer to secret share any function , such that each function share hides the function, and the shares can be used to non-interactively compute additive shares of for any input . 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 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 as batch size is increased from to . 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.
@misc{cryptoeprint:2024/823,
author = {Lucas Piske and Jaspal Singh and Ni Trieu},
title = {Batched Distributed Point Function from Sparse {LPN} and Homomorphic Secret Sharing},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/823},
year = {2024},
url = {https://eprint.iacr.org/2024/823}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.