TY - JOUR
AU - Nakamichi, Ryota
AU - Iwata, Tetsu
PY - 2020/07/24
Y2 - 2021/01/17
TI - Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2020
IS - 2
SE - Articles
DO - 10.13154/tosc.v2020.i2.68-92
UR - https://tosc.iacr.org/index.php/ToSC/article/view/8669
SP - 68-92
AB - Coron et al. showed a construction of a 3-round 2n-bit cryptographic permutation from three independent n-bit ideal ciphers with n-bit keys (TCC 2010). Guo and Lin showed a construction of a (2d − 1)-round dn-bit cryptographic permutation from 2d − 1 independent n-bit ideal ciphers with kn-bit keys, where d = k + 1 (Cryptography and Communications, 2015). These constructions have an indifferentiability security bound of O(q2/2n) against adversaries that make at most q queries. The bound is commonly referred to as birthday-bound security. In this paper, we show that a 5-round version of Coron et al.’s construction and (2d+1)-round version of Guo and Lin’s construction yield a cryptographic permutation with an indifferentiability security bound of O(q2/22n), i.e., by adding two more rounds, these constructions have beyond-birthday-bound security. Furthermore, under the assumption that q ≤ 2n, we show that Guo and Lin’s construction with 2d+2l−1 rounds yields a cryptographic permutation with a security bound of O(q2/2(l+1)n), where 1 ≤ l ≤ d − 1, i.e., the security bound exponentially improves by adding every two more rounds, up to 4d − 3 rounds. To the best of our knowledge, our result gives the first cryptographic permutation that is built from n-bit ideal ciphers and has a full n-bit indifferentiability security bound.
ER -