[Resource Topic] 2016/279: Constrained PRFs for Unbounded Inputs with Short Keys

Welcome to the resource topic for 2016/279

Constrained PRFs for Unbounded Inputs with Short Keys

Authors: Hamza Abusalah, Georg Fuchsbauer


A constrained pseudorandom function (CPRF) F \colon {\cal K} \times {\cal X} \to {\cal Y} for a family {\cal T} of subsets of \cal X is a function where for any key k \in {\cal K} and set S \in {\cal T} one can efficiently compute a short constrained key k_S, which allows to evaluate F(k,\cdot) on all inputs x \in S, while the outputs on all inputs x \notin S look random even given k_S. Abusalah et al. recently constructed the first constrained PRF for inputs of arbitrary length whose sets S are decided by Turing machines. They use their CPRF to build broadcast encryption and the first ID-based non-interactive key exchange for an unbounded number of users. Their constrained keys are obfuscated circuits and are therefore large. In this work we drastically reduce the key size and define a constrained key for a Turing machine M as a short signature on M. For this, we introduce a new signature primitive with constrained signing keys that let one only sign certain messages, while forging a signature on others is hard even when knowing the coins for key generation.

ePrint: https://eprint.iacr.org/2016/279

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .