HAETAE: Post-Quantum Digital Signature
HAETAE is a module lattice-based signature scheme for shorter and easily maskable signatures. While based on the Fiat-Shamir with Aborts paradigm, like the NIST-selected Dilithium signature scheme, our design choices target an improved complexity/compactness compromise that is highly relevant for many space-limited scenarios such as DNSSEC. 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.
Design rationale
Fiat-Shamir with Aborts
HAETAE follows the "Fiat-Shamir with Aborts" paradigm, like Dilithium or BLISS, which guarantees quantum security (in the QROM).
Module structure
To offer more flexibility and smaller sizes without losing in terms of implementation efficiency, HAETAE relies on module lattices. Varying the security and updating the parameter sets is easily achievable with the size-speed trade-offs.
Bimodal distribution
We use a bimodal distribution for the rejection sampling to reduce the sizes, like in the BLISS signature scheme, instead of a "unimodal" distribution like Dilithium.
Hyperball uniform sampling
We use uniform distributions over hyperballs, recently introduced in [DFPS22], instead of the SCA-vulnerable discrete Gaussian distributions used in BLISS.
Compact compression & encoding
We further reduce the key and the signature sizes by truncating the verification key and by compressing and encoding the signature.
On/off-line acceleration
HAETAE can be accelerated significantly by precomputing the hyperball samples.
Performance
All benchmarks were obtained on one core of an Intel Core i7-10700k, with TurboBoost and hyperthreading disabled. All cycle counts reported are the median of the cycle counts of 1,000 executions of the respective functions.
HAETAE-120
HAETAE-180
HAETAE-260
Resources
Specifications
2022.11.22. v0.9 (KpqC round 1 submitted)
Reference Implementations
2023.05.02. v1.0 (constant-time reference implementation)
2022.11.22. v0.9 (KpqC round 1 submitted)
Papers
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, In IACR eprint 2023. [eprint]
Team HAETAE
The HAETAE team consists of the following members (KpqC round 1 & NIST Additional Signature round 1).
Seoul National Univ. (KR)
CryptoLab Inc. (KR)
ENS de Lyon (FR)
After 1st round KpqC submission, the following members have joined/contributed.
Marc Möller (Ruhr Univ. Bochum)