Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys

  • Ryota Nakamichi Nagoya University, Nagoya, Japan
  • Tetsu Iwata Nagoya University, Nagoya, Japan
Keywords: Cryptographic permutation, Ideal cipher, Provable security, Indifferentiability, Coefficient-H technique

Abstract

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 ≤ ld − 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.

Published
2020-07-24
How to Cite
Nakamichi, R., & Iwata, T. (2020). Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys. IACR Transactions on Symmetric Cryptology, 2020(2), 68-92. https://doi.org/10.13154/tosc.v2020.i2.68-92
Section
Articles