International Association
for Cryptologic Research

Authenticity can be compromised by information leaked via side-channels (e.g., power consumption). Examples of attacks include direct key recoveries and attacks against the tag verification which may lead to forgeries. At FSE 2018, Berti et al. described two authenticated encryption schemes which provide authenticity assuming a “leak-free implementation” of a Tweakable Block Cipher (TBC). Precisely, security is guaranteed even if all the intermediate computations of the target implementation are leaked in full but the TBC long-term key. Yet, while a leak-free implementation reasonably models strongly protected implementations of a TBC, it remains an idealized physical assumption that may be too demanding in many cases, in particular, if hardware engineers mitigate the leakage to a good extent but (due to performance constraints) do not reach leak-freeness. In this paper, we get rid of this important limitation by introducing the notion of “Strong Unpredictability with Leakage” for BC's and TBC's. It captures the hardness for an adversary to provide a fresh and valid input/output pair for a (T)BC, even having oracle access to the (T)BC, its inverse and their leakages. This definition is game-based and may be verified/falsified by laboratories. Based on it, we then provide two Message Authentication Codes (MAC) which are secure if the (T)BC on which they rely are implemented in a way that maintains a sufficient unpredictability. Thus, we improve the theoretical foundations of leakage-resilient MAC and extend them towards engineering constraints that are easier to achieve in practice.