Paper 2016/279

Constrained PRFs for Unbounded Inputs with Short Keys

Hamza Abusalah and Georg Fuchsbauer

Abstract

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.

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},
      note = {\url{https://eprint.iacr.org/2016/279}},
      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.