Efficient broadcast encryption using multiple interpolation methods

Eun Sun Yoo, Nam Su Jho, Jung Hee Cheon, Myung Hwan Kim

Research output: Contribution to journalConference articlepeer-review

12 Scopus citations


We propose a new broadcast encryption scheme based on polynomial interpolations. Our scheme, obtained from the Naor-Pinkas scheme by partitioning the user set and interpolating multiple polynomials, turns out to be better in efficiency than the best known broadcast schemes like the Subset Difference and the Layered Subset Difference methods, which are tree based schemes. More precisely, when r users are revoked among n users, our method requires O(log(n/m)) user keys and O(αr + m) transmission overhead in the worst case, where m is the number of partitions of the user set and can be chosen to optimize its efficiency, and α is a predetermined constant satisfying 1 < α < 2. So, our scheme is always better in the storage than the tree based schemes (whose storage overhead is O(log2 n) or O(log 3/2 n)). In the transmission overhead, our scheme beats those schemes except for a very small r/n. The computation cost is worse than the other schemes but is reasonable for systems with moderate computing power. The security proof is given based on the computational Diffie-Hellman problem.

Original languageEnglish
Pages (from-to)87-103
Number of pages17
JournalLecture Notes in Computer Science
StatePublished - 2005
Event7th International Conference on Information Security and Cryptology - ICISC 2004 - Seoul, Korea, Republic of
Duration: 2 Dec 20043 Dec 2004


  • Broadcast encryption
  • Interpolation
  • Partition


Dive into the research topics of 'Efficient broadcast encryption using multiple interpolation methods'. Together they form a unique fingerprint.

Cite this