Cryptology ePrint Archive: Report 2015/205

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