**Towards Key-Length Extension with Optimal Security: Cascade Encryption and Xor-cascade Encryption**

*Jooyoung Lee*

**Abstract: **This paper discusses provable security of two types of cascade encryptions. The first construction $\CE^l$, called $l$-cascade encryption, is obtained by sequentially composing $l$ blockcipher calls with independent keys. The security of $\CE^l$ has been a longstanding open problem until Gaži and Maurer~\cite{GM09} proved its security up to $2^{\ka+\min\{\frac{n}{2},\ka\}}$ query complexity for large cascading length, where $\ka$ and $n$ denote the key size and the block size of the underlying blockcipher, respectively. We improve this limit by proving the security of $\CE^l$ up to $2^{\ka+\min\left\{\ka,n\right\}-\frac{16}{l}\left(\frac{n}{2}+2\right)}$ query complexity: this bound approaches $2^{\ka+\min\left\{\ka,n\right\}}$ with increasing cascade length $l$.

The second construction $\XCE^l$ is a natural cascade version of the DESX scheme with intermediate keys xored between blockcipher calls. This can also be viewed as an extension of double XOR-cascade proposed by Gaži and Tessaro~\cite{GT12}. We prove that $\XCE^l$ is secure up to $2^{\ka+n-\frac{8}{l}\left(\frac{n}{2}+2\right)}$ query complexity. As cascade length $l$ increases, this bound approaches $2^{\ka+n}$.

In the ideal cipher model, one can obtain all the evaluations of the underlying blockcipher by making $2^{\ka+n}$ queries, so the $(\ka+n)$-bit security becomes the maximum that key-length extension based on a single $\ka$-bit key $n$-bit blockcipher is able to achieve. Cascade encryptions $\CE^l$~(with $n\leq\ka$) and $\XCE^l$ provide almost optimal security with large cascade length.

**Category / Keywords: **secret-key cryptography / Block ciphers, Pseudorandomness

**Original Publication**** (in the same form): **IACR-EUROCRYPT-2013

**Date: **received 5 Mar 2015, last revised 10 Mar 2015

**Contact author: **hicalf at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20150310:124142 (All versions of this report)

**Short URL: **ia.cr/2015/205

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]