International Association
for Cryptologic Research

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.

At EUROCRYPT2012, Banerjee, Peikert, and Rosen introduced Ring Learning With Rounding (RLWR) problem and constructed lattice-based pseudorandom functions for the first time. Subsequently, Banerjee, Brenner, Leurent, Peikert, and Rosen named this family of lattice-based pseudorandom functions as SPRING, reanalyzed the security, and gave two practical instances. Building upon the SPRING family, Bouillaguet, Delaplace, Fouque, and Kirchner further extended it to a pseudorandom number generator called SPRING-RS. It is quite fast but still has a certain gap compared with the classical pseudorandom number generator based on symmetric cryptography, and the key size is large.In this work, we present LEAP, a lattice-based pseudorandom number generation scheme characterized by high performance, adaptable parameter selection, and extensive support for parallel processing. Unlike the RLWR problem used in public key cryptography, LEAP treats the public parameter in the RLWR problem as the key as well. Hiding the public parameters leads to larger lattice dimensions and higher standard deviations of error in the concrete security analysis compared to RLWR under identical parameters. These adjustments imply enhanced security, allowing smaller parameters while maintaining the same security level, thereby improving performance. Additionally, we introduce a novel framework that reuses multiple parameters, significantly enhancing overall performance. To mitigate the issue of increased key size caused by treating the public parameter as the key, we design a pseudorandom number generator leveraging the small key size characteristic of a variant of the NTRU assumption, which provides the key required for the high-performance pseudorandom number generator.Compared with the SPRING-RS, the LEAP can reduce the key size by 1.71X while improving performance by 3.30X at the same security level. Under the AVX2 and AVX512 implementations, the performance reaches 1.61 Cycles/byte and 1.14 Cycles/byte, and the throughput reaches 16.12 Gbps and 22.60 Gbps, respectively.