International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Public Key Broadcast Encryption with Low Number of Keys and Constant Decryption Time

Authors:
Yi-Ru Liu
Wen-Guey Tzeng
Download:
URL: http://eprint.iacr.org/2007/167
Search ePrint
Search Google
Abstract: In this paper we propose two public-key BE schemes that have efficient complexity measures. The first scheme, called the BE-PI scheme, has $O(r)$ header size, $O(1)$ public keys and $O(\log N)$ private keys, where $r$ is the number of revoked users. This is the first public-key BE scheme that has both public and private keys under $O(\log N)$ while the header size is $O(r)$. These complexity measures of the header size and private keys also match those of efficient secret-key broadcast encryption schemes. \par Our second scheme, called the PK-SD-PI scheme, has $O(r)$ header size, $O(1)$ public key and $O(\log^2 N)$ private keys. They are the same as those of the SD scheme. % Nevertheless, the decryption time is remarkably $O(1)$. % This is the first public-key BE scheme that has $O(1)$ decryption time while other complexity measures are kept low. The PK-LSD-PI scheme can be constructed in the same way. % It has $O(r/\epsilon)$ ciphertext size and $O(\log^{1+\epsilon} N)$ private keys, where $0<\epsilon<1$. The decryption time is also $O(1)$. \par Our basic schemes are one-way secure against {\em full collusion of revoked users}. With a slight modification, we make both schemes indistinguishably secure against the adaptive chosen ciphertext attack. The BE-PI scheme has the capability of {\em tracing traitors}. It is able to find out what private keys are used in a confiscated decoding box.
BibTeX
@misc{eprint-2007-13449,
  title={Public Key Broadcast Encryption with Low Number of Keys and Constant Decryption Time},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  url={http://eprint.iacr.org/2007/167},
  note={broadcast encryption wgtzeng@cs.nctu.edu.tw 13640 received 6 May 2007},
  author={Yi-Ru Liu and Wen-Guey Tzeng},
  year=2007
}