TY - GEN

T1 - Public key broadcast encryption with low number of keys and constant decryption time

AU - Liu, Yi Ru

AU - Tzeng, Wen-Guey

PY - 2008/3/10

Y1 - 2008/3/10

N2 - In this paper we propose three 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(logN) 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(logN) while the header size is O(r). These complexity measures match those of efficient secret key BE schemes. 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 per user. 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 third scheme, called, the PK-LSD-PI scheme, is constructed in the same way, but based on the LSD method. It has O(r/ε) ciphertext size and O(log1∈+∈ε N) private keys per user, where 0∈<∈ε<∈1. The decryption time is also O(1). Our basic schemes are one-way secure against full collusion of revoked users in the random oracle model under the BDH assumption. We can modify our schemes to have indistinguishably security against adaptive chosen ciphertext attacks.

AB - In this paper we propose three 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(logN) 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(logN) while the header size is O(r). These complexity measures match those of efficient secret key BE schemes. 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 per user. 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 third scheme, called, the PK-LSD-PI scheme, is constructed in the same way, but based on the LSD method. It has O(r/ε) ciphertext size and O(log1∈+∈ε N) private keys per user, where 0∈<∈ε<∈1. The decryption time is also O(1). Our basic schemes are one-way secure against full collusion of revoked users in the random oracle model under the BDH assumption. We can modify our schemes to have indistinguishably security against adaptive chosen ciphertext attacks.

KW - Broadcast encryption

KW - Collusion

KW - Polynomial interpolation

UR - http://www.scopus.com/inward/record.url?scp=40249098618&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78440-1_22

DO - 10.1007/978-3-540-78440-1_22

M3 - Conference contribution

AN - SCOPUS:40249098618

SN - 354078439X

SN - 9783540784395

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 380

EP - 396

BT - Public Key Cryptography - PKC 2008 - 11th International Workshop on Practice and Theory in Public Key Cryptography, Proceedings

Y2 - 9 March 2008 through 12 March 2008

ER -