International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Double-Block-Length Hash Function for Minimum Memory Size

Yusuke Naito , Mitsubishi Electric Corporation
Yu Sasaki , NTT Social Informatics Laboratories
Takeshi Sugawara , The University of Electro-Communications
DOI: 10.1007/978-3-030-92078-4_13
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: Sharing a common primitive for multiple functionalities is essential for lightweight cryptography, and NIST's lightweight cryptography competition (LWC) considers the integration of hashing to AEAD. While permutations are natural primitive choices in such a goal, for design diversity, it is interesting to investigate how small block-cipher (BC) based and tweakable block-cipher (TBC) based schemes can be. Double-block-length (DBL) hash function modes are suitable to ensure the same security level for AEAD and hashing, but hard to achieve a small memory size. Romulus, a TBC-based finalist in NIST LWC, introduced the DBL hashing scheme Romulus-H, but it requires $3n+k$ bits of memory using an underlying primitive with an $n$-bit block and a $k$-bit (twea)key. Even the smallest DBL modes in the literature require $2n+k$ bits of memory. Addressing this issue, we present new DBL modes EXEX-NI and EXEX-I achieving $(n+k)$-bit state size, i.e., no extra memory in addition to $n+k$ bits needed within the primitive. EXEX-NI is indifferentiable from a random oracle up to $n - \log n$ bits. By instantiating it with SKINNY, we can provide hashing to Romulus with zero memory overhead. EXEX-I is an optimized mode with collision resistance. We finally compare the hardware performances of EXEX-NI and EXEX-I, and Romulus-H with SKINNY-128-384. EXEX-NI and EXEX-I achieve the circuit-area reduction by 2,000+ GE, yielding the total areas being smaller than 70% of that of Romulus-H.
Video from ASIACRYPT 2021
  title={Double-Block-Length Hash Function for Minimum Memory Size},
  author={Yusuke Naito and Yu Sasaki and Takeshi Sugawara},