Cryptology ePrint Archive: Report 2022/031

BAT: Small and Fast KEM over NTRU Lattices

Pierre-Alain Fouque and Paul Kirchner and Thomas Pornin and Yang Yu

Abstract: We present $\BAT$ -- an IND-CCA secure key encapsulation mechanism (KEM) that is based on NTRU but follows an encryption/decryption paradigm distinct from classical NTRU KEMs. It demonstrates a new approach of decrypting NTRU ciphertext since its introduction 25 years ago. Instead of introducing an artificial masking parameter $p$ to decrypt the ciphertext, we use 2 linear equations in 2 unknowns to recover the message and the error. The encryption process is therefore close to the GGH scheme. However, since the secret key is now a short basis (not a vector), we need to modify the decryption algorithm and we present a new NTRU decoder. Thanks to the improved decoder, our scheme works with a smaller modulus and yields shorter ciphertexts, smaller than RSA-4096 for 128-bit classical security with comparable public-key size and much faster than RSA or even ECC. Meanwhile, the encryption and decryption are still simple and fast in spite of the complicated key generation. Overall, our KEM has more compact parameters than all current lattice-based schemes and a practical efficiency. Moreover, due to the similar key pair structure, $\BAT$ can be of special interest in some applications using Falcon signature that is also the most compact signature in the round 3 of the NIST post-quantum cryptography standardization. However, different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.

Category / Keywords: public-key cryptography / Lattice-based cryptography, NTRU, KEM, Falcon

Original Publication (in the same form): IACR-CHES-2022

Date: received 10 Jan 2022

Contact author: yang yu0986 at gmail com, pa fouque at gmail com, thomas pornin at nccgroup com, paul kirchner at irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20220114:072016 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]