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 Gazi and Maurer [9] proved its security up to 2~(κ+min{n/2,κ}) 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~(κ+min{κ,n}-16/l(n/2+2)) query complexity: this bound approaches 2~(κ+min{κ,n}) 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 Gazi 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). In the ideal cipher model, one can obtain all the evaluations of the underlying blockcipher by making 2~(κ+n) queries, so the (κ+n)-bit security becomes the maximum that key-length extension based on a single κ-bit key n-bit blockcipher is able to achieve. Cascade encryptions CE~l (with n ≤ κ) and XCE~l provide almost optimal security with large cascade length.
展开▼
