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 encryptionBroadcast encryptionTraitor tracingTrace and revokeBilinear 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.