Paper 2024/725

Multi User Security of LightMAC and LightMAC_Plus

Abstract

LightMAC is one of the ISO/IEC standardized message authentication codes that provably achieves security roughly in the order of O(q^2/2^n), where q is the total number of queries and n is the block size of the underlying block cipher. In a subsequent work, Naito proposed a beyond-birthday-bound variant of the LightMAC construction, dubbed LightMAC_Plus, and demonstrated that it achieves 2n/3-bit PRF security. Later in EUROCRYPT'20, Kim et al. improved the security bound of LighMAC_Plus from 2n/3 bits to 3n/4 bits. However, all these security results have been proven in the single-user setting, where we assume that the adversary has access to a single instance of the construction. In this paper, we investigate, for the first time, the security of the LightMAC and the LightMAC_Plus constructions in the context of the multi-user setting, where we assume that the adversary has access to more than one instance of the construction. In particular, we have shown that LightMAC offers O(qq_{max}l k/2^n + up/2^k) multi-user PRF security, where q denotes the total number of construction queries, p denotes the total number of offline primitive queries, q_{max} denotes the maximum number of queries per user, $u$ denotes the total number of users and l denotes the maximum number of message blocks in a query. We have also shown that LightMAC_Plus maintains security up to approximately 2^{2n/3} construction queries and 2^{2k/3} ideal-cipher queries in the ideal-cipher model, where n denotes the block size and k denotes the key size of the block cipher. In this paper, we investigate, for the first time, the security of the LightMAC and the LightMAC_Plus constructions in the context of the multi-user setting, where we assume that the adversary has access to more than one instance of the construction. In particular, we show that LightMAC offers O(qq_{max}l k/2^n + up/2^k) multi-user PRF security, where q denotes the total number of construction queries, p denotes the total number of offline primitive queries, q_{max} denotes the maximum number of queries per user, $u$ denotes the total number of users, and l denotes the maximum number of message blocks in a query. We also show that LightMAC_Plus maintains security up to approximately 2^{2n/3} construction queries and 2^{2k/3} ideal-cipher queries in the ideal-cipher model, where n denotes the block size and k denotes the key size of the block cipher.

Note: Accepted for publication in IACR Communications in Cryptology, Vol. 2, Issue 3 (2025), under the title ``Multi-User Security of LightMAC and LightMAC_Plus''.