Paper 2024/823

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 ($\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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
function secret sharinghomomorphic secret sharing
Contact author(s)
lpiske @ asu edu
sing1361 @ purdue edu
nitrieu @ asu edu
History
2024-12-15: revised
2024-05-26: received
See all versions
Short URL
https://ia.cr/2024/823
License
Creative Commons Attribution
CC BY

BibTeX

@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.