Exposure-resilience for free: The hierarchical ID-based encryption case

Y. Dodis, M. Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the problem of gradual key exposure, the secret key is assumed to be slowly compromised over time, so that more and more information about a secret key is eventually leaked. This models the general situation in the real world where memory, storage systems and devices cannot perfectly hide all information for long time. In this setting, in order to protect against exposure threats, the secret key is represented in an "exposure- resilient" form, which is periodically refreshed with the following guarantee: as long as the adversary does not learn "too much" information about the current representation of the secret between successive refreshes, the system should remain secure. To measure the efficiency of a given solution, one considers the "natural" secret key representation A, the "exposure- resilient" representation B, and examines the following three measures: (1) space loss which is the extra space required by B over A; (2) time loss which is the operation slowdown when B is used in place of A: and (3) exposure-resilience which is the fraction of B which can be "safely leaked". All the current solutions to the problem - including proactive secret sharing, all-or-nothing transforms and exposure-resilient functions - always suffered from non-trivial losses in both space and time in order to achieve varying levels of exposure-resilience. It was, therefore, informally believed that these losses are inevitable in even, reasonable application, since a "natural" representation A is unlikely to offer any exposure-resilience. We show this belief is false for the elegant "hierarchical identity-based encryption" (HIBE) of Gentry and Silverberg (2002), which is the only known fully junctional HIBE up to date. Specifically, we show that the natural secret key representation for the HIBE admits a simple and efficient refresh operation, which offers very high level of exposure-resilience, while incurring absolutely no space or time losses for decryption. We argue that this simple fact is quite powerful from a key storage security perspective, is highly applicable for such tasks as threshold decryption, and that it further makes HIBE a much more attractive alternative in various real life scenarios. On a philosophical level, while previous techniques protected against gradual key exposure in a generic way, oblivious to the application, we show that in certain situations one might achieve much better parameters by concentrating on the application at hand.

Original languageEnglish (US)
Title of host publicationProceedings - 1st International IEEE Security in Storage Workshop, SISW 2002
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)0769518885, 9780769518886
StatePublished - 2003
Event1st International IEEE Security in Storage Workshop, SISW 2002 - Greenbelt, United States
Duration: Dec 11 2002 → …

Publication series

NameProceedings - 1st International IEEE Security in Storage Workshop, SISW 2002


Other1st International IEEE Security in Storage Workshop, SISW 2002
Country/TerritoryUnited States
Period12/11/02 → …


  • bilinear Diffie-Hellman
  • cryptographic key storage
  • exposure resilience
  • gradual key exposure
  • hierarchical id-based encryption
  • key redundancy
  • key storage protection

ASJC Scopus subject areas

  • Computer Networks and Communications


Dive into the research topics of 'Exposure-resilience for free: The hierarchical ID-based encryption case'. Together they form a unique fingerprint.

Cite this