The Exact Multi-user Security of (Tweakable) Key Alternating Ciphers with a Single Permutation

We prove the tight multi-user (mu) security of the (tweakable) key alternating cipher (KAC) for any round r with a single permutation and r-wise independent subkeys, providing a more realistic provable-security foundation for block ciphers. After Chen and Steinberger proved the single-user (su) tight security bound of r-round KAC in 2014, its extension under more realistic conditions has become a new research challenge. The state-of-the-art includes (i) single permutation by Yu et al., (ii) the mu security by Hoang and Tessaro, and (iii) correlated subkeys by Tessaro and Zhang. However, the previous works considered these conditions independently, and the tight security bound of r-round KACs with all of these conditions is an open research problem. We address it by giving the new mu-bound with an n-bit message space, approximately q. (p+rq/2(n))(r) wherein p and q are the number of primitive and construction queries, respectively. The bound ensures the security up to the O(2rn/r+1) r+1) query complexity and is tight, matching the conventional attack bound. Moreover, our result easily extends to the r-round tweakable KAC when its subkeys generated by a tweak function is r-wise independent. The proof is based on the re-sampling method originally proposed for the mu-security analysis of the triple encryption. Its extension to any rounds is the core technique enabling the new bound.