Paper 2011/011

After-the-Fact Leakage in Public-Key Encryption

Shai Halevi and Huijia Lin

Abstract

What does it mean for an encryption scheme to be leakage-resilient Prior formulations require that the scheme remains semantically secure even in the presence of leakage, but only considered leakage that occurs \emph{before the challenge ciphertext is generated}. Although seemingly necessary, this restriction severely limits the usefulness of the resulting notion. In this work we study after-the-fact leakage, namely leakage that the adversary obtains after seeing the challenge ciphertext. We seek a ``natural'' and realizable notion of security, which is usable in higher-level protocols and applications. To this end, we formulate \emph{entropic leakage-resilient PKE}. This notion captures the intuition that as long as the entropy of the encrypted message is higher than the amount of leakage, the message still has some (pseudo) entropy left. We show that this notion is realized by the Naor-Segev constructions (using hash proof systems). We demonstrate that entropic leakage-resilience is useful by showing a simple construction that uses it to get semantic security in the presence of after-the-fact leakage, in a model of bounded memory leakage from a split state.