ESORICS 2014
Public-Key Revocation and Tracing Schemes with Subset Difference Methods Revisited
Kwangsu Lee, Woo Kwon Koo, Dong Hoon Lee, Jong Hwan Park
Broadcast encryption is a very powerful primitive since it can send an
encrypted message to a set of users excluding a set of revoked users.
Public-key broadcast encryption (PKBE) is a special type of broadcast
encryption such that anyone can run the encryption algorithm to create an
encrypted message by using a public key.
In this paper, we propose a new technique to construct an efficient PKBE
scheme by using the subset cover framework. First, we introduce a new concept
of public-key encryption named single revocation encryption (SRE) and propose
an efficient SRE scheme in the random oracle model. A user in SRE is
represented as a group that he belongs and a member in the group. In SRE, a
sender can create a ciphertext for a specified group where one member in the
group is revoked, and a receiver can decrypt the ciphertext if he belongs to
the group in the ciphertext and he is not revoked in the group.
Second, we show that the subset difference (SD) scheme (or the layered subset
difference (LSD) scheme) and an SRE scheme can be combined to construct a
public-key revocation encryption (PKRE) scheme such that a set of revoked
users is specified in a ciphertext. Our PKRE scheme using the LSD scheme
and our SRE scheme can reduce the size of private keys and public keys
by $\log N$ factor compared with the previous scheme of Dodis and Fazio.