Simulation without the Artificial Abort: Simpler Proof and Improved Concrete Security for Waters' IBE Scheme

Authors:
Mihir Bellare and Thomas Ristenpart

Abstract:
Waters' variant of the Boneh-Boyen IBE scheme is attractive because of its efficency, applications, and security attributes, but suffers from a relatively complex proof with poor concrete security. This is due in part to the proof's ``artificial abort'' step, which has then been inherited by numerous derivative works. It has often been asked whether this step is necessary. We show that it is not, providing a new proof that eliminates this step. The new proof is not only simpler than the original one but offers better concrete security for important ranges of the parameters. As a result, one can securely use smaller groups, resulting in significant efficiency improvements.

References:
A preliminary version of this paper appears in Advances in Cryptology -- Eurocrypt '09, Lecture Notes in Computer Science Vol. --, A. Joux ed., Springer-Verlag, 2009.

Full Version:
Full version of the paper is available as a pdf.

List of Updates:
February 2009 - Put up full version of paper.