How to leak on key updates

Leakage resilient cryptography is an exciting area of cryptography that aims to build cryptosystems that provide security against side channel attacks. In this post I will give a nontechnical description of a common leakage resilient security model, as well as describe a recent paper in the area with Allison Lewko and Brent Waters, titled “How to Leak on Key Updates”.

Review of Public Key Encryption

Let us (informally) recall the definition of a public key cryptography system. Alice would like to send Bob a private message over an unsecured channel. Alice and Bob have never met before and we assume they do not share any secret information. Ideally, we would like a procedure where 1) Alice and Bob engage in a series of communications resulting in Bob learning the message 2) an eavesdropper, Eve, who intercepts all of the communications sent between Alice and Bob, should not learn any (nontrivial) information about the message . As stated, the problem is information theoretically impossible. However, this problem is classically solved under the heading of public key cryptography if we further assume that:

1) Eve has limited computational resources,
2) certain computational problems (such as factoring large integers or computing discrete logarithms in a finite group) are not efficiently solvable, and
3) we allow Alice and Bob to use randomization (and permit security to fail with very small probability).

More specifically, a public key protocol works as follows: Bob generates a private and public key, say and respectively. As indicated by the names, is publicly known but Bob retains as secret information. When Alice wishes to send a message to Bob she generates an encrypted ciphertext using the message , Bob’s public key and some randomness. She then sends this ciphertext to Bob via the public channel. When Bob receives the ciphertext he decrypts it using his secret key and recovers . While Eve has access to the ciphertext and the secret key , she is unable to learn any nontrivial information about the message (assuming our assumptions are sound). In fact, we require a bit more: even if this is repeated many times (with fixed keys), Eve’s ability to decrypt the ciphertext does not meaningfully improve.

Leakage Resilient Cryptography and our work

In practice, however, Eve may be able to learn information in addition to what she intercepts over Alice and Bob’s public communications via side channel attacks. Such attacks might include measuring the amount of time or energy Bob uses to carry out computations. The field of leakage resilient cryptography aims to incorporate protection against such attacks into the the security model. In this model, in addition to the ciphertext and public key, we let Eve select a (efficiently computable) function where is the bit length of and is a constant. We now assume, in addition to and , Eve  also gets to see . In other words, Eve gains a fair amount of information about the secret key, but not enough to fully determine it.

Moreover, we allow Eve to specify a different function every time Alice sends Bob a message. There is an obvious problem now, however. If the secret key remained static, then Eve could start by choosing to output the first bits, the second time she could choose to give the next bits, and if she carries on like this, after messages she would have recovered the entire secret key. To compensate for this we allow Bob to update his secret key between messages. The public key will remain the same.

There has been a lot of interesting work on this problem. In the works of Brakerski, Kalai, Katz, and Vaikuntanathan and Dodis, Haralambiev, Lopez-Alt, and Wichs many schemes are presented that are provably secure against continual leakage. In these schemes, however, information about the secret key is permitted to be leaked between updates, but only a tiny amount is allowed to be leaked during the update process itself.

In our current work, we offer the first scheme that allows a constant fraction of the information used in the update to be leaked. The proof is based on subgroup decision assumptions in composite order bilinear groups.