Paper 2015/302

Boosting OMD for Almost Free Authentication of Associated Data

Reza Reyhanitabar, Serge Vaudenay, and Damian Vizár


We propose \emph{pure} OMD (p-OMD) as a new variant of the Offset Merkle-Damgård (OMD) authenticated encryption scheme. Our new scheme inherits all desirable security features of OMD while having a more compact structure and providing higher efficiency. The original OMD scheme, as submitted to the CAESAR competition, couples a single pass of a variant of the Merkle-Damgård (MD) iteration with the counter-based XOR MAC algorithm to provide privacy and authenticity. Our improved p-OMD scheme dispenses with the XOR MAC algorithm and is \emph{purely} based on the MD iteration; hence, the name ``pure'' OMD. To process a message of $\ell$ blocks and associated data of $a$ blocks, OMD needs $\ell+a+2$ calls to the compression function while p-OMD only requires $\max\left\{\ell, a\right\}+2$ calls. Therefore, for a typical case where $\ell \geq a$, p-OMD makes just $\ell+2$ calls to the compression function; that is, associated data is processed almost freely compared to OMD. We prove the security of p-OMD under the same standard assumption (pseudo-randomness of the compression function) as made in OMD; moreover, the security bound for p-OMD is the same as that of OMD, showing that the modifications made to boost the performance are without any loss of security.

Note: This is the revised version taking into account the nonce-misusing attack by Ashur and Mennink in Cryptology ePrint Archive: Report 2015/175.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2015
authenticated-encryptionOMDassociated dataperformanceCAESAR competition
Contact author(s)
reza reyhanitabar @ epfl ch
2015-04-06: received
Short URL
Creative Commons Attribution


      author = {Reza Reyhanitabar and Serge Vaudenay and Damian Vizár},
      title = {Boosting OMD for Almost Free Authentication of Associated Data},
      howpublished = {Cryptology ePrint Archive, Paper 2015/302},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.