Leakage-Resilient Public-Key Encryption from Obfuscation

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In this work, we consider the bounded leakage and the continual leakage models. In the bounded leakage model (Akavia et al. – TCC 2009), it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model (Brakerski et al. – FOCS 2010, Dodis et al. – FOCS 2010), the lifetime of a cryptographic scheme is divided into “time periods” between which the scheme’s secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period.

In the continual leakage model, a challenging problem has been to provide security against leakage on key updates, that is, leakage that is a function not only of the current secret key but also the randomness used to update it. We propose a new, modular approach to overcome this problem. Namely, we present a compiler that transforms any public-key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation (Barak et al. – CRYPTO 2001, Garg et al. – FOCS 2013). Under the stronger assumption of public-coin differing-inputs obfuscation (Ishai et al. – TCC 2015) the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is obtained by making a new connection between the problems of leakage on key updates and so-called “sender-deniable” encryption (Canetti et al. – CRYPTO 1997). In particular, our compiler adapts and optimizes recent techniques of Sahai and Waters (STOC 2014) that make any encryption scheme sender-deniable. We then show that prior continual leakage resilient schemes can be upgraded to security against consecutive continual leakage without introducing new assumptions.

In the bounded leakage model, we develop an entirely new approach to constructing leakage-resilient encryption from obfuscation directly, based upon the public-key encryption scheme from \({\mathsf {iO}} \) and punctured pseudorandom functions due to Sahai and Waters (STOC 2014). In particular, we achieve (1) leakage-resilient public key encryption tolerating L bits of leakage for any L from \({\mathsf {iO}} \) and one-way functions, (2) leakage-resilient public key encryption with optimal leakage rate of \(1-o(1)\) based on public-coin differing-inputs obfuscation and collision-resistant hash functions.