Leakage-Resilient Public-Key Encryption from Obfuscation

Dana Dachman-Soled, S. Dov Gordon, Feng-Hao Liu, Adam O'Neill, Hong-Sheng Zhou

TL;DR

This paper introduces new techniques to build more robust public-key encryption schemes that can withstand "leakage attacks" where an adversary can observe partial information about the secret key. They achieve this by connecting the problem of leakage resilience to program obfuscation, a powerful cryptographic tool, and develop a compiler that transforms existing schemes into more secure ones, even when secret keys are updated.

What Problem Does This Paper Address?

In modern computing, attackers can exploit side-channel attacks to glean information about secret keys by observing physical phenomena like execution time or power consumption. Cryptographers have developed "leakage-resilient" schemes to protect against these attacks. However, existing models and constructions have limitations, particularly when secret keys are updated over time (continual leakage) or when leakage occurs during the update process itself. This paper tackles the challenging problem of building public-key encryption schemes that are secure even with these more sophisticated leakage models, especially concerning key updates.

Methods

The paper presents two main contributions:

  1. A Compiler for Leakage on Key Updates: They introduce a novel compiler that takes a public-key encryption scheme that is "consecutive continual leakage resilient" (2CLR) and transforms it into one that is continually leakage resilient with leakage on key updates. This compiler leverages a connection between leakage on key updates and "sender-deniable" encryption, and crucially uses program obfuscation (specifically, indistinguishability obfuscation or public-coin differing-inputs obfuscation). The compiler essentially "hides" the secret key update process in a way that is only understandable by an obfuscated program.
  2. Constructions from Obfuscation: They build leakage-resilient public-key encryption schemes directly from obfuscation. This includes schemes that are leakage-resilient in the bounded leakage model and schemes that are continually leakage resilient. They extend existing techniques that use obfuscation and "puncturable pseudorandom functions" to achieve leakage resilience. They also develop new techniques for constructing continually leakage-resilient schemes, which they believe are of independent interest.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Connecting Leakage and Obfuscation: A key insight is the surprising connection between leakage resilience and program obfuscation. Obfuscation, which aims to hide the functionality of a program, can be used to hide sensitive operations like secret key updates, making them resilient to leakage attacks.
  • Sender-Deniability as a Tool: The paper cleverly uses the concept of sender-deniability (where a sender can make a message appear as if it were encrypted differently) to handle leakage during key updates. This allows for a "simulated" explanation of how a new key was derived from an old one, even under leakage.
  • Modular Approach: The compiler approach provides a modular way to upgrade existing leakage-resilient schemes to handle more complex leakage scenarios, making the construction of secure systems more manageable.
  • New Leakage Model (2CLR): The introduction of "consecutive continual leakage resilience" (2CLR) provides a slightly stronger security notion that is crucial for their compiler to work effectively.

Key Results

  • They present a compiler that transforms 2CLR-secure schemes into CLR schemes with leakage on key updates, achieving leakage rates of $1/4 - o(1)$ under certain assumptions. This is a significant improvement over prior work.
  • They construct leakage-resilient public-key encryption schemes in the bounded leakage model with optimal leakage rates ($1 - o(1)$) based on public-coin differing-inputs obfuscation and collision-resistant hash functions.
  • They develop new techniques for constructing continually leakage-resilient schemes, which they believe are of independent interest.
  • Their results extend to digital signatures as well, showing the generality of their approach.

Limitations and Future Work

  • The paper notes that achieving the absolute optimal leakage rate of $1/2 - o(1)$ for CLR with leakage on key updates remains an open question.
  • Extending their constructions to achieve continual leakage resilience without additional assumptions (beyond those used for bounded leakage) is mentioned as an interesting open problem.
  • The constructions often rely on advanced cryptographic primitives like indistinguishability obfuscation and differing-inputs obfuscation, which have their own complexities and assumptions.

Summary updated

Abstract

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In this work, we consider the \emph{bounded leakage} and the \emph{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 \emph{leakage on key updates}, that is, leakage that is a function not only of the current secret key but also the \emph{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 \emph{consecutive} continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming \emph{indistinguishability obfuscation} (Barak et al. --- CRYPTO 2001, Garg et al. -- FOCS 2013). Under the stronger assumption of \emph{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), which was recently realized for the first time by Sahai and Waters (STOC 2014). In the bounded leakage model, we develop a new approach to constructing leakage-resilient encryption from obfuscation, based upon the public-key encryption scheme from $\iO$ and punctured pseudorandom functions due to Sahai and Waters (STOC 2014). In particular, we achieve leakage-resilient public key encryption tolerating $L$ bits of leakage for any $L$ from $\iO$ and one-way functions. We build on this to achieve 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. Such a leakage rate is not known to be achievable in a generic way based on public-key encryption alone. We then develop entirely new techniques to construct a new public key encryption scheme that is secure under (consecutive) continual leakage resilience (under appropriate assumptions), which we believe is of independent interest.
BibTeX
@article{dachmansoled2016leakage,
  author = {Dana Dachman-Soled and S. Dov Gordon and Feng-Hao Liu and Adam O'Neill and Hong-Sheng Zhou},
  title = {{Leakage-Resilient Public-Key Encryption from Obfuscation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}
Figure