How to Incorporate Associated Data in Sponge-Based Authenticated Encryption

We explore ways to combine associated data

$$A$$

with a sponge-based authenticated encryption (AE) scheme. In addition to the popular “header” and “trailer” methods, this paper investigates two other methods,

concurrent absorption

and

ciphertext translation

. The concurrent absorption is a novel method unique to the sponge construction. The advantage of the concurrent absorption is its efficiency; the number of permutation calls reduces to

$$\max \bigl \{|A|/c,\,|M|/r\bigr \}$$

where

$$|\cdot |$$

denotes the bit length,

$$c$$

the capacity size in bits, and

$$r$$

the rate size. In particular, if the size of

$$A$$

is relatively small, i.e.

$$|A|/c\le |M|/r$$

, then there is no need of extra permutation calls for processing

$$A$$

. On the other hand, the ciphertext translation is a generic technique developed by Rogaway (ACM CCS 2002), and in this paper it is concretized as a sponge-based AE scheme. The advantage of the sponge-based ciphertext translation is that it can start encrypting a message

$$M$$

irrespective of the relative arrival time of

$$A$$

.The efficiency of header and trailer methods can also be improved by using a similar technique. Remarkably, all of these methods are highly secure; the key length being denoted by

$$\kappa $$

, all methods achieve

$$\min \bigl \{2^{(r+c)/2},\,2^c/r,\,2^\kappa \bigr \}$$

security against nonce-respecting adversaries in the ideal model, as recently shown by Jovanovic et al. (Asiacrypt 2014) for the conventional header and trailer methods.