A constrained pseudorandom function F: K × X → Y for a family T ⊆ 2X of subsets of X is a function where for any key k ∈ K and set S ∈ T one can efficiently compute a constrained key kS which allows to evaluate F (k, ·) on all inputs x ∈ S, while even given this key, the outputs on all inputs x ∉ S look random. At Asiacrypt’13 Boneh and Waters gave a construction which supports the most general set family so far. Its keys kc are defined for sets decided by boolean circuits C and enable evaluation of the PRF on any x ∈ X where C(x) = 1. In their construction the PRF input length and the size of the circuits C for which constrained keys can be computed must be fixed beforehand during key generation. We construct a constrained PRF that has an unbounded input length and whose constrained keys can be defined for any set recognized by a Turing machine. The only a priori bound we make is on the description size of the machines. We prove our construction secure assuming publiccoin differing-input obfuscation. As applications of our constrained PRF we build a broadcast encryption scheme where the number of potential receivers need not be fixed at setup (in particular, the length of the keys is independent of the number of parties) and the first identity-based non-interactive key exchange protocol with no bound on the number of parties that can agree on a shared key.
Supported by the European Research Council, ERC Starting Grant (259668-PSPC).
413 - 428
CT-RSA: Topics in Cryptology
San Francisco, CA, USA
2016-02-29 – 2016-03-04
Abusalah HM, Fuchsbauer G, Pietrzak KZ. Constrained PRFs for unbounded inputs. In: Vol 9610. Springer; 2016:413-428. doi:10.1007/978-3-319-29485-8_24
Abusalah, H. M., Fuchsbauer, G., & Pietrzak, K. Z. (2016). Constrained PRFs for unbounded inputs (Vol. 9610, pp. 413–428). Presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA: Springer. https://doi.org/10.1007/978-3-319-29485-8_24
Abusalah, Hamza M, Georg Fuchsbauer, and Krzysztof Z Pietrzak. “Constrained PRFs for Unbounded Inputs,” 9610:413–28. Springer, 2016. https://doi.org/10.1007/978-3-319-29485-8_24.
H. M. Abusalah, G. Fuchsbauer, and K. Z. Pietrzak, “Constrained PRFs for unbounded inputs,” presented at the CT-RSA: Topics in Cryptology, San Francisco, CA, USA, 2016, vol. 9610, pp. 413–428.
Abusalah HM, Fuchsbauer G, Pietrzak KZ. 2016. Constrained PRFs for unbounded inputs. CT-RSA: Topics in Cryptology, LNCS, vol. 9610. 413–428.
Abusalah, Hamza M., et al. Constrained PRFs for Unbounded Inputs. Vol. 9610, Springer, 2016, pp. 413–28, doi:10.1007/978-3-319-29485-8_24.
IST-2017-764-v1+1_279.pdf 495.18 KB
Material in IST:
Dissertation containing IST record