Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


In recent years, there has been a major effort to design cryptographic schemes that remain secure even if part of the secret key is leaked. This is due to a recent proliferation of side channel attacks which, through various physical means, can recover part of the secret key. Micali and Reyzin (2004) suggested the intriguing possibility of achieving security even with continual leakage, i.e., even if some information is leaked each time the key is used. To achieve this impossible-sounding goal, theirs and several subsequent works all required the so-called ``only computation leaks information'' assumption, and it was unclear whether this strong assumption could be removed. We succeed in removing this assumption.

We show how to securely update a secret key while information is leaked, allowing some leakage {em even during the updates} themselves. Namely, we construct schemes that remain secure, even if an attacker {em at each time period}, can probe the {em entire} memory (containing a secret key) and ``leak out'' a $1/4-epsilon$ fraction of the secret key . The attacker may also probe the memory {em 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).

Specifically, under the decisional linear assumption on bilinear groups, 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 encryption schemes even under the (stronger) assumption of Micali and Reyzin. One of our technical tools is a new linear algebraic theorem (which is unconditional, and requires no computational assumptions), stating that ``random subspaces are leakage-resilient''.

The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (without the aforementioned strong assumption) and (2) giving a public key {em enc

Questions and Answers

You need to be logged in to be able to post here.