Abstract
We define and study a new cryptographic primitive, named OneOne Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string K, where Alice in addition holds a predicate f:[N] → {0,1} and Bob in addition holds an input x ∈ [N]. We then let Alice generate a key K_f based on f and K, and let Bob evaluate a value K_x based on x and K. We consider a third party that sees the values (x,f,K_f) and the goal is to allow her to reconstruct K_x whenever f(x)=1, while keeping K_x pseudorandom whenever f(x)=0. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query.
We focus on the informationtheoretic setting, where the oneone cPRF has perfect correctness and perfect security. Our main results are as follows.
1) A Lower Bound. We show that in the informationtheoretic setting, any oneone cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGMbased punctured PRF from OWF, which is in particular a oneone cPRF. This also implies a similar lower bound for all NC1.
2) New Constructions. On the positive side, we present efficient informationtheoretic constructions of oneone cPRFs for a few other predicate families, such as equality predicates, innerproduct predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity.
3) An Amplification to standard cPRF. We show that all of our oneone cPRF constructions can be amplified to a standard (singlekey) cPRF via any keyhomomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the doublekey model which allows to construct constrained PRFs via keyhomomorphic PRFs.
4) Relation to CDS. We show that oneone constrained PRFs imply conditional disclosure of secrets (CDS) protocols. We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of oneone constrained PRFs and our doublekey model will be found in the future, in addition to those we show in this paper.
BibTeX  Entry
@InProceedings{peter_et_al:LIPIcs:2020:12118,
author = {Naty Peter and Rotem Tsabary and Hoeteck Wee},
title = {{OneOne Constrained Pseudorandom Functions}},
booktitle = {1st Conference on InformationTheoretic Cryptography (ITC 2020)},
pages = {13:113:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771511},
ISSN = {18688969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12118},
URN = {urn:nbn:de:0030drops121188},
doi = {10.4230/LIPIcs.ITC.2020.13},
annote = {Keywords: Constrained pseudorandom functions, function secretsharing, conditional disclosure of secrets}
}
Keywords: 

Constrained pseudorandom functions, function secretsharing, conditional disclosure of secrets 
Collection: 

1st Conference on InformationTheoretic Cryptography (ITC 2020) 
Issue Date: 

2020 
Date of publication: 

04.06.2020 