Paper 2022/031

BAT: Small and Fast KEM over NTRU Lattices

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


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.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2022
Lattice-based cryptographyNTRUKEMFalcon
Contact author(s)
yang yu0986 @ gmail com
pa fouque @ gmail com
thomas pornin @ nccgroup com
paul kirchner @ irisa fr
2022-01-14: received
Short URL
Creative Commons Attribution


      author = {Pierre-Alain Fouque and Paul Kirchner and Thomas Pornin and Yang Yu},
      title = {BAT: Small and Fast KEM over NTRU Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2022/031},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.