Cryptology ePrint Archive: Report 2008/309

Revocation Systems with Very Small Private Keys

Allison Lewko and Amit Sahai and Brent Waters

Abstract: 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.

We believe that our new technique will be of use elsewhere as well.

Category / Keywords:

Date: received 10 Jul 2008, last revised 18 Nov 2009

Contact author: alewko at cs utexas edu

Available format(s): PDF | BibTeX Citation

Note: Newer version

Version: 20091118:230151 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]