Paper 2020/073

Anonymous Symmetric-Key Communication

Fabio Banfi and Ueli Maurer


We study anonymity of probabilistic encryption (pE) and probabilistic authenticated encryption (pAE). We start by providing concise game-based security definitions capturing anonymity for both pE and pAE, and then show that the commonly used notion of indistinguishability from random ciphertexts (IND\($\)) indeed implies the anonymity notions for both pE and pAE. This is in contrast to a recent work of Chan and Rogaway (Asiacrypt 2019), where it is shown that IND\($\)-secure nonce-based authenticated encryption can only achieve anonymity if a sophisticated transformation is applied. Moreover, we also show that the Encrypt-then-MAC paradigm is anonymity-preserving, in the sense that if both the underlying probabilistic MAC (pMAC) and pE schemes are anonymous, then also the resulting pAE scheme is. Finally, we provide a composable treatment of anonymity using the constructive cryptography framework of Maurer and Renner (ICS 2011). We introduce adequate abstractions modeling various kinds of anonymous communication channels for many senders and one receiver in the presence of an active man-in-the-middle adversary. Then we show that the game-based notions indeed are anonymity-preserving, in the sense that they imply constructions between such anonymous channels, thus generating authenticity and/or confidentiality as expected, but crucially retaining anonymity if present.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.SCN 2020
anonymous encryptionanonymous authenticated encryptioncomposable securitycomposable anonymityanonymous channel
Contact author(s)
fabio banfi @ inf ethz ch
2020-08-10: last of 2 revisions
2020-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabio Banfi and Ueli Maurer},
      title = {Anonymous Symmetric-Key Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2020/073},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.