Paper 2017/533

Quantum non-malleability and authentication

Gorjan Alagic and Christian Majenz


In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. Ambainis et al. gave a definition of non-malleability for the encryption of quantum data. In this work, we show that this definition is too weak, as it allows adversaries to ``inject'' plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of Ambainis et al.). Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that ``total authentication'' (a notion recently proposed by Garg et al.) can be satisfied with two-designs, a significant improvement over their eight-design-based construction. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis et al.

Available format(s)
Publication info
Published by the IACR in CRYPTO 2017
quantum cryptographynon-malleabilityauthenticationinformation-theoretic security
Contact author(s)
majenz @ caltech edu
galagic @ gmail com
2017-06-07: received
Short URL
Creative Commons Attribution


      author = {Gorjan Alagic and Christian Majenz},
      title = {Quantum non-malleability and authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2017/533},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.