The Multi-user Security of GCM-SST and Further Enhancements

GCM with Secure Short Tag (GCM-SST) is a variant of the GCM authenticated encryption mode designed for improved security with short tags, and its standardization is ongoing in various organizations, including 3GPP and IETF. The original design specification was published with informal security claims only, and Inoue et al. then verified them with formal security proofs. They proved that the term regarding tag length t is \(\frac{v}{2^t}\) in GCM-SST (cf. \(\frac{v \ell }{2^t}\) in GCM), wherein v is the number of decryption queries and the maximum message block length \(\ell \). However, the proofs were given in the single-user (su) setting only, and its multi-user (mu) security remained an open research problem, which is a significant gap because GCM-SST’s specification document explicitly considers mu use cases and even recommends nonce randomization (NR) for improving mu-security. Addressing this issue, this paper proves mu-security of GCM-SST, verifying that the security with short tags stays intact under the mu setting. Moreover, by combining GCM-SST with NR and nonce-based key derivation (NKD), we show that those enhancement methods improve mu-security in the same level as those combined with GCM.