Cryptology ePrint Archive: Report 2021/1250

Efficient Leakage-Resilient MACs without Idealized Assumptions

Francesco Berti and Chun Guo and Thomas Peters and Fran├žois-Xavier Standaert

Abstract: The security proofs of leakage-resilient MACs based on symmetric building blocks currently rely on idealized assumptions that hardly translate into interpretable guidelines for the cryptographic engineers implementing these schemes. In this paper, we first present a leakage-resilient MAC that is both efficient and secure under standard and easily interpretable black box and physical assumptions. It only requires a collision resistant hash function and a single call per message authentication to a Tweakable Block Cipher ($\mathsf{TBC}$) that is unpredictable with leakage. This construction leverages two design twists: large tweaks for the $\mathsf{TBC}$ and a verification process that checks the inverse $\mathsf{TBC}$ against a constant. It enjoys beyond birthday security bounds. We then discuss the cost of getting rid of these design twists. We show that security can be proven without them as well. Yet, a construction without large tweaks requires stronger (non idealized) assumptions and may incur performance overheads if specialized $\mathsf{TBC}$s with large tweaks can be exploited, and a construction without twisted verification requires even stronger assumptions (still non idealized) and leads to more involved bounds. The combination of these results makes a case for our first pragmatic construction and suggests the design of $\mathsf{TBC}$s with large tweaks and good properties for side-channel countermeasures as an interesting challenge.

Category / Keywords: secret-key cryptography / MAC, leakage resilience/resistance, tweakable blockcipher, unpredictability

Original Publication (with minor differences): IACR-ASIACRYPT-2021

Date: received 20 Sep 2021, last revised 20 Sep 2021

Contact author: francesco berti at tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20210920:185337 (All versions of this report)

Short URL: ia.cr/2021/1250


[ Cryptology ePrint archive ]