International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

DAWN: Smaller and Faster NTRU Encryption via Double Encoding

Authors:
Yijian Liu , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Yu Zhang , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Xianhui Lu , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Yao Cheng , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Yongjian Yin , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
Abstract: This paper introduces DAWN, a compact and efficient NTRU encryption utilizing double encoding, which is provably secure under the NTRU assumption and the Ring-LWE assumption. We propose a novel technique for NTRU encryption called the zero divisor encoding. Unlike the polynomial encoding technique proposed by Hoffstein and Silverman (2001) and the vector encoding technique proposed by Zhang, Feng, and Yan in NEV (Asiacrypt 2023), our zero divisor encoding technique leverages the algebraic structure of the ring used in NTRU, enabling greater ciphertext compression while maintaining negligible decryption failure. We further develop a paradigm for NTRU encryption called the double encoding paradigm to maximize the potential of the zero divisor encoding. This paradigm transforms optimizing an NTRU-based encryption into constructing a better encoding within the NTRU context, providing more concrete direction for scheme development. Several previous NTRU encryptions can be situated within this paradigm with different parameters, facilitating direct comparison. We instantiate this paradigm based on the provably IND-CPA secure NTRU variant by Stehlé and Steinfeld (Eurocrypt 2011) to achieve an IND-CPA secure PKE, and subsequently employ the Fujisaki-Okamoto transformation to achieve an IND-CCA secure KEM. We present two parameter settings of DAWN: DAWN-alpha minimizes ciphertext size, achieving lengths of 436 bytes under NIST-I security and 973 bytes under NIST-V security; DAWN-beta minimizes the combined size of the public key and ciphertext, attaining combined sizes of 964 bytes under NIST-I security and 2054 bytes under NIST-V security. DAWN achieves superior compactness and performance among current lattice-based KEMs without introducing additional security assumptions. Compared to NEV (Asiacrypt 2023), the previously leading NTRU-based KEM in balancing compactness and performance, DAWN demonstrates 20%-29% greater compactness at approximate security levels and decryption failure probabilities, while executing 1.1X-2.0X faster in a complete ephemeral key exchange process.
BibTeX
@inproceedings{asiacrypt-2025-35917,
  title={DAWN: Smaller and Faster NTRU Encryption via Double Encoding},
  publisher={Springer-Verlag},
  author={Yijian Liu and Yu Zhang and Xianhui Lu and Yao Cheng and Yongjian Yin},
  year=2025
}