Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Leakage-resilient cryptography, Public-key encryption

Publication Info: Extended abstract in TCC 2011, this is the full version

Date: received 5 Jan 2011, last revised 5 Jan 2011

Contact author: shaih at alum mit edu, huijia@cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20110106:065357 (All versions of this report)

Short URL: ia.cr/2011/011

Discussion forum: Show discussion | Start new discussion