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:
- 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.
- 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