Cryptology ePrint Archive: Report 2017/145

The Multi-User Security of Double Encryption

Viet Tung Hoang and Stefano Tessaro

Abstract: It is widely known that double encryption does not substantially increase the security of a block cipher. Indeed, the classical meet-in-the middle attack recovers the $2k$-bit secret key at the cost of roughly $2^k$ off-line enciphering operations, in addition to very few known plaintext-ciphertext pairs. Thus, essentially as efficiently as for the underlying cipher with a $k$-bit key.

This paper revisits double encryption under the lens of multi-user security. We prove that its security degrades only very mildly with an increasing number of users, as opposed to single encryption, where security drops linearly. More concretely, we give a tight bound for the multi-user security of double encryption as a pseudorandom permutation in the ideal-cipher model, and describe matching attacks.

Our contribution is also conceptual: To prove our result, we enhance and generalize the generic technique recently proposed by Hoang and Tessaro for lifting single-user to multi-user security. We believe this technique to be broadly applicable.

Category / Keywords: secret-key cryptography / symmetric security, provable security, multi-user security, double encryption

Original Publication (with minor differences): IACR-EUROCRYPT-2017

Date: received 15 Feb 2017, last revised 29 Nov 2018

Contact author: hviettung at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181129:153231 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]