Paper 2026/2903

Batched Function Secret Sharing: Parallel Generation and Key Compression

Tianpei Lu, The State Key Laboratory of Blockchain and Data Security, Zhejiang University
Keyu Ji, The State Key Laboratory of Blockchain and Data Security, Zhejiang University
Yuntian Chen, Northwest University
Yuan Zhao, Ant Group
Shoumeng Yan, Ant Group
Bingsheng Zhang, The State Key Laboratory of Blockchain and Data Security, Zhejiang University
Kui Ren, The State Key Laboratory of Blockchain and Data Security, Zhejiang University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.