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 $\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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2013
Keywords
Block ciphersPseudorandomness
Contact author(s)
hicalf @ gmail com
History
2015-03-10: last of 3 revisions
2015-03-06: received
See all versions
Short URL
https://ia.cr/2015/205
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/205,
      author = {Jooyoung Lee},
      title = {Towards Key-Length Extension with Optimal Security: Cascade Encryption and Xor-cascade Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/205},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/205}},
      url = {https://eprint.iacr.org/2015/205}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.