Paper 2025/1766
Eliminating Exponential Key Growth in PRG-Based Distributed Point Functions
, University of Twente, French Institute for Research in Computer Science and AutomationAbstract
Distributed Point Functions (DPFs) enable sharing secret point functions across multiple parties, supporting privacy-preserving technologies such as Private Information Retrieval, and anonymous communications. While 2-party PRG-based schemes with logarithmic key sizes have been known for a decade, extending these solutions to multi-party settings has proven challenging. In particular, PRG-based multi-party DPFs have historically struggled with practicality due to key sizes growing exponentially with the number of parties and the field size. Our work addresses this efficiency bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al. (EUROCRYPT'15). By leveraging the honest-majority assumption, we eliminate the exponential factor present in this scheme. Our construction is the first PRG-based multi-party DPF scheme with practical key sizes, and provides key up to $3\times$ smaller than the best known multi-party DPF. This work demonstrates that with careful optimization, PRG-based multi-party DPFs can achieve practical performances, and even obtain top performances.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. DPM 2025
- Keywords
- Function Secret SharingDistributed Point FunctionDPFFSSMultiparty Computations
- Contact author(s)
- m f d damie @ utwente nl
- History
- 2025-09-30: approved
- 2025-09-27: received
- See all versions
- Short URL
- https://ia.cr/2025/1766
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2025/1766,
author = {Marc Damie and Florian Hahn and Andreas Peter and Jan Ramon},
title = {Eliminating Exponential Key Growth in {PRG}-Based Distributed Point Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1766},
year = {2025},
url = {https://eprint.iacr.org/2025/1766}
}
