Paper 2013/292

A Leakage Resilient MAC

Dan Martin and Elisabeth Oswald and Martijn Stam

Abstract

We put forward the first practical message authentication code (MAC) which is provably secure against continuous leakage under the Only Computation Leaks Information (OCLI) assumption. We introduce a novel, modular proof technique: while most previous schemes are proven secure directly in the face of leakage, we reduce the (leakage) security of our scheme to its non-leakage security. This modularity, while known in other contexts, has two advantages: it makes it clearer which parts of the proof rely on which assumptions (i.e. whether a given assumption is needed for the leakage or the non-leakage security) and it also means that, if the security of the non-leakage version is improved, the security in the face of leakage is improved ‘for free’. We feel that this is an advantageous proof technique, providing a better understanding of the scheme’s security properties. In practice, we envisage that our scheme would be implemented using pairings on some pairing-friendly elliptic curve, where the ‘leakiness’ of the group operation can be experimentally estimated. This allows us to compare the resulting instantiation against other leakage resilient MACs (or related schemes), and conclude that ours is the most efficient, as well as being (by far) the most practical.