2026-08-14T00:27:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27095 2026-08-12T06:00:27Z ddc:004 open_access

Limits on the Power of Private Constrained PRFs Bi, Mengda Ma, Yaohua Dai, Chenxin Black-box Separations Private Constrained PRFs Key Agreement Private constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don't know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key primitives such as public-key encryption and secret-key agreement. In this work, we prove the black-box separation between a 1-key secure PCPRF for any predicate and a secret-key agreement, which is the first black-box separation result about PCPRF. Specifically, we prove that there exists an oracle relative to which 1-key secure PCPRFs exist while secret-key agreement does not. Our proof is based on the simulation-based technique proposed by Impagliazzo and Rudich (STOC 89). The main technical challenge in generalizing the simulation-based technique to PCPRF is the issue of unfaithfulness of Eve’s simulation to the real world because our oracle is more complicated than a random oracle. We introduce a new technique which we call the "weighting" technique and show how to leverage it to circumvent the issue of unfaithfulness in the proof framework of Impagliazzo and Rudich. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mengda Bi and Yaohua Ma and Chenxin Dai 2026 Is Part Of LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2026.2 urn:nbn:de:0030-drops-270952 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode