Paper 2026/1874
Collusion-Resistant Constrained PRFs for Compute-&-Compare Predicates from LWE
, University of Wisconsin–MadisonAbstract
We design the first collusion-resistant constrained PRFs (CPRFs) for a non-trivial and expressive class of constraints from standard LWE. The two predicate classes for which we design CPRFs are: compute-&-compare and predicated range constraints. We improve our CPRF for compute-&-compare predicates to also satisfy collusion-resistant constraint privacy. An additional feature of our CPRFs is that they also satisfy (almost-)key-homomorphic property. Prior to this work, we did not have any post-quantum collusion-resistant CPRF beyond prefixfixing constraints, and collusion-resistant CPRFs for expressive predicates relied on either code obfuscation or multilinear maps. As an immediate application, we obtain a two-sided predicate encryption (PE) and functional encryption (FE) for the compute-&-compare class in the symmetric-key setting. Prior to this work, we did not have any post-quantum construction for 2-sided PE/FE beyond inner product predicates. An important contribution of this work is to introduce a new framework of purifying functionality. The main motivation behind our new framework is to systematically eliminate zeroizing attacks, which have been a highly successful cryptanalysis paradigm for breaking various candidates for advanced cryptographic objects.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in CRYPTO 2026
- DOI
- 10.1007/978-3-032-35367-2_17
- Keywords
- Constrained PRFs
- Contact author(s)
-
jiaqicheng @ cs wisc edu
rishab @ cs wisc edu - History
- 2026-09-06: approved
- 2026-09-02: received
- See all versions
- Short URL
- https://ia.cr/2026/1874
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1874,
author = {Jiaqi Cheng and Rishab Goyal},
title = {Collusion-Resistant Constrained {PRFs} for Compute-&-Compare Predicates from {LWE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1874},
year = {2026},
doi = {10.1007/978-3-032-35367-2_17},
url = {https://eprint.iacr.org/2026/1874}
}
