Constrained PRFs for Unbounded Inputs with Short Keys

摘要

A constrained pseudorandom function (CPRF) F: K × X → Y for a family T of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a short constrained key k_S, which allows to evaluate F(k, •) on all inputs x ∈ S, while the outputs on all inputs x is not an element of 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.