Paper 2024/725

Multi User Security of LightMAC and LightMAC_Plus

Abstract

In FSE'16, Luykx et al. have proposed $\mathsf{\text{LightMAC}}$ that provably achieves a query length independent PRF security bound. To be precise, the construction achieves security roughly in the order of $O(q^2/2^n)$, when instantiated with two independently keyed $n$-bit block ciphers and $q$ is the total number of queries made by the adversary. Subsequently, in ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the $$ construction, dubbed as $$, that is built on three independently keyed $$-bit block ciphers and achieves $$-bits PRF security. Security analyses of these two constructions have been conducted in the single-user setting, where we assume that the adversary has the access to a single instance of the construction. In this paper, we investigate, for the first time, the security of the $$ and the $$ construction in the context of multi-user setting, where we assume that the adversary has access to more than one instances of the construction. In particular, we have shown that $$ remains secure roughly up to $$ construction queries and $$ ideal-cipher queries in the ideal-cipher model and $$ maintains security up to approximately $$ construction queries and $$ ideal-cipher queries in the ideal-cipher model, where $$ denotes the block size and $$ denotes the key size of the block cipher.