CryptoDB
Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys
| Authors: |
|
|---|---|
| Download: | |
| 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 ≤ 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. |
Video from TOSC 2020
BibTeX
@article{tosc-2020-30538,
title={Beyond-Birthday-Bound Secure Cryptographic Permutations from Ideal Ciphers with Long Keys},
journal={IACR Transactions on Symmetric Cryptology},
publisher={Ruhr-Universität Bochum},
volume={2020, Issue 2},
pages={68-92},
url={https://tosc.iacr.org/index.php/ToSC/article/view/8669},
doi={10.13154/tosc.v2020.i2.68-92},
author={Ryota Nakamichi and Tetsu Iwata},
year=2020
}