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

This paper discusses provable security of two types of cascade encryptions. The rst construction CE l , calledl-cascade encryption, is obtained by sequentially composingl blockcipher calls with independent keys. The security of CE l has been a longstanding open problem until Ga zi and Maurer (9) proved its security up to 2 +minf n ; g query complexity for large cascading length, where 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 +minf;n g 16 l ( n 2 +2) query complexity: this bound approaches 2 +minf;n g 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 zi and Tessaro (10). We prove that XCE l is secure up to 2 +n 8 l ( n 2 +2) query complexity. As cascade length l increases, this bound approaches 2 +n .