International Association for Cryptologic Research

International Association
for Cryptologic Research


How to Use (Plain) Witness Encryption: Registered ABE, Flexible Broadcast, and More

Cody Freitag , Boston University
Brent Waters , UT Austin and NTT Research
David J. Wu , UT Austin
DOI: 10.1007/978-3-031-38551-3_16 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Witness encryption (WE) is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of WE essentially relied on indistinguishability obfuscation (iO), recent works have shown new pathways for direct constructions of WE that are significantly more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using WE to realize advanced cryptographic primitives previously only known to exist in ``obfustopia.'' In this work, we give new constructions of trustless encryption schemes from plain witness encryption (and the learning-with-errors assumption) that were previously only known from iO: (1) a distributed broadcast encryption scheme (a broadcast encryption scheme where users choose their own secret keys); and (2) registered attributed-based encryption scheme (a system where users choose their own keys and then register their public key together with their attributes with a deterministic and transparent key curator). We also show how to use our techniques to obtain an optimal broadcast encryption scheme in the random oracle model. Underlying our constructions is a novel technique for using witness encryption based on a new primitive which we call function-binding hash functions. Whereas a somewhere statistically binding hash function binds a digest to a few bits of the input, a function-binding hash function binds a digest to the output of a function of the inputs. As we demonstrate in this work, function-binding hash functions provide us new ways to leverage the power of plain witness encryption and use it as the foundation of advanced cryptographic primitives. Finally, we show how to build function-binding hash functions for the class of disjunctions of block functions from leveled homomorphic encryption; this in combination with with witness encryption yields our main results.
  title={How to Use (Plain) Witness Encryption: Registered ABE, Flexible Broadcast, and More},
  author={Cody Freitag and Brent Waters and David J. Wu},