CryptoDB
The Exact Multi-User Security of (Tweakable) Key Alternating Ciphers with a Single Permutation
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | We prove the tight multi-user (mu) security of the (tweakable) key alternating ciphers (KACs) 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) 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(2^(rn/(r+1))) query complexity and is tight, matching the conven- tional upper 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. |
BibTeX
@inproceedings{eurocrypt-2024-33998,
title={The Exact Multi-User Security of (Tweakable) Key Alternating Ciphers with a Single Permutation},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58716-0_4},
author={Yusuke Naito and Yu Sasaki and Takeshi Sugawara},
year=2024
}