Alexandre Adomnicăi
Independent Researcher, Paris, France

Wonseok Choi
Purdue University, West Lafayette, US; Georgia Institute of Technology, Atlanta, US

Yeongmin Lee
DESILO Inc., Seoul, Korea

Kazuhiko Minematsu
NEC, Kawasaki, Japan

Yusuke Naito
Mitsubishi Electric Corporation, Kanagawa, Japan

Keywords: Authenticated Encryption, Short input, Beyond birthday bound security

Abstract

Authenticated encryption (AE) is a fundamental tool in today’s secure communication. Numerous designs have been proposed, including well-known standards such as GCM. While their performance for long inputs is excellent, that for short inputs is often problematic due to high overhead in computation, showing a gap between the real need for IoT-like protocols where packets are often very short. Existing dedicated short-input AEs are very scarce, the classical Encode-then-encipher (Bellare and Rogaway, Asiacrypt 2000) and Manx (Adomnicăi et al., CT-RSA 2023), using up to two block cipher calls. They have superior performance for (very) short inputs, however, security is up to n/2 bits, where n is the block size of the underlying block cipher. This paper proposes a new family of short-input AEs, dubbed Cymric, which ensure beyond-birthday-bound (BBB) security. It supports a wider range of input space than EtE and Manx with the help of one additional block cipher call (thus three calls). In terms of the number of block cipher calls, Cymric is the known minimum construction of BBB-secure AEs, and we also prove this is indeed minimal by presenting an impossibility result on BBB-secure AE with two calls. Finally, we show a comprehensive benchmark on microcontrollers to show performance advantage over existing schemes.