Paper 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 ${\text{CE}}^l$, called $l$-cascade encryption, is obtained by sequentially composing $l$ blockcipher calls with independent keys. The security of ${\text{CE}}^l$ has been a longstanding open problem until Gaži and Maurer~\cite{GM09} proved its security up to $2^{\text{ka}+min\{\frac{n}{2},\text{ka}\}}$ query complexity for large cascading length, where $\text{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 ${\text{CE}}^l$ up to $2^{\text{ka}+min\{\text{ka},n\}-\frac{16}{l}(\frac{n}{2}+2)}$ query complexity: this bound approaches $2^{\text{ka}+min\{\text{ka},n\}}$ with increasing cascade length $l$. The second construction $$ 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 $$ is secure up to $$ query complexity. As cascade length $$ increases, this bound approaches $$. In the ideal cipher model, one can obtain all the evaluations of the underlying blockcipher by making $$ queries, so the $$-bit security becomes the maximum that key-length extension based on a single $$-bit key $$-bit blockcipher is able to achieve. Cascade encryptions $$~(with $$) and $$ provide almost optimal security with large cascade length.