Paper 2025/1520

DAWN: Smaller and Faster NTRU Encryption via Double Encoding

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 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.