Paper 2026/2903
Batched Function Secret Sharing: Parallel Generation and Key Compression
Abstract
Function secret sharing (FSS) enables local evaluation of secret-shared functions and is an important building block for efficient secure computation, particularly for comparisons and private lookups. However, conventional tree-based distributed point functions (DPFs) and distributed comparison functions (DCFs) incur sequential dependencies during key generation and require $O(n\lambda)$-bit keys for fixed output length, where $n$ is the input length and $\lambda$ is the security parameter. We address these bottlenecks through parallel correction-word generation and compact key representation. By sampling the states along the target path in advance, we decouple correction computations across tree levels and enable their parallel generation. For compression, we give a shared-header batch representation under an explicit label-evaluation interface, using homomorphic seed expansion to reconstruct encrypted correction words locally. A uniform sublinear header bound makes the amortized key size approach $n+m$ bits per evaluator per function, where $m$ is the payload length. For 20-bit inputs, parallelization reduces the communication rounds for DPF and DCF from 72 and 1,048, respectively, to 13, while batched FSS requires only one round. Key compression reduces the key size to 1\% of that of conventional FSS schemes and achieves key-generation speedups ranging from $3\times$ to $40\times$.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
-
lutianpei @ zju edu cn
jikeyu @ zju edu cn
chenyt_x @ 163 com
caesar zy @ antgroup com
Shoumeng ysm @ antgroup com
bingsheng @ zju edu cn
kuiren @ zju edu cn - History
- 2026-11-21: approved
- 2026-11-16: received
- See all versions
- Short URL
- https://ia.cr/2026/2903
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2903,
author = {Tianpei Lu and Keyu Ji and Yuntian Chen and Yuan Zhao and Shoumeng Yan and Bingsheng Zhang and Kui Ren},
title = {Batched Function Secret Sharing: Parallel Generation and Key Compression},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2903},
year = {2026},
url = {https://eprint.iacr.org/2026/2903}
}