Improved XKX-Based AEAD Scheme: Removing the Birthday Terms

摘要

Naito [ToSC 2017, Issue 2] proposed XKX, a tweakable blockcipher (TBC) based on a blockcipher (BC). It offers efficient authenticated encryption with associated data (AEAD) schemes with beyondbirthday-bound (BBB) security, by combining with efficient TBC-based AEAD schemes such as ΘCB3. In the resultant schemes, for each data block, a BC is called once. The security bound is roughly l~2q/2~n + σ~2_A/2~n + σ~2_D/2~n, where n is the block size of the BC in bits, l is the number of BC calls by a query, q is the number of queries, σ_A is the number of BC calls handing associated data by encryption queries, and σ_D is the number of BC calls by decryption queries. Hence, assuming l,σ_A,σ_D {much less than} 2~(n/2), the AEAD schemes achieve BBB security. However, the birthday terms σ~2_A/2~n, σ~2_D/2~n might become dominant, for example, when n is small such as n = 64 and when DoS attacks are performed. The birthday terms are introduced due to the modular proof via the XKX's security proof. In this paper, in order to remove the birthday terms, we slightly modify ΘCB3 called ΘCB3, and directly prove the security of ΘCB3 with XKX. We show that the security bound becomes roughly l~2q/2~n.