International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Revocation Systems with Very Small Private Keys

Amit Sahai
Brent Waters
Search ePrint
Search Google
Abstract: In this work, we design a new public key broadcast encryption system, and we focus on a critical parameter of device key size: the amount of the cryptographic key material that must be stored securely on the receiving devices. Our new scheme has ciphertext size overhead O(r), where $r$ is the number of revoked users, and the size of public and private keys is only a constant number of group elements from an elliptic-curve group of prime order. All previous work, even in the restricted case of systems based on symmetric keys, required at least lg(n) keys stored on each device. In addition, we show that our techniques can be used to realize Attribute-Based Encryption (ABE) systems with non-monotonic access formulas, where are key storage is significantly more efficient than previous solutions. Our results are in the standard model under a new, but non-interactive, assumption.
  title={Revocation Systems with Very Small Private Keys},
  booktitle={IACR Eprint archive},
  note={ 14071 received 10 Jul 2008},
  author={Amit Sahai and Brent Waters},