Full-State Keyed Duplex with Built-In Multi-user Support

The keyed duplex construction was introduced by Bertoni et al. (SAC 2011) and recently generalized to full-state absorption by Mennink et al. (ASIACRYPT 2015). We present a generalization of the full-state keyed duplex that natively supports multiple instances by design, and perform a security analysis that improves over that of Mennink et al. in terms of a more modular security analysis and a stronger and more adaptive security bound. Via the introduction of an additional parameter to the analysis, our bound demonstrates a significant security improvement in case of nonce-respecting adversaries. Furthermore, by supporting multiple instances by design, instead of adapting the security model to it, we manage to derive a security bound that is largely independent of the number of instances.