Advertisement
Published in:
2016 | OriginalPaper | Chapter
Constrained PRFs for Unbounded Inputs with Short Keys
Authors : Hamza Abusalah, Georg Fuchsbauer
Published in: Applied Cryptography and Network Security
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A constrained pseudorandom function (CPRF) \(F:\mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}\) for a family \(\mathcal{T}\) of subsets of \(\mathcal X\) is a function where for any key \(k \in \mathcal{K}\) and set \(S\in \mathcal{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.