Paper 2025/106

NTRU+Sign: Compact NTRU-Based Signatures Using Bimodal Distributions

Joo Woo, Korea University
Jonghyun Kim, Korea University
Ga Hee Hong, Korea University
Seungwoo Lee, Korea University
Minkyu Kim, The Affiliated Institute of ETRI
Hochang Lee, The Affiliated Institute of ETRI
Jong Hwan Park, Sangmyung University
Abstract

We present a new lattice-based signature scheme, called ‘NTRU+Sign’, using the Fiat-Shamir with Aborts framework. The proposed scheme is designed based on a novel NTRU-based key structure that fits well with bimodal distributions, enabling efficiency improvements compared to its predecessor, BLISS. The novel NTRU-based key structure is characterized by: (1) effectively changing a modulus from 2q to q, which is different from the existing usage of 2q for bimodal distributions, and (2) drastically reducing the magnitude of a secret key, which directly leads to compactness of signature sizes. We provide two concrete parameter sets for NTRU+Sign, supporting 93-bit and 211-bit security levels. Using the technique from GALACTICS (that was suggested as the constant-time implementation of BLISS), our analysis shows that NTRU+Sign achieves a good balance between computational efficiency and signature compactness, with constant-time implementation. For instance, at the NIST-3 security level, NTRU+Sign produces signatures that are significantly smaller than Dilithium and HAETAE, while providing faster verification speeds. These advantages position NTRU+Sign as a competitive and practical solution for real-world deployments.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-quantum cryptographyLattice-based signatures
Contact author(s)
woojoo0121 @ korea ac kr
yoswuk @ korea ac kr
hongh @ korea ac kr
kak5175 @ korea ac kr
mkkim @ nsr re kr
lhc254 @ nsr re kr
jhpark @ smu ac kr
History
2025-01-24: last of 2 revisions
2025-01-23: received
See all versions
Short URL
https://ia.cr/2025/106
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/106,
      author = {Joo Woo and Jonghyun Kim and Ga Hee Hong and Seungwoo Lee and Minkyu Kim and Hochang Lee and Jong Hwan Park},
      title = {{NTRU}+Sign: Compact {NTRU}-Based Signatures Using Bimodal Distributions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/106},
      year = {2025},
      url = {https://eprint.iacr.org/2025/106}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.