Revocation Systems with Very Small Private Keys

In this work, we design a method for creating public key broadcast encryption systems. Our main technical innovation is based on a new "two equation" technique for revoking users. This technique results in two key contributions: First, 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 emph{constant} number of group elements from an elliptic-curve group of prime order. In addition, the public key allows us to encrypt to an unbounded number of users. Our system is the first to achieve such parameters. We give two versions of our scheme: a simpler version which we prove to be selectively secure in the standard model under a new, but non-interactive assumption, and another version that employs the new dual system encryption technique of Waters to obtain adaptive security under the d-BDH and decisional Linear assumptions. Second, we show that our techniques can be used to realize Attribute-Based Encryption (ABE) systems with non-monotonic access formulas, where our key storage is significantly more efficient than previous solutions. This result is also proven selectively secure in the standard model under our new non-interactive assumption.