HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures

Jung Hee Cheon; Hyeongmin Choe; Julien Devevey; Tim Güneysu; Dongyeon Hong; Markus Krausz; Georg Land; Marc Möller; Damien Stehlé; MinJune Yi

Paper 2023/624

HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures

Jung Hee Cheon, Seoul National University, CryptoLab Inc.

Hyeongmin Choe, Seoul National University

Julien Devevey, École Normale Supérieure de Lyon

Tim Güneysu

, Ruhr University Bochum, German Research Centre for Artificial Intelligence

Dongyeon Hong, The Affiliated Institute of ETRI

Markus Krausz

, Ruhr University Bochum

Georg Land

, Ruhr University Bochum

Marc Möller, Ruhr University Bochum

Damien Stehlé, CryptoLab Inc.

MinJune Yi, Seoul National University

Abstract

We present HAETAE (Hyperball bimodAl modulE rejecTion signAture schemE), a new lattice-based signature scheme. Like the NIST-selected Dilithium signature scheme, HAETAE is based on the Fiat-Shamir with Aborts paradigm, but our design choices target an improved complexity/compactness compromise that is highly relevant for many space-limited application scenarios. We primarily focus on reducing signature and verification key sizes so that signatures fit into one TCP or UDP datagram while preserving a high level of security against a variety of attacks. As a result, our scheme has signature and verification key sizes up to 39% and 25% smaller, respectively, compared than Dilithium. We provide a portable, constant-time reference implementation together with an optimized implementation using AVX2 instructions and an implementation with reduced stack size for the Cortex-M4. Moreover, we describe how to efficiently protect HAETAE against implementation attacks such as side-channel analysis, making it an attractive candidate for use in IoT and other embedded systems.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. CHES 2024
Keywords: Signature Fiat-Shamir Lattice-based Cryptography Bimodal Distribution
Contact author(s): jhcheon @ snu ac kr
sixtail528 @ snu ac kr
julien devevey @ ens-lyon fr
tim gueneysu @ rub de
jjoker041 @ gmail com
markus krausz @ rub de
georg land @ rub de
marc moeller @ rub de
damien stehle @ cryptolab co kr
yiminjune @ snu ac kr
History: 2024-07-04: last of 3 revisions; 2023-05-02: received; See all versions
Short URL: https://ia.cr/2023/624
License: CC BY

BibTeX

@misc{cryptoeprint:2023/624,
      author = {Jung Hee Cheon and Hyeongmin Choe and Julien Devevey and Tim Güneysu and Dongyeon Hong and Markus Krausz and Georg Land and Marc Möller and Damien Stehlé and MinJune Yi},
      title = {{HAETAE}: Shorter Lattice-Based Fiat-Shamir Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/624},
      year = {2023},
      url = {https://eprint.iacr.org/2023/624}
}