KIVR: Committing Authenticated Encryption Using Redundancy and Application to GCM, CCM, and More

Constructing a committing authenticated encryption (AE) satisfying the CMT-4 security notion is an ongoing research challenge. We propose a new mode KIVR, a black-box conversion for adding the CMT-4 security to existing AEs. \(\textsf {KIVR}\) is a generalization of the Hash-then-Enc (HtE) [Bellare and Hoang, EUROCRYPT 2022] and uses a collision-resistant hash function to generate an initial value (or nonce) and a mask for redundant bits, in addition to a temporary key. We obtain a general bound \(r/2 + \textsf{tag}\text {-}\textsf{col}\) with r-bit redundancy for a large class of CTR-based AEs, where \(\textsf{tag}\text {-}\textsf{col}\) is the security against tag-collision attacks. Unlike HtE, the security of KIVR linearly increases with r, achieving beyond-birthday-bound security. With a t-bit tag, \(\textsf{tag}\text {-}\textsf{col}\) lies \(0 \le \textsf{tag}\text {-}\textsf{col}\le t/2\) depending on the target AE. We set \(\textsf{tag}\text {-}\textsf{col}=0\) for GCM, GCM-SIV, and CCM, and the corresponding bound r/2 is tight for GCM and GCM-SIV. With \(\textsf{CTR}\text{- }\textsf{HMAC}\) , \(\textsf{tag}\text {-}\textsf{col}= t/2\) , and the bound \((r+t)/2\) is tight.