Registration-Based Encryption: Definitions, Constructions, and Lower Bounds
In this work, we will address a fundamental issue with the identity based encryption (IBE) which is the trust that we need to put in some entity which we call private key generator (PKG). We propose a new primitive that we call registration based encryption (RBE) to address the PKG issue of IBE, while maintaining its important characteristics. In our proposed RBE scheme people register their own sampled public and secret keys to a---not necessarily trusted---``key curator'' who will update a public parameter when new people register. The encryption algorithm is the same as the one used in IBE, which takes public parameter and some message as well as the identity of the receiver as input, and outputs an encrypted ciphertext. For decryption, the decryptor might need some additional information connecting their public/secret keys to the public parameter, which can be obtained from the key curator. More formally, assuming n is the number of registered identities and k is the security parameter, our proposed RBE scheme must have the following properties:
1- The length of public parameter be always poly(k,log n).
2- Any decryptor will ask for additional information (update) at most O(log n) times from the key curator.
3- The total size of additional information a decryptor ever needs is at most poly(k,log n).
4- The key curator can do either registration or sending additional information in time poly(k,log n).
Finally we propose a construction of RBE based on indistinguishability obfuscation assumption, and we show that having at least one update is necessary in any RBE scheme.
Committee:
- Mohammad Mahmoody (Advisor)
- David Wu (Committee Chair)
- Dave Evans
- Yuan Tian