Committing Wide Encryption Mode with Minimum Ciphertext Expansion

Abstract

We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. In response to the recent call for proposal by NIST, WE and its tweakable variant, TWE, are attracting much attention in the last few years. Combined with the encode-then-encipher (EtE) construction, TWE offers an RAE that provides robustness against wide range of misuses. The list of desired properties for WE-based authenticated encryption in the NIST standardization includes committing security that considers an attacker who generates ciphertexts that can be decrypted with different decryption contexts, but TWE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4 attack (Chen et al., ToSC 2023(4)). Improving CMT-4 security requires considerable ciphertext expansion, and the state-of-the-art scheme expands the ciphertext by s_rae + 2s_cmt bits from an original message to achieve s_rae-bit RAE and s_cmt-bit CMT-4 security. Our new WE mode, FFF, addresses the issue by achieving s_rae-bit RAE and s_cmt-bit CMT-4 security only with max{s_cmt, s_rae} bits of ciphertext expansion. Our design is based on the committing concealer proposed by Bellare et al., and its extension to WE (cf. tag-based AE) while satisfying RAE security is the main technical innovation.