Identity-based encryption resilient to continual auxiliary leakage

We devise the first identity-based encryption (IBE) that remains secure even when the adversary is equipped with auxiliary input (STOC '09)-any computationally uninvertible function of the master secret key and the identity-based secret key. In particular, this is more general than the tolerance of Chow et al.'s IBE schemes (CCS '10) and Lewko et al.'s IBE schemes (TCC '11), in which the leakage is bounded by a pre-defined number of bits; yet our construction is also fully secure in the standard model based on only static assumptions, and can be easily extended to give the first hierarchical IBE with auxiliary input. Furthermore, we propose the model of continual auxiliary leakage (CAL) that can capture both memory leakage and continual leakage. The CAL model is particularly appealing since it not only gives a clean definition when there are multiple secret keys (the master secret key, the identity-based secret keys, and their refreshed versions), but also gives a generalized definition that does not assume secure erasure of secret keys after each key update. This is different from previous definitions of continual leakage (FOCS '10, TCC '11) in which the length-bounded leakage is only the secret key in the current time period. Finally, we devise an IBE scheme which is secure in this model. A major tool we use is the modified Goldreich-Levin theorem (TCC '10), which until now has only been applied in traditional public-key encryption with a single private key.