Paper 2011/011

After-the-Fact Leakage in Public-Key Encryption

Shai Halevi and Huijia Lin


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.

Available format(s)
Publication info
Published elsewhere. Extended abstract in TCC 2011, this is the full version
Leakage-resilient cryptographyPublic-key encryption
Contact author(s)
shaih @ alum mit edu
huijia @ cs cornell edu
2011-01-06: revised
2011-01-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Huijia Lin},
      title = {After-the-Fact Leakage in Public-Key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2011/011},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.