Public-Key Revocation and Tracing Schemes with Subset Difference Methods Revisited

Kwangsu Lee; Woo Kwon Koo; Dong Hoon Lee; Jong Hwan Park

Paper 2013/228

Public-Key Revocation and Tracing Schemes with Subset Difference Methods Revisited

Kwangsu Lee, Woo Kwon Koo, Dong Hoon Lee, and Jong Hwan Park

Abstract

Trace and revoke is broadcast encryption with the traitor tracing functionality. It is a very powerful primitive since it can revoke users whose private keys are compromised by finding them using a tracing algorithm if a pirate decoder is given. Public-key trace and revoke (PKTR) is a special type of trace and revoke such that anyone can run the tracing algorithm and anyone can create an encrypted message by using a public key. Although public-key trace and revoke schemes are attractive tools, the currently known PKTR schemes are a little bit inefficient in terms of the private key size and the public key size compared with public-key broadcast encryption schemes. In this paper, we propose a new technique to construct an efficient PKTR 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. The universe of SRE consists of many groups and each group consists of many members. 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 a SRE scheme can be combined to construct a PKTR scheme. Our PKTR scheme using the LSD scheme and our SRE scheme has the ciphertext size of $O(r)$, the private key size of $O(\log^{1.5} N)$, and the public key size of $O(1)$ where $N$ is the total number of users in the system and $r$ is the size of a revoked set. Our PKTR scheme is the first one that achieves the private key size of $O(\log^{1.5} N)$ and the public key size of $O(1)$.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. ESORICS 2014
DOI: 10.1007/978-3-319-11212-1_1
Keywords: Public-key encryption Broadcast encryption Traitor tracing Trace and revoke Bilinear map
Contact author(s): guspin @ korea ac kr
History: 2015-06-23: last of 2 revisions; 2013-04-29: received; See all versions
Short URL: https://ia.cr/2013/228
License: CC BY

BibTeX

@misc{cryptoeprint:2013/228,
      author = {Kwangsu Lee and Woo Kwon Koo and Dong Hoon Lee and Jong Hwan Park},
      title = {Public-Key Revocation and Tracing Schemes with Subset Difference Methods Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/228},
      year = {2013},
      doi = {10.1007/978-3-319-11212-1_1},
      url = {https://eprint.iacr.org/2013/228}
}