@article{Nakamichi_Iwata_2020, title={Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys}, volume={2020}, url={https://tosc.iacr.org/index.php/ToSC/article/view/8669}, DOI={10.13154/tosc.v2020.i2.68-92}, abstractNote={<p>Coron et al. showed a construction of a 3-round 2<em>n</em>-bit cryptographic permutation from three independent <em>n</em>-bit ideal ciphers with <em>n</em>-bit keys (TCC 2010). Guo and Lin showed a construction of a (2<em>d</em> − 1)-round <em>dn</em>-bit cryptographic permutation from 2<em>d</em> − 1 independent <em>n</em>-bit ideal ciphers with <em>kn</em>-bit keys, where <em>d</em> = <em>k</em> + 1 (Cryptography and Communications, 2015). These constructions have an indifferentiability security bound of <em>O</em>(<em>q</em><sup>2</sup>/2<em><sup>n</sup></em>) against adversaries that make at most <em>q</em> queries. The bound is commonly referred to as birthday-bound security. <br>In this paper, we show that a 5-round version of Coron et al.’s construction and (2<em>d</em>+1)-round version of Guo and Lin’s construction yield a cryptographic permutation with an indifferentiability security bound of <em>O</em>(<em>q</em><sup>2</sup>/2<sup>2<em>n</em></sup>), i.e., by adding two more rounds, these constructions have beyond-birthday-bound security. Furthermore, under the assumption that <em>q</em> ≤ 2<em><sup>n</sup></em>, we show that Guo and Lin’s construction with 2<em>d</em>+2<em>l</em>−1 rounds yields a cryptographic permutation with a security bound of <em>O</em>(<em>q</em><sup>2</sup>/2<sup>(<em>l</em>+1)<em>n</em></sup>), where 1 ≤ <em>l</em> ≤ <em>d</em> − 1, i.e., the security bound exponentially improves by adding every two more rounds, up to 4<em>d</em> − 3 rounds. To the best of our knowledge, our result gives the <em>first</em> cryptographic permutation that is built from <em>n</em>-bit ideal ciphers and has a full <em>n</em>-bit indifferentiability security bound.</p>}, number={2}, journal={IACR Transactions on Symmetric Cryptology}, author={Nakamichi, Ryota and Iwata, Tetsu}, year={2020}, month={Jul.}, pages={68-92} }