Tight Security Bound of  \(\textsf {2k{\text {-}}LightMAC\_Plus}\)

In ASIACRYPT’17, Naito proposed a beyond-birthday-bound variant of the LightMAC construction, called \(\textsf {LightMAC\_Plus}\) , which is built on three independently keyed n-bit block ciphers, and showed that the construction achieves 2n/3-bits PRF security. Later, Kim et al. claimed (without giving any formal proof) its security bound to \(2^{3n/4}\) . In FSE’18, Datta et al. have proposed a two-keyed variant of the \(\textsf {LightMAC\_Plus}\) construction, called \(\textsf {2k{\text {-}}LightMAC\_Plus}\) , which is built on two independently keyed n-bit block ciphers, and showed that the construction achieves 2n/3-bits PRF security. In this paper, we show a tight security bound on the \(\textsf {2k{\text {-}}LightMAC\_Plus}\) construction. In particular, we show that it provably achieves security up to \(2^{3n/4}\) queries. We also exhibit a matching attack on the construction with the same query complexity and hence establishing the tightness of the security bound. To the best of our knowledge, this is the first work that provably shows a message length independent 3n/4-bit tight security bound on a block cipher based variable input length PRF with two block cipher keys.