Paper 2013/767 Original: eprint.iacr.org/2013/767 ↗

Misuse Resistant Parallel Authenticated Encryptions

Abstract

The authenticated encryptions which resist misuse of initial value (or nonce) at some desired level of privacy are two-pass or Mac-then-Encrypt constructions (inherently inefficient but provide full privacy) and online constructions, e.g., McOE, sponge-type authenticated encryptions (such as duplex, AEGIS) and COPA. Only the last one is almost parallelizable with some bottleneck in processing associated data. In this paper, {\em we design a new online secure authenticated encryption, called \tx{ELmE} or Encrypt-Linear mix-Encrypt, which is completely (two-stage) {\bf parallel} (even in associated data) and {\bf pipeline implementable}}. It also provides full privacy when associated data (which includes initial value) is not repeated. The basic idea of our construction and COPA are based on \tx{EME}, an Encrypt-Mix-Encrypt type SPRP constructions (secure against chosen plaintext and ciphertext). Unlike \tx{EME}, we consider (so does COPA) online computable {\bf linear mixing}. In addition with getting rid of bottleneck, our construction optionally supports {\bf intermediate tags} which can be verified faster with less buffer size. Intermediate tag provides security against block-wise adversaries which is meaningful in low-end device implementation.