Cryptology ePrint Archive: Report 2007/167

Public Key Broadcast Encryption with Low Number of Keys and Constant Decryption Time (Version 2)

Yi-Ru Liu, Wen-Guey Tzeng

Abstract: In this paper we propose two public key BE schemes that have efficient complexity measures. The first scheme, called the PBE-PI scheme, has $O(r)$ header size, $O(1)$ public keys and $O(\log N)$ private keys per user, 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 match those of efficient secret key BE schemes. \par Our second scheme, called the PBE-SD-PI scheme, has $O(r)$ header size, $O(1)$ public key and $O(\log N)$ private keys per user also. However, its 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. Overall, this is the most efficient public key BE scheme up to now. \par Our basic schemes are one-way secure against {\em full collusion of revoked users} in the random oracle model under the BDH assumption. We modify our schemes to have indistinguishably security against adaptive chosen ciphertext attacks.

Category / Keywords: public-key cryptography /

Publication Info: broadcast encryption

Date: received 6 May 2007, last revised 31 Mar 2008

Contact author: wgtzeng at cs nctu edu tw

Available formats: PDF | BibTeX Citation

Note: Improved version

Version: 20080401:020637 (All versions of this report)

Discussion forum: Show discussion | Start new discussion