Paper 2016/279

Constrained PRFs for Unbounded Inputs with Short Keys

Hamza Abusalah and Georg Fuchsbauer

Abstract

A constrained pseudorandom function (CPRF) F:K×XY for a family T of subsets of X is a function where for any key kK and set ST one can efficiently compute a short constrained key kS, which allows to evaluate F(k,) on all inputs xS, while the outputs on all inputs xS look random even given kS. 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 as a short signature on . 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Constrained PRFsunbounded inputs
Contact author(s)
fuchsbau @ di ens fr
History
2016-03-14: received
Short URL
https://ia.cr/2016/279
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/279,
      author = {Hamza Abusalah and Georg Fuchsbauer},
      title = {Constrained {PRFs} for Unbounded Inputs with Short Keys},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/279},
      year = {2016},
      url = {https://eprint.iacr.org/2016/279}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.