Multi-User Security of CCM Authenticated Encryption Mode

The CCM authenticated encryption mode has gained widespread usage and standardization. Notably, in conjunction with GCM and ChaCha20-Poly1305, CCM is recommended to be used in TLS 1.3 that underlies in https. Since TLS 1.3 is currently utilized by a large number of users, it is imperative to assess the security of these schemes in the multi-user model. Concrete multi-user security analysis for GCM and ChaCha20-Poly1305 have been scrutinized in literature. However, the formal multi-user security analysis for CCM falls behind that for GCM and ChaCha20-Poly1305. Furthermore, in the associated IETF document, the multi-user security bound for CCM is derived by naive generic reduction and falls considerably short of our expectations. In this paper, we bridge the gap by establishing a concrete multi-user security bound for CCM. Our new bound surpasses that derived from generic reduction and it indicates that CCM maintains birthday-bound security in the multi-user model as in the single-user model.