Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
symmetric securityprovable securitymulti-user securitydouble encryption
Contact author(s)
hviettung @ gmail com
History
2018-11-29: last of 2 revisions
2017-02-20: received
See all versions
Short URL
https://ia.cr/2017/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/145,
      author = {Viet Tung Hoang and Stefano Tessaro},
      title = {The Multi-User Security of Double Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/145},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/145}},
      url = {https://eprint.iacr.org/2017/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.