Boosting OMD for Almost Free Authentication of Associated Data

We propose 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 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{$\ell, a$}+$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.

Published in:
Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, 411-427
Presented at:
Fast Software Encryption - FSE 2015, Istanbul, TURKEY, March 8-11, 2015
Berlin, Springer
978-3-662-48116-5; 978-3-662-48115-8

 Record created 2014-12-09, last modified 2018-01-28

External link:
Download fulltext
Rate this document:

Rate this document:
(Not yet reviewed)