We show how to securely update a secret key while information is leaked: We construct schemes that remain secure even if an attacker, {\em at each time period}, can probe the entire memory (containing a secret key) and ``leak'' up to a $(1-o(1))$ fraction of the secret key. The attacker may also probe the memory during the updates, and leak $O(\log k)$ bits, where $k$ is the security parameter (relying on subexponential hardness allows $k^\epsilon$ bits of leakage during each update process). All of the above is achieved without restricting the model as is done in previous works (e.g. by assuming that ``only computation leaks information'' [Micali-Reyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of $(1/2-o(1))$) or the symmetric external Diffie-Hellman assumption (which allows for a leakage rate of $(1-o(1))$), we achieve the above for public key encryption, identity-based encryption, and signature schemes. Prior to this work, it was not known how to construct public-key encryption schemes even in the more restricted model of [MR].
The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (in the more general model) and (2) giving a public key encryption (and IBE) schemes that are resilient to continual leakage.
Category / Keywords: public-key cryptography / public key encryption, continual memory leakage Publication Info: FOCS 2010 Date: received 11 May 2010, last revised 16 Nov 2010 Contact author: zvika brakerski at weizmann ac il Available format(s): PDF | BibTeX Citation Note: Title change (previous: "Cryptography Resilient to Continual Memory Leakage"). Version: 20101116:195811 (All versions of this report) Short URL: ia.cr/2010/278 Discussion forum: Show discussion | Start new discussion