Paper 2010/562

How to Leak on Key Updates

Allison Lewko, Mark Lewko, and Brent Waters


In the continual memory leakage model, security against attackers who can repeatedly obtain leakage is achieved by periodically updating the secret key. This is an appealing model which captures a wide class of side-channel attacks, but all previous constructions in this model provide only a very minimal amount of leakage tolerance \emph{during secret key updates}. Since key updates may happen frequently, improving security guarantees against attackers who obtain leakage during these updates is an important problem. In this work, we present the first cryptographic primitives which are secure against a super-logarithmic amount of leakage during secret key updates. We present signature and public key encryption schemes in the standard model which can tolerate a constant fraction of the secret key to be leaked between updates as well as \emph{a constant fraction of the secret key and update randomness} to be leaked during updates. Our signature scheme also allows us to leak a constant fraction of the entire secret state during signing. Before this work, it was unknown how to tolerate super-logarithmic leakage during updates even in the random oracle model. We rely on subgroup decision assumptions in composite order bilinear groups.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
alewko @ cs utexas edu
2010-11-05: received
Short URL
Creative Commons Attribution


      author = {Allison Lewko and Mark Lewko and Brent Waters},
      title = {How to Leak on Key Updates},
      howpublished = {Cryptology ePrint Archive, Paper 2010/562},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.