Paper 2024/058
Constrained Pseudorandom Functions for Inner-Product Predicates from Weaker Assumptions
Abstract
In this paper, we build a framework for constructing Constrained Pseudorandom Functions (CPRFs) with inner-product constraint predicates, using ideas from subtractive secret sharing and related-key-attack security. Our framework can be instantiated using a random oracle or any suitable Related-Key-Attack (RKA) secure pseudorandom function. We provide three instantiations of our framework: 1. an adaptively-secure construction in the random oracle model; 2. a selectively-secure construction under the DDH assumption; and 3. a selectively-secure construction with a polynomial domain under the assumption that one-way functions exist. All three instantiations are constraint-hiding and support inner-product predicates, leading to the first constructions of such expressive CPRFs under each corresponding assumption. Moreover, while the OWF-based construction is primarily of theoretical interest, the random oracle and DDH-based constructions are concretely efficient, which we show via an implementation.
Note: This version fixes a mistake in Theorem 8 which impacts the one-way function based construction. The input domain of the construction is now restricted to be polynomial in the security parameter.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- pseudorandomconstrainedinnerproductprfcprfminicryptddhrkarom
- Contact author(s)
- 3s @ mit edu
- History
- 2024-04-22: last of 3 revisions
- 2024-01-15: received
- See all versions
- Short URL
- https://ia.cr/2024/058
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/058,
author = {Sacha Servan-Schreiber},
title = {Constrained Pseudorandom Functions for Inner-Product Predicates from Weaker Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2024/058},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/058}},
url = {https://eprint.iacr.org/2024/058}
}
