Paper 2006/279

On (Hierarchical) Identity Based Encryption Protocols with Short Public Parameters \\ (With an Exposition of Waters' Artificial Abort Technique)

Sanjit Chatterjee and Palash Sarkar

Abstract

At Eurocrypt 2005, Waters proposed an efficient identity based encryption (IBE) scheme. One drawback of this scheme is that the size of the public parameter is rather large. Our first contribution is a generalization of Waters scheme. In particular, we show that there is an interesting trade-off between the tightness of the security reduction and smallness of the public parameter size. For a given security level, this implies that if one reduces the public parameter size there is a corresponding increase in the computational cost. This introduces a flexibility in choosing the public parameter size without compromising in security. In concrete terms, to achieve $80$-bit security for 160-bit identities we show that compared to Waters protocol the public parameter size can be reduced by almost $90 \%$ while increasing the computation cost by $30\%$. Our second contribution is to extend the IBE protocol to a hierarchical IBE (HIBE) protocol which can be shown to be secure in the full model without the use of random oracle. A previous construction of a HIBE in the same setting is due to Waters. Our construction improves upon Waters' suggestion by significantly reducing the number of public parameters.

Note: Some changes have been made to the analysis in the Appendix.