@article{Cogliati_Ethan_Jha_Kanti Saha_2023, title={On Large Tweaks in Tweakable Even-Mansour with Linear Tweak and Key Mixing}, volume={2023}, url={https://tosc.iacr.org/index.php/ToSC/article/view/11292}, DOI={10.46586/tosc.v2023.i4.330-364}, abstractNote={<p>In this paper, we provide the first analysis of the Iterated Tweakable Even-Mansour cipher with linear tweak and key (or tweakey) mixing, henceforth referred as TEML, for an arbitrary tweak(ey) size <em>kn</em> for all <em>k</em> ≥ 1, and arbitrary number of rounds <em>r</em> ≥ 2. Note that TEML captures the high-level design paradigm of most of the existing tweakable block ciphers (TBCs), including SKINNY, Deoxys, TweGIFT, TweAES etc. from a provable security point of view. At ASIACRYPT 2015, Cogliati and Seurin initiated the study of TEML by showing that 4-round TEML with a <em>2n</em>-bit uniform at random key, and <em>n</em>-bit tweak is secure up to 2<sup><em>2n</em>/<em>3</em> </sup>queries. In this work, we extend this line of research in two directions. First, we propose a necessary and sufficient class of linear tweakey schedules to absorb <em>mn</em>-bit tweak(ey) material in a minimal number of rounds, for all <em>m</em> ≥ 1. Second, we give a rigorous provable security treatment for <em>r</em>-round TEML, for all <em>r</em> ≥ 2. In particular, we first show that the <em>2r</em>-round TEML with a (<em>2r</em> + 1)<em>n</em>-bit key, <em>αn</em>-bit tweak, and a special class of tweakey schedule is IND-CCA secure up to <em>O</em>(2<sup><em>r</em>−α/<em>r</em> <em>n</em></sup>) queries. Our proof crucially relies on the use of the <em>coupling</em> technique to upper-bound the statistical distance of the outputs of TEML cipher from the uniform distribution. Our main echnical contribution is a novel approach for computing the probability of failure in coupling, which could be of independent interest for deriving tighter bounds in coupling-based security proofs. Next, we shift our focus to the chosen-key setting, and show that (<em>r</em> + 3)-round TEML, with <em>rn</em> bits of tweakey material and a special class of tweakey schedule, offers some form of resistance to chosen-key attacks. We prove this by showing that <em>r</em> + 3 rounds of TEML are both necessary and sufficient for <em>sequential indifferentiability</em>. As a consequence of our results, we provide a sound provable security footing for the TWEAKEY framework, a high level design rationale of popular TBC.</p>}, number={4}, journal={IACR Transactions on Symmetric Cryptology}, author={Cogliati, Benoît and Ethan, Jordan and Jha, Ashwin and Kanti Saha, Soumya}, year={2023}, month={Dec.}, pages={330–364} }