Pierre-Alain Fouque
email: pierre-alain.fouque@irisa.fr

Paul Kirchner
email: paul.kirchner@irisa.fr

Thomas Pornin
email: thomas.pornin@nccgroup.com

Yang Yu

BAT: Small and Fast KEM over NTRU Lattices

Keywords: Lattice-based cryptography, NTRU, KEM, Falcon

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 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. But different from Falcon, our KEM does not rely on floating-point arithmetic and can be fully implemented over the integers.

Introduction

Lattice-based schemes, especially when they have a polynomial structure, are a very strong contender for post-quantum cryptography. They can be faster than widely deployed cryptosystems based on RSA and ECDH. However, the sizes of public keys, signatures and ciphertexts are significantly larger than in RSA and even larger by an order of magnitude compared with ECDH cryptosystems. Such a large size is a major drawback of lattice schemes, and can be a crucial obstacle in the following situations:

-Real-world protocols may have a maximum length designed for classical cryptography.

For a standard Ethernet connection, the maximum transmission unit (MTU) is 1500 bytes 1 , and forward secrecy requires several objects.

-Large communication sizes increase the risk of lost packets and delays. Recent experiments on post-quantum TLS [START_REF] Paquin | Benchmarking post-quantum cryptography in TLS[END_REF] show that communication sizes come to govern the performance when the packet loss rate is higher than 3%. Moreover, [START_REF] Sikeridis | Assessing the overhead of postquantum cryptography in TLS 1.3 and SSH[END_REF] examines how the initial TCP window size affects post-quantum TLS and SSH performance, and show that even a small size increase can reduce the observed post-quantum slowdown by 50%. In addition, transmission energy can also be a significant part of the energy consumption on cryptography [START_REF] Saarinen | On PQC message lengths and some energy consumption myths[END_REF]. The size of signature schemes in TLS handshakes is also important as analyzed in [START_REF] Sikeridis | Post-quantum authentication in TLS 1.3: A performance study[END_REF].

-In some lightweight applications, e.g. internet of things (IoT), encryption and verification are done by some constrained devices. These devices only have small on-board storage and modest processors so that they may not be compatible with large public keys, signatures and ciphertexts.

With post-quantum cryptography standardization and deployment underway, it is important to explore new lattice-based cryptosystems with smaller parameters.

In this light, a natural choice is NTRU [START_REF] Hoffstein | NTRU: A ring-based public key cryptosystem[END_REF], as its structure reduces the data to one ring element. There have been many high-performance NTRU-based schemes ranging from Falcon [START_REF] Fouque | Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU[END_REF], BLISS [START_REF] Ducas | Lattice Signatures and Bimodal Gaussians[END_REF] for signature to NTRU-HRSS [START_REF] Hülsing | High-Speed Key Encapsulation from NTRU[END_REF], NTTRU [START_REF] Lyubashevsky | NTTRU: Truly Fast NTRU Using NTT[END_REF], NTRUEncrypt [START_REF] Chen | NIST PQ Submission: NTRUEncrypt A lattice based encryption algorithm[END_REF], NTRU Prime [START_REF] Bernstein | NTRU prime: Reducing attack surface at low cost[END_REF] for encryption and KEM. In particular, Falcon is the most compact signature in the round 3 of the NIST post-quantum cryptography standardization [START_REF]NIST: Round 3 candidates of the NIST Post-Quantum Cryptography Standardization[END_REF].

NTRU-based schemes are defined over some polynomial ring R that is R = Z[x]/(x n +1) with n a power-of-2 in this work. The secret key of an NTRU cryptosystem is essentially a pair of short polynomials (f, g) ∈ R 2 while the public key is h = f -1 g mod q. All NTRU encryption schemes, ranging from the earliest proposal [START_REF] Hoffstein | NTRU: A ring-based public key cryptosystem[END_REF] to the round 3 NIST submission [START_REF] Chen | NTRU: A submission to the NIST post-quantum standardization effort[END_REF], have followed essentially the same design rationale for more than 20 years. Concretely, the ciphertext is c = phr + m mod q where p is the masking modulus, r is the randomness, m is the message. A correct decryption is built upon that c = pgr + f m is short so that c = (f c mod q). The masking modulus p is also necessary to decrypt: one needs to first clean out pgr via reduction modulo p and then to recover m by multiplying the inverse of f modulo p. For typical NTRU KEMs, (f, g) is sparse and of length about C √ n for small constant C. By contrast, the design rationale for NTRU-based signatures went through some significant changes. The first NTRU-based signature is NTRUSign [START_REF] Hoffstein | NTRUSIGN: Digital Signatures Using the NTRU Lattice[END_REF] that is a hashand-sign scheme. However, its signature transcripts leak some secret key information so that NTRUSign and some variants were broken by statistical attacks [START_REF] Nguyen | Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures[END_REF][START_REF] Ducas | Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures[END_REF]. Later, Ducas et al. made use of the GPV hash-and-sign framework [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF] and proposed a provably secure NTRU-based signature [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF] that further developed into Falcon [START_REF] Fouque | Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU[END_REF]. The public key of Falcon is still h = f -1 g mod q for some short (f, g), while the actual secret key is a trapdoor basis B f,g = g G f F ∈ R 2×2 such that gF -f G = q. The signing of Falcon is essentially Gaussian sampling with a trapdoor [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF][START_REF] Ducas | Fast Fourier Orthogonalization[END_REF]. Consequently, the signature size depends on the maximal Gram-Schmidt norm of B f,g . As analyzed in [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF], Falcon chooses (f, g) of (f, g) ≈ 1.17 √ q for optimal parameters. Therefore, (f, g) in Falcon is independent of n, which is different from the case of NTRU KEMs. Some other NTRU-based signatures [START_REF] Ducas | Lattice Signatures and Bimodal Gaussians[END_REF][START_REF] Das | Modular lattice signatures, revisited. Designs[END_REF], do just use one vector (f, g) as the secret key as the case of NTRU KEMs. However, to the best of our knowledge, there is no practical NTRU-based KEM using a trapdoor basis as the secret key. Intuitively we expect (F, G) to yield one more equation in decryption so that one can recover both the message and encryption randomness via two equations. This in effect gets rid of the masking modulus p in classical NTRU KEMs and thus hopefully allows smaller parameters. Moreover, when we unify the trapdoor function for both signature and KEM part of the code can be shared, and we may also reduce some storage and communication. Therefore, it would be interesting to investigate the practicality of a trapdoor basis for KEM.

Indeed, the earliest lattice-based cryptosystem GGH (Goldreich-Goldwasser-Halevi [START_REF] Goldreich | Public-Key Cryptosystems from Lattice Reduction Problems[END_REF]) uses a trapdoor basis as the secret key and implements both encryption and signature based on that trapdoor function. Later Micciancio improved the GGH trapdoor function by using the Hermite normal form [START_REF] Micciancio | Improving lattice based cryptosystems using the Hermite normal form[END_REF]. While GGH encryption has a long history as NTRU, its practicality is far from well-studied and there is no GGH-like encryption/KEM with concrete parameter and security analysis so far.

Our contributions. We present a new KEM based on NTRU, called BAT2 . Similar to Falcon signature, BAT uses h = f -1 g mod q as the public key and its secret key is a trapdoor basis B f,g with an additional ring element (for faster decapsulation). In addition, BAT shares the same leading design principle with Falcon, i.e. minimizing the communication size.

Our main improvement in BAT-KEM is a better decapsulation algorithm, which represents a major modification to the NTRU encryption scheme since its introduction 25 years ago. Instead of following the original NTRU, we modify it according to the GGH-Micciancio blueprint [START_REF] Goldreich | Public-key cryptosystems from lattice reduction problems[END_REF][START_REF] Micciancio | Improving lattice based cryptosystems using the Hermite normal form[END_REF]. The message m is now encapsulated as c = hm + e mod q where h is the NTRU public key and e is a small error. The decapsulation corresponds to applying Babai's nearest plane algorithm with the secret basis to decode the closest lattice point, and therefore recovering the message. Compared with other NTRU KEMs, we do not need the masking modulus p to extract the message. Instead of multiplying only by f , we multiply by F so that we get 2 linear equations in the 2 unknowns e, m.

However, Babai's nearest plane algorithm heavily relies on floating-point arithmetic, although most expensive calculation can be done in a pre-computation phase. To avoid floating-point arithmetic in the decapsulation, we replace the high-precision Gram-Schmidt vectors with integral approximations. Additionally, notice that m and e do not necessarily follow the identical distribution, hence we take into account their different sizes to optimize the decoding. We also use the Learning With Rounding (LWR) assumption [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF][START_REF] Chen | On the hardness of the computational Ring-LWR problem and its applications[END_REF] in order to further reduce the size of the ciphertext. Our improved decoding algorithm can be used with a smaller modulus and dropping more bits, and thereby increases the security of the scheme and decreases the communication.

Overall, our KEM achieves very impressive performance. First of all, for the same NIST security level, BAT achieves the smallest communication size, namely "public key size + ciphertext size", among all current lattice cryposystems and even RSA cryptosystems. Secondly, the complexity of the code as well as its running time is asymmetric: while the key generation is complicated, the frequent key usage is quite efficient. Specifically, the encryption is very simple -essentially a ring multiplication -, and the decryption also boils down to a few ring additions and multiplications. Cheap daily operations make BAT particularly compatible with small devices. Thirdly, we can implement the whole scheme fully over integers, which is different from the case of Falcon. Our implementation is constant-time and uses some AVX2 optimizations. We can notice that BAT has performance comparable to Kyber while being more compact. Furthermore, it is comparable to SIKE p434 in size while being much more efficient. We gave the timing with x86 assembly optimization, while with the same level of optimization we did, the SIKE performance timing would be higher by one order of magnitude. We summarize the detailed comparisons with some well-known schemes in Table 2.

Finally, we explain in a simplistic way why the new decryption algorithm leads to smaller parameters. To correctly decrypt, our KEM needs (f c mod q) = gm + f e, i.e. gm + f e ∞ < q 2 , while previous NTRU KEMs need pgr + f m ∞ < q 2 . We also compare with ring-LWE-based KEMs. For a typical ring-LWE-based KEM, its secret

key is (f, g) ∈ R 2 , public key is (a, b = af + g) ∈ (R/qR) 2 and ciphertext is (c 1 = ae 0 + e 1 , c 2 = be 0 + e 2 + q 2 m) ∈ (R/qR) 2 .
The requirement for correct decryption is e 0 g -e 1 f + e 2 ∞ < q 4 . Suppose that m, e, r, e i are drawn from a distribution of standard deviation σ e and f, g from a distribution of standard deviation σ f . The coefficients of gm + f e, pgr + f m, e 0 g -e 1 f + e 2 are modeled as Gaussian. The comparison on parameter restrictions are summarized in Table 1. It can be seen that given (n, τ, σ e , σ f ), BAT allows a smaller modulus q. Note that for fixed (n, σ e , σ f ), a smaller q implies higher security. Comparison with Falcon. BAT is similar in spirit to Falcon signature: they both achieve good compactness by using some nice NTRU trapdoor basis as the secret key. Nevertheless, some crucial distinctions exist between BAT and Falcon.

-At a high level, BAT and Falcon exploit their trapdoor to solve CVP (closest vector problem), but the used CVP algorithms are very different. Specifically, Falcon makes use of the KGPV Gaussian sampler [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF] that is a randomized Babai's nearest plane algorithm. In contrast, BAT decrypts with a deterministic NTRU decoder that can be viewed as a hybrid of Babai's round-off and nearest plane algorithms.

-The algorithms of BAT are simpler than those of Falcon. On the one hand, the signing of Falcon relies on high-precision Gaussian sampling, but the encryption and decryption of BAT only need basic integer operations. On the other, Falcon includes many high-precision intermediate values along with the trapdoor for faster signing, but BAT just adds one integral polynomial for faster decryption.

-The NTRU trapdoors of BAT and Falcon are generated in different ways. In fact, Falcon chooses its trapdoor for smaller signatures, which is equivalent to minimizing the maximal Gram-Schmidt norm of the trapdoor basis. As for BAT, the trapdoor is generated to minimize the decryption failure, and according to our new decoder, the distributions of the message and error will also affect the trapdoor generation (see Section 3 for more details).

Related work.

Very recently, Chuengsatiansup et al. [START_REF] Chuengsatiansup | ModFalcon: compact signatures based on module NTRU lattices[END_REF] propose some extensions of Falcon signature and NTRU encryption over Module-NTRU lattices. This allows more flexible parameters for NTRU-based cryptosystems. Our techniques are likely to apply to the Module-NTRU-based schemes as well.

In order to improve parameters, some schemes [START_REF] Cheon | Lizard: Cut off the tail! A practical postquantum public-key encryption from LWE and LWR[END_REF][START_REF] Zhang | Tweaking the Asymmetry of Asymmetric-Key Cryptography on Lattices: KEMs and Signatures of Smaller Sizes[END_REF] are built upon a variant of LWE in which the secret and error follow different distributions. Our work makes use of a similar idea. Yet the main difference is that our KEM follows a novel pattern which is essential to minimize the parameters.

Roadmap. We start in Section 2 with some preliminary materials. In Section 3, we introduce a new decoding algorithm that is the building block of our NTRU-based KEM. Section 4 presents our KEM in details. We give security proofs and estimates in Section 5 and implementation details in Section 6.

Preliminaries

Notations

We follow the setting Z q = {-( q/2 -1), -( q/2 -2), • • • , q -q/2 } and (a mod q) ∈ Z q for any a ∈ Z. Let ln (resp. log) denote the logarithm with base e (resp. 2). For an integer q > 0, let a q = aq /q ∈ (1/q) • Z for a ∈ R. For a real-valued function f and a countable set S, we write f (S) = x∈S f (x) assuming that this sum is absolutely convergent.

Linear algebra

Let B = (b 0 , . . . , b n-1 ) ∈ Q n×n of rank n. The Gram-Schmidt orthogonalization of B is B = B * U, where U ∈ Q n×n is upper-triangular with 1 on its diagonal and B * = (b * 0 , . . . , b * n-1
) is a matrix with pairwise orthogonal columns. Let R n = Z[x]/(x n + 1) with n a power-of-2 and K n = Q[x]/(x n + 1). We denote by (R n mod q) the ring R n /qR n . When the context is clear, we may write R n (resp.

K n ) as R (resp. K). We identify f = n-1 i=0 f i x i ∈ K n with its coefficient vector coef (f ) = (f 0 , • • • , f n-1 ). Let f = coef (f ) and f ∞ = coef (f ) ∞ . We denote by f the conjugate of f , i.e. f (x -1 ). Let 1 = n-1 i=0 x i ∈ R.
The symbol • q is naturally generalized to K n by applying it coefficient-wise.

Probability and statistics

Given a distribution χ, we write z ← χ when the random variable z is drawn from χ. For z ← χ, let µ[z] (resp. σ[z]) denote the expectation (resp. standard deviation) of z, and

µ[χ] := µ[z] (resp. σ[χ] := σ[z]). If µ[χ] = 0, then χ is called centered. For a random a ∈ K, if all its coefficients independently follow a distribution χ, then we call a iid-random over χ. If a ∈ K is iid-random over χ, we write σ a = σ[χ] and µ a = µ[χ]. We call it centered when µ a = 0.
For a distribution χ, we denote by Sample(χ) the procedure of generating a random sample of χ and by Sample(χ; seed) the sampling procedure with seed seed. For a finite set S, let U (S) be the uniform distribution over S. In particular, for a positive integer k,

σ[U (Z k )] = k 2 -1 12 and µ[U (Z k )] = 0 if k is odd; otherwise µ[U (Z k )] = 1 2 . For c ∈ R and σ > 0, let ρ σ,c (x) = exp -(x-c) 2 2σ 2
be the one-dimensional Gaussian function with center c and standard deviation σ. When c = 0, we just write ρ σ (x). The discrete Gaussian over integers with center c and standard deviation σ is defined by the probability function

D Z,σ,c (x) = ρ σ,c (x) ρ σ,c (Z) , ∀x ∈ Z. Let erf(x) = 2 √ π x 0 exp(-t 2
)dt be the error function. For a random variable X following a normal distribution with mean 0 and variance 1/2, erf(x) is the probability of X in the range [-x, x].

NTRU

Given f, g ∈ R such that f is invertible modulo some q ∈ Z, let h = f -1 g mod q.
The NTRU lattice defined by h is denoted by [START_REF] Hoffstein | NTRUSIGN: Digital Signatures Using the NTRU Lattice[END_REF][START_REF] Pornin | More efficient algorithms for the NTRU key generation using the field norm[END_REF]. Fixing (f, g), there are infinitely many such bases, whereas these bases have the same Gram-Schmidt norms. Hence, we simply write

L h,q = {(u, v) t | u = hv mod q}. Given (f, g), one can compute g G f F ∈ R 2×2 a basis of L h,q by solving the NTRU equation gF -f G = q
B f,g = g G f F ∈ R 2×2 .
While the public key of an NTRU-based scheme is h itself, the secret key can have different forms. For most NTRU encryption schemes, the secret key is (g, f ) itself, i.e. one short vector of L h,q . But for some other applications, e.g. signature and IBE, the secret key is B f,g called an NTRU trapdoor basis. Falcon [START_REF] Fouque | Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU[END_REF] is a representative example. Falcon is an NTRU-based signature following the GPV hash-and-sign framework [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF]. To sign a message m, the signer computes a pair of short polynomials (s 1 , s 2 ) such that s 1 + hs 2 = Hash(m). This procedure is accomplished by lattice Gaussian sampling with B f,g and the length of the signature (s 1 , s 2 ) depends on the sampled Gaussian width. The Gaussian sampler of Falcon is a fast Fourier variant [START_REF] Ducas | Fast Fourier Orthogonalization[END_REF] of the KGPV sampler [START_REF] Gentry | Trapdoors for Hard Lattices and New Cryptographic Constructions[END_REF], hence the signature size is proportional to the maximal Gram-Schmidt norm of B f,g . For optimal parameters, Falcon generates (f, g) such that (f, g) ≈ 1.17

√ q as per [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF].

A New NTRU Decoder

In this section we present a new NTRU decoding algorithm that is the key component of our KEM. In the context of NTRU, the code words are hs + e mod q where h is the public key and s, e are small polynomials. The decoding process recovers (s, e) with an NTRU trapdoor. An ideal decoder is supposed to satisfy:

1. All operations are simple and efficient; no high-precision arithmetic is needed.

2. The decoding distance is large, i.e. being able to recover large errors (s, e). Note that for our KEM, larger errors correspond to higher security level.

There have been two famed decoding algorithms due to Babai [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]: Babai's round-off algorithm (RO for short) and Babai's nearest plane algorithm (NP for short). They have respective pros and cons. The RO algorithm outperforms NP in efficiency and simplicity.

In addition, RO is particularly compatible with q-ary lattices: all operations are over Z q . By contrast, NP is capable of decoding larger errors in both the worst and average cases [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF]. Yet the principal drawback of NP is its reliance on high-precision arithmetic.

Our decoder improves on both RO and NP. First, it is able to tackle a larger decoding distance than RO. Second, while complicated computations are still required, all involved algorithms can be implemented using fixed-point arithmetic in practice, which outperforms NP. Meanwhile these expensive computations can be done in the pre-computation and therefore do not affect the decoding efficiency. With an auxiliary integer vector, our algorithm achieves the same efficiency as RO and totally performs over integers. To optimize the decoding, our algorithm also takes into account the distributions of s and e.

Babai's algorithms for NTRU

For better contrast, we first recall RO and NP briefly in the NTRU setting. Let h ∈ (R mod q) be the public key and B f,g = g G f F ∈ R 2×2 be the trapdoor basis. In later discussion, we shall treat L h,q as a R-module of rank 2 rather than a Z-module of rank 2n.

The application of RO related to NTRU dates back to NTRUSign [START_REF] Hoffstein | NTRUSIGN: Digital Signatures Using the NTRU Lattice[END_REF]. Given c = hs + e ∈ (R mod q), we have

c 0 ∈ L h,q + e -s . The RO algorithm computes e -s = c 0 -B f,g B -1 f,g c 0 as e -s . As B -1 f,g = 1 q F -G -f g , a correct decoding such that (e , s ) = (e, s) follows if F -G -f g e -s = F c mod q -f c mod q . This is equivalent to max{ f e + gs ∞ , F e + Gs ∞ } ≤ q 2 .
The NP algorithm is more complicated. It involves the Gram-Schmidt orthogonal basis

B * f,g = g G * = G -vg f F * = F -vf where v = F f +Gg f f +gg . A correct decoding follows if max{ f e + gs ∞ , F * e + G * s ∞ } ≤ q 2 .
In some applications [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF][START_REF] Fouque | Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU[END_REF], the trapdoor basis is optimal with respect to Gram-Schmidt norms: (g, f ) ≈ (G * , F * ) . However, (g, f ) and (G, F ) are not so close:

(G, F ) ≈ n 12 • (g, f ) [START_REF] Hoffstein | NTRUSIGN: Digital Signatures Using the NTRU Lattice[END_REF]. As a consequence, (e, s) is dominated by the large (G, F ) in the RO algorithm but by the small (g, f ) in the NP algorithm, which leads to a gap of O( √ n).

Our decoding algorithm for NTRU

As shown in Section 3.1, RO boils down to solving two linear equations over R (without modular reduction). To enlarge its decoding range, we hope to replace the large (G, F ) with some small vector (G , F ) of size

≈ (g, f ) . A natural candidate is (G * , F * ) = (G -vg, F -vf ) with v = F f +Gg f f +gg as in NP.
However, if we want to work with (G * , F * ) directly, we have to resort to high-precision arithmetic. To overcome the precision issue, we choose (G , F ) = (G -g v q , F -f v q ) ∈ (1/q )R 2 . When q is sufficiently large, (G , F ) converges to (G * , F * ) whose norm is about (g, f ) . In practice, a moderate q suffices to significantly improve the decoding.

We further refine our decoder as per the distributions of s and e. We focus on the common case where both s and e are iid-random over some publicly known distributions χ s and χ e . In practice, χ s and χ e are not necessarily same even close, which may cause a gap between the sizes of s and e. For example, when s e , we expect a better decoding by using a basis

g G f F with g > g ≈ f > f and G > G ≈ F > F .
To this end, we introduce a parameter γ, by default γ = σ e /σ s , to compute the optimal decoding basis. Moreover, χ s and χ e do not have to be centered neither, e.g. χ s = U (Z 2 ). For given (f, g), non-centered s and e lead to a non-zero average of f e + gs. Therefore, we also consider the impact of µ s and µ e during decoding. Here we assume µ s , µ e ∈ 1 Q • Z for some Q ∈ N, which is indeed the case of our later schemes.

The decoding algorithm consists in two steps: (1) computing the auxiliary polynomial w and (2) recovering (s, e). They are illustrated in Algorithms 3.1 and 3.2 respectively. Notably, both algorithms can be fully implemented over the integers. In Algorithm 3.1, the computation of v consists in one polynomial division, but the final output is actually an integral approximation of q v, which can be computed with fixed-point values. More details are presented in Section 6.1.

Algorithm 3.1 ComputeVec

Input: a trapdoor basis B f,g = g G f F ∈ R 2×2 , q ∈ N and γ > 0; Output: w ∈ R 1: v ← γ 2 F f +Gg γ 2 f f +gg 2: return w = q v q Algorithm 3.2 Decode Input: a trapdoor basis B f,g = g G f F ∈ R 2×2 , w ∈ R, q, q , Q ∈ N, c = (hs + e mod q) ∈ R with small (e, s) and µ e , µ s ∈ 1 Q • Z Output: (e, s) ∈ R 2 1: (G d , F d ) ← (q G -gw, q F -f w) 2: c ← (Qf c -f (Qµ e 1) -g(Qµ s 1) mod qQ) 3: c ← (q QF c -F (q Qµ e 1) -G(q Qµ s 1) -c w mod qq Q) 4: solving e s from f g F d G d e s = 1 Q • c c 5: return (e = e + µ e 1, s = s + µ s 1)
Theorem 1 gives the probability of correct decoding of Algorithm 3.2 and its proof is in Appendix A.

Theorem 1. Let R = Z[x]/(x n + 1) with n a power-of-2 and q ∈ N. Let f, g ∈ R be iid- random over D Z,σ f and h = f -1 g mod q. Let B f,g = g G f F ∈ R 2×2 be an NTRU basis.
Let s, e ∈ R be iid-random over χ s and χ e respectively, and

µ e , µ s ∈ 1 Q • Z for some Q ∈ N. Let γ = σ e /σ s , q ∈ N and w = ComputeVec(B f,g , q , γ). Let I(γ) = 2 ln(γ) γ 2 -1 for γ = 1 and I(1) = 1. Let σ 1 = √ nσ f σ s γ 2 + 1, σ 2 = σ s qγ √ n•σ f I(γ) + n 1.5 √ γ 2 +1 2q σ f . Let τ = min q 2 √ 2σ1 , q 2 √ 2σ2 .
Then the probability of Decode(B f,g , w, q, q , Q, (hs+e mod q)) = (e, s) is heuristically estimated at least 1 -2n • (1 -erf(τ )) over the randomness of s and e.

Decoding failure rate

Theorem 1 gives a heuristic estimate for µ[P (B f,g , w, χ s , χ e )] (over the randomness of (f, g)) where P (B f,g , w, χ s , χ e ) = Pr[Decode(B f,g , w, q, q , Q, (hs + e mod q)) = (e, s) | e ← χ e , s ← χ s ] is the decoding failure rate for given (B f,g , w). In fact, it is hard to numerically compute µ[P (B f,g , w, χ s , χ e )], since the distribution of (G , F ) (defined in Lemma 1) is complicated. But it is easy to numerically compute P (B f,g , w, χ s , χ e ) given (B f,g , w).

We experimentally calculate P (B f,g , w, χ s , χ e ) for some (B f,g , w) generated with the suggested parameters (see Tables 3 and4). The failure probabilities are smaller than for a naive Gaussian model, and significantly so for a ring dimension of 256.

BAT KEM

In this section, we present a KEM scheme, called BAT, constructed following the aforementioned encode/decode paradigm. Its secret key is an NTRU trapdoor basis as in the Falcon signature. As a consequence, some codes for Falcon implementation can be reused.

BAT permits very compact parameters. Specifically, the modulus q is greatly reduced in contrast to Falcon. More remarkably, the ciphertext is well compressed: each coefficient requires only less than one byte of storage.

Algorithm description

Prior to the description of our KEM, we first present the underlying public key encryption. It is specified by the following parameters:

-R = Z[x]/(x n + 1) with n = 2 l .

q = bk + 1 with b, k ∈ N. Note that b determines the size of each ciphertext coefficient and k determines the decoding distance.

q ∈ N is used to control the decryption failure rate.

At a high level, our idea is to build an encryption scheme upon a one-way trapdoor function. Indeed, for a pseudorandom public key h, the function F (s, e) = hs + e mod q is one-way under the Ring-LWE assumption, but one can invert it with the trapdoor B f,g as shown in Section 3. In our scheme, the encryption consists in computing c = F (s, e) and the decryption in recovering s by inverting F (s, e).

The key generation is shown in Algorithm 4.1. The first step is to generate an NTRU trapdoor basis B f,g along with the public key h. This is similar to the Falcon key generation, but the size of the secret key is changed. The second step pre-computes an auxiliary vector w. As explained in Section 3, w is used for decoding a larger error while avoiding floating-point arithmetic in the decapsulation. We include it as a part of the secret key. Note that Falcon key generation also pre-computes the Falcon tree for signing, but that computation is useless in our scheme.

The encryption algorithm is described in Algorithm 4.2. The message space is M = {0, 1} λ where λ denotes the claimed security level. To achieve the IND-CPA security, we compute the trapdoor function on an ephemeral s and then mask the message m with hashed s. For better compactness, we replace F (s, e) with F (s) = (hs mod q) k and thus use Ring-LWR as the hardness assumption. It is easy to see that the storage of a ciphertext is n log b + λ bits. The decryption stems from the decoding algorithm in Section 3. The formal description is provided in Algorithm 4.3.

Algorithm 4.1 KeyGen Enc

Input: the ring R = Z[x]/(x n + 1), integers q, k, q ∈ N Output: public key h ∈ R, secret key (B f,g , w) ∈ R 2×2 × R where B f,g = g G f F 1: γ ← k 2 -1 3 2: σ f ← qγ n I(γ) γ 2 +1
where I(γ) is defined as in Theorem 1 return ⊥ 6: end if 7: c 2 ← Hash m (s) m where Hash m is some hash with range M 8: return (c 1 , c 2 ) Algorithm 4.3 Decrypt Input: ciphertext (c 1 , c 2 ), public key h ∈ R, secret key (B f,g , w), integers q, k, q ∈ N Output: message m 1: c ← c 1 k 2: (e, s) ← Decode (B f,g , w, q, q , 2, c ) By some standard techniques [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF][START_REF] Dent | A designer's guide to KEMs[END_REF], an IND-CCA secure KEM immediately follows from our IND-CPA encryption. Algorithms 4.4, 4.5 and 4.6 describe the key generation, encapsulation and decapsulation algorithms respectively, in which S (resp. K) is the set of seed (resp. shared key). The detailed security arguments are given in Section 5.2.

3: f, g ← D R,σ f 4: if f or g is not invertible in (R mod q) then 5: restart 6: end if 7: if (g, γf ) > √ nσ f γ 2 + 1 then 8: restart 9: end if 10: h ← f -1 g mod q 11: compute (F, G) ∈ R 2 such that gF -Gf = q 12: B f,g ← g G f F ∈ R 2×2 13: w ← ComputeVec(B f,g , q , γ) 14: (G d , F d ) ← (q G -gw, q F -f w) 15: if (G d , γF d ) > q qγ √ n•σ f I(γ) + n 1.5 √ γ 2 +1 2q σ f then 16: restart 17: end if 18: return (h, (B f,g , w)) Algorithm 4.2 Encrypt Input: public key h ∈ R, integers q, k ∈ N, message m ∈ M, seed seed Output: ciphertext (c 1 , c 2 ) 1: s ← Sample(U (R mod 2); seed) 2: c 1 ← (hs mod q) k 3: e ← (hs mod q) -kc 1 , γ ← k 2 -1
3: γ ← k 2 -1
Our KEM tolerates a small decryption failure rate for better performance, as many current lattice-based KEMs. Yet some works [START_REF] Gama | New chosen-ciphertext attacks on NTRU[END_REF][START_REF] D'anvers | Decryption failure attacks on IND-CCA secure lattice-based schemes[END_REF][START_REF] Guo | A Novel CCA Attack Using Decryption Errors Against LAC[END_REF][START_REF] D'anvers | One) Failure Is Not an Option: Bootstrapping the Search for Failures in Lattice-Based Encryption Schemes[END_REF] also show the impact of decryption failures on security. We bound the size of the error used to 1.08 its average to limit the impact of precomputed messages on the decryption failure rates: the exponent may be reduced by 20 % in the worst case.

Algorithm 4.4 KeyGen Encap

Input: the ring R = Z[x]/(x n + 1), integers q, k, q ∈ N Output: public key h ∈ R, secret key (B f,g , w, r) ∈ R 2×2 × R × R 1: r ← Sample(U (M)) 2: (h, (B f,g , w)) ← KeyGen Enc (R, q, k, q ) 3: return (h, (B f,g , w, r))

Algorithm 4.5 Encapsulate Input: public key h ∈ R, integers q, k ∈ N Output: ciphertext c, key K 1: m ← Sample(U (M)) 2: (c 1 , c 2 ) ← Encrypt(h, q, k, m, Hash s (m))
where Hash s is some hash with range S 3: if (c 1 , c 2 ) =⊥ then 4:

restart 5: end if 6: K ← Hash k (m, c 1 , c 2 )
where Hash k is some hash with range K 7: return ((c 1 , c 2 ), K)

Parameter selection

We keep the same ring R as Falcon but choose a much smaller modulus q. Indeed, a smaller modulus forbids the applications of a complete NTT, nevertheless similar techniques [START_REF] Lyubashevsky | Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs[END_REF][START_REF] Lyubashevsky | NTTRU: Truly Fast NTRU Using NTT[END_REF] still allow a very fast polynomial multiplication. For security, a smaller q implies a smaller Algorithm 4.6 Decapsulate Input: ciphertext (c 1 , c 2 ), public key h ∈ R, secret key (B f,g , w, r), integers q, k, q ∈ N Output: key K 1: m ← Decrypt((c 1 , c 2 ), h, (B f,g , w), q, k, q ) 2: if m =⊥ and (c 1 , c 2 ) = Encrypt(h, q, k, m , Hash s (m )) then 3:

return K ← Hash k (m , c 1 , c 2 ) 4: else 5: return K ← F(r, c 1 , c 2 )
where F is some PRF with range K 6: end if 7: return K standard deviation of the secret key distribution and then less entropy of the secret key. But such loss does not reduce much the concrete security level.

A notable modification exists in key generation. In Falcon, (f, g) is sampled to make (g, f ) ≈ (G * , F * ) where (G * , F * ) is the Gram-Schmidt orthogonalization of (G, F ) in B f,g . However, in BAT, we choose σ f satisfying

√ nσ f γ 2 + 1 = qγ √ n•σ f I(γ).
This gives rise to a nearly optimal decryption failure rate according to Theorem 1. In particular, when γ = 1, the σ f we use also makes (g, f ) ≈ (G * , F * ) as the case of Falcon. But for this case, σ used by BAT is different from that by Falcon, which is explained in Remark 4.

Let us recall that

c = ck = hs -k hs k - (hs mod q) k := hs + e mod q.
We model e drawn from U (Z n k ) and thus

3 σ e = k 2 -1 12 . As σ s = 1 2 , it follows that γ = σ e /σ s = k 2 -1
3 . The decryption failure rate is equal to the probability of incorrect decoding. According to Theorem 1, the decryption failure rate is heuristically bounded by 2n • (1 -erf(τ )) for some τ . We also exactly computed the decryption failure rate for 100 keys: the standard deviation of the logarithm of the rate over the secret key distribution is around 8, and the exact values are even smaller than their heuristic estimates. Therefore we present the exact values for the decryption failure rate and the tail-bound parameter τ for the heuristic estimates.

Table 3 shows the suggested parameters. The parameter set for lightweight BAT. We further suggest one more parameter set particularly aiming at a lower security level, say 80 bits of security, which may be of interest for some lightweight use-cases. We call this lightweight variant LW-BAT. In LW-BAT, the degree n is only 256; for better compactness the modulus q does not support NTT anymore. We choose a relatively high decryption failure rate 2 -71.9 , but it should be sufficient for lightweight applications, e.g. IoT: for the Round5 IoT parameters [START_REF] Baan | Round5: KEM and PKE based on (Ring) Learning with Rounding[END_REF], the decryption failure rate is 2 -41 even larger than ours. Table 4 summarizes the concrete parameter set.

Security

We now report on the security of BAT. First, we demonstrate the IND-CCA security of our KEM under some hardness assumptions. Then we estimate the concrete security according to the best known attacks.

Assumptions

The (decision) NTRU assumption. Let R × q be the set of invertible elements in R/qR. Let χ be some distribution over R × q . The advantage of adversary A in solving the decision NTRU problem NTRU R,q,χ is

Adv NTRU R,q,χ (A) = Pr[b = 1 | f, g ← χ; b ← A(f -1 g mod q)] -Pr[b = 1 u ← U (R × q ); b ← A(u)
] . In our case, R = Z[x]/(x n + 1) and χ is the distribution of the secret key f and g.

Remark 1. There are some researches on the hardness of the decision NTRU assumption over R = Z[x]/(x n + 1). Notably, as shown in [START_REF] Stehlé | Making NTRU as secure as worst-case problems over ideal lattices[END_REF], when χ is a discrete Gaussian of standard deviation σ = ω(n √ q), the ratio of f and g is statistically indistinguishable from uniform, which gives a firm theoretical grounding. The decision NTRU assumption with a narrow distribution χ is also closely related to Falcon [START_REF] Fouque | Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU[END_REF] and sometimes referred to as the Decisional Small Polynomial Ratio (DSPR) assumption [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF][START_REF] Brakerski | Lossiness and Entropic Hardness for Ring-LWE[END_REF].

The (search) Ring-LWR assumption. Let χ be some distribution over R. The advantage of adversary A in solving the search Ring-LWR problem RLWR R,q,k,χ is

Adv RLWR R,q,k,χ (A) = Pr a← U (R × q ),s← χ
A a, (as mod q) k = s .

In our case, R = Z[x]/(x n + 1) and χ = U (R mod 2).

Remark 2. The theoretical foundation of the search Ring-LWR assumption is developed in [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF][START_REF] Bogdanov | On the hardness of learning with rounding over small modulus[END_REF][START_REF] Chen | On the hardness of the computational Ring-LWR problem and its applications[END_REF]. There are also some practical schemes, e.g. Lizard [START_REF] Cheon | Lizard: Cut off the tail! A practical postquantum public-key encryption from LWE and LWR[END_REF] and Saber [START_REF] Basso | SABER: Mod-LWR based KEM[END_REF], using the Ring-LWR over Z[x]/(x n + 1) or its module variant as their hardness assumption. Indeed, the provable hardness of Ring-LWR with a binary secret s remains open. Yet this would not weaken the concrete security especially when q is relatively small (as in our case).

KEM security

The security notion we prove for BAT is IND-CCA security (indistinguishability against chosen-ciphertext attacks). To this end, we first note that the underlying encryption (Algorithms 4.2 and 4.3) is IND-CPA secure (indistinguishability against chosen-plaintext attacks) under the assumptions in Section 5.1.

Theorem 2. Let Π be the public key encryption scheme defined by Algorithms 4.1, 4.2 and 4.3. Let Hash m be modeled as a random function. For any adversary A, there exist adversaries A 1 and A 2 of roughly the same running time as that of A such that

Adv IND-CPA Π (A) ≤ Adv NTRU R,q,χ1 (A 1 ) + Adv RLWR R,q,k,χ2 (A 2 )
where χ 1 is the distribution of the secret key (f, g) and χ 2 = U (R mod 2).

Theorem 3. [[43], Corollary 4.7]

Let Π be the public key encryption scheme defined by Algorithms 4.1, 4.2 and 4.3. Let M, C, K and S be the message, ciphertext, key and seed spaces of Π. Let Π CCA be the IND-CCA secure KEM defined by Algorithms 4.4,4.5 and 4.6. Let Hash m : R → M, Hash s : M → S and Hash k : M × C → K be quantum-accessible random oracles. Let F : M × C → K be a PRF. Let δ be the decryption error rate of Π and η be the injectiveness parameter of the derandomized Π by Hash s . 4 For an IND-CCA adversary A against Π CCA issuing at most q H (resp. q S ) quantum queries to Hash k (resp. Hash s ) with query depth at most d H (resp. d S ) and at most q dec classical decapsulation queries, we can construct two adversaries of running time roughly bounded by 3 • T ime A . These adversaries are:

-an IND-CPA adversary A against Π; -a PRF adversary A against F issuing at most q dec queries.

These adversaries satisfy:

Adv IND-CCA Π CCA (A) ≤ 8 • d H • (d S + 1) • Adv IND-CPA Π (A ) + 8 • (3q S + 1) |M| + 6 • (3q S + q dec ) • (8d S + 1)δ + 3η + (4d H + 12) • η + 2Adv PRF F (A ).

Concrete security

We estimate the concrete security based on the primal attack and the hybrid attack that are two best known attacks in lattice-based cryptography. Additionally, an attacker can break a KEM through either key recovery or message recovery. For BAT, the cost of key recovery relies on the hardness of the NTRU assumption, while the cost of message recovery relies on the hardness of the Ring-LWR assumption. Thus, we respectively analyze the costs of key recovery and message recovery based on the primal and hybrid attack.

Cost of lattice reduction

We begin with a brief introduction to lattice reduction that is heavily used by both primal and hybrid attacks. Currently, the most practical lattice reduction algorithms are BKZ [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF] and BKZ 2.0 [START_REF] Chen | BKZ 2.0: Better Lattice Security Estimates[END_REF]. Let BKZ-β denote the BKZ/BKZ 2.0 with blocksize β. For a d-dimensional lattice L, BKZ-β would generally find some v ∈ L with v ≤ δ d β vol(L) 1/d and

δ β ≈ (πβ) 1 β β 2πe 1 2(β-1) when d > β > 50.
The cost of running BKZ-β on a d-dimensional lattice is estimated by

C BKZ-β = t • d • C SVP-β
where t is the tour number BKZ-β takes and C SVP-β is the cost of solving SVP on a β-dimensional lattice. We follow a typical setting taking quantum speedups into account:

t = 1, C SVP-β = 2 0.265β+16.4 , C BKZ-β = d • 2 0.265β+16.4 .
Remark 3. The BKZ cost model we use is not extremely conservative: some lattice-based schemes use the Core-SVP model in which C BKZ-β = 2 0.265β (resp. 2 0.292β ) for quantum (resp. classical) setting. For a fair comparison, we shall also show the required blocksize β along with the estimated cost.

Primal attack

The primal attack consists of constructing a uSVP (unique-SVP) instance and solving it by lattice reduction. We refer to [3, 2, 1] for details.

For key recovery, the uSVP instance is

qI n M n (h) I n ∈ Z 2n×2n where M n (h) is
the matrix form of the public key h. The secret key pair g f is a short vector of the uSVP instance. To optimize the primal attack, one can reduce the instance dimension by "forgetting" some equations and take homogeneousness into account.

For message recovery, it suffices to recover s from

c 1 = (hs mod q) k . Let c = k • c 1 , then c = hs -k hs k -(hs mod q) k := hs + e mod q.
We construct the uSVP instance as

  qI n -M n (h) coef (c) I n 1   ∈ Z (2n+1)×(2n+1) that contains   e s 1
  as a short vector. Unlike the case of key recovery, the unknowns s and e have different distributions. Therefore, the primal attack can be improved by re-scaling technique. Also, the strategy of "forgetting" some equations still works here. The primal attack with all above optimizations is systematically discussed in [START_REF] Dachman-Soled | Lwe with side information: Attacks and concrete security estimation[END_REF]. We estimate the cost of primal attack with the open-source script5 of [START_REF] Dachman-Soled | Lwe with side information: Attacks and concrete security estimation[END_REF]. Numbers are shown in Table 5.

Hybrid attack

The hybrid attack was first proposed to cryptanalyze NTRU [START_REF] Howgrave-Graham | A hybrid lattice-reduction and meet-in-the-middle attack against ntru[END_REF]. Later, the hybrid attack is adapted to solving uSVP instances and then analyzed taking quantum speedups into account [START_REF] Buchmann | On the hardness of LWE with binary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack[END_REF][START_REF] Göpfert | A hybrid lattice basis reduction and quantum search attack on LWE[END_REF][START_REF] Wunderer | On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks[END_REF].

To estimate the hybrid attack, we first construct the uSVP instance as Section 5.3.2 as per key recovery and message recovery. The hybrid attack solves a uSVP instance B C I r ∈ Z d×d as follows. Let v l v g be the short vector of the uSVP instance. First, it guesses the last r coefficients v g . Next, it solves a BDD instance of (B, Cv g ) by lattice reduction and obtains the first (d -r) coefficients v l . For each (v g , v l ), it labels v g with some addressed determined by v l . After collecting many such v g 's, it finds a collision, that is (v g , v g ) at one same address, which implies a uSVP solution with some probability. We estimate the cost of the hybrid attack with the open-source script6 by Thomas Wunderer. Our estimate is based on the hybrid attack with quantum speedups. Numbers are shown in Table 5.

Implementation Details

We implemented BAT with integer-only computations. We provide here some details on the used implementation techniques.

Key pair generation

Key pair generation starts with producing the short polynomials f and g, then solving the NTRU equation to obtain F and G. This specific step uses the algorithm described in [START_REF] Pornin | More efficient algorithms for the NTRU key generation using the field norm[END_REF]. Compared with the reference implementation of Falcon, the following differences are noteworthy:

-BAT polynomials have a lower norm than their Falcon equivalent. The polynomial resultants obtained at the deepest level of the recursive algorithm are then shorter, which improves performance.

-All uses of floating-point operations (for Babai's nearest-plane algorithm) have been replaced with fixed-point values (over 64 bits, with 32 fractional bits), which removes all dependencies on the floating-point unit. Since fixed-point values have a limited range, this implies that the reduction may fail, leading to a key pair generation restart. Failed cases can be efficiently filtered out early in the process by checking the current partial solution to the NTRU equation modulo a small prime integer; hence, the overhead implied by these restarts is low. At degree n = 512, about 30% of candidate (f, g) pairs lead to a restart.

-Some memory reorganization allowed for additional RAM savings, down to 12288 and 24576 bytes for n = 512 and 1024, respectively (compared to 14336 and 28672 bytes for Falcon).

Once the complete NTRU basis (f, g, F, G) has been obtained, ComputeVec is used to obtain w. The polynomials γ 2 F f + Gg and γ 2 f f + gg are first computed modulo a small prime where NTT can be applied for efficient computations (a 31-bit prime is used; since the basis coefficients are all small, it is easily seen that coefficients do not exceed 2 19 in absolute value). The v polynomial is then obtained by performing the division in the FFT domain, using the same fixed-point code as the one used for solving the NTRU equation. The division itself is performed with a constant-time bit-by-bit routine.

Since fixed-point values are approximations of the real coefficients of v, the rounding step may occasionally be wrong by 1. Extensive tests show that it is a relatively uncommon occurrence (it happens in about 0.5% of keys at n = 512) and always when v is close to z + 1/2 for some integer z; over 30000 random key pairs, the largest observed deviation of v -1/2 from the closest integer, for coefficients where our implementation rounds to w incorrectly, is lower than 2 × 10 -4 . This means that in all observed cases, |w i -v i | < 1/2 + 2 × 10 -4 . Since the decoding process works as long as |w i -v i | < 1, the impact on the decryption failure rate is negligible.

Field operations

Efficient and secure (constant-time) operations in the small base fields (modulo q and q ) are implemented with Montgomery multiplication. Namely, a value x modulo q is represented by an integer y in the 1 to q range (inclusive), such that y = 2 32 x mod q. Montgomery reduction can be implemented in two 16-bit multiplications, two shifts and one addition; they can moreover be mutualized because analysis shows that reduction works properly for values up to close to 2 32 . For details on this technique, see [START_REF] Pornin | Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions[END_REF].

On recent x86 platforms, SIMD opcodes can be used to further optimize operations. AVX2 registers can store 16 values modulo q (or q ) and perform 16 Montgomery reductions in parallel. The _mm256_mullo_epi16() and _mm256_mulhi_epu16() intrinsics compute, respectively, the low and high halves of a 16-bit product, with a very low reciprocal throughput (0.5 cycles). Computing 16 modular multiplications in parallel requires in total only 6 invocations of such intrinsics.

NTT multiplication

Since q -1 and q -1 are multiples of 256 for BAT, the NTT can be applied to speed up computations over polynomials modulo X n + 1, when working with integers modulo either q or q . For n a power of two up to 27 = 128, the NTT representation of a polynomial f is the set of f (ζ 2i+1 ) for 0 ≤ i ≤ n -1, where ζ is a primitive 2n-th root of 1 modulo q (or q ). In NTT representation, addition and multiplication of polynomials can be done coefficient-wise, hence with cost O(n) operations modulo q. Moreover, conversion to and from NTT representation can be done in O(n log n) steps.

For larger degrees, we cannot use full NTT representation, but we can still optimize operations by splitting polynomials as follows. Consider n = 512; the polynomial f modulo X 512 + 1 can be split into four sub-polynomials as follows:

f = f 0 (X 4 ) + Xf 1 (X 4 ) + X 2 f 2 (X 4 ) + X 3 f 3 (X 4 )
the polynomials f i being of degree up to 127, and operating modulo X 128 + 1. Then, operations on such polynomials can be expressed as a relatively small number of operations on the sub-polynomials, which themselves can be implemented in the NTT domain, since the sub-polynomials are of degree less than 128.

In our implementation, the NTT representations of the sub-polynomials are interleaved, so as to maximize parallelization efficiency.

Polynomial splitting and Karatsuba multiplication

For LW-BAT, we use q = 128, which prevents us from using the NTT straightforwardly 7 . Instead, for polynomial multiplications, we use Karatsuba with an even/odd split, by writing a polynomial f as:

f = f 0 (X 2 ) + Xf 1 (X 2 )
with f 0 and f 1 being half-size polynomials (they operate modulo X n/2 + 1). We can then express the product of f and g as:

f g = (f 0 g 0 )(X 2 ) + X 2 (f 1 g 1 )(X 2 ) + X((f 0 + f 1 )(g 0 + g 1 ) -f 0 g 0 -f 1 g 1 )(X 2 )
i.e. we turn the multiplication of two polynomials modulo X n + 1 into three multiplications of polynomials modulo X n/2 + 1. We use this reduction recursively, until polynomials have degree less than 4.

The same split is used to compute polynomial divisions modulo X n + 1: this is used to compute the public key h = g/f mod q, and also to rebuild G from f , g and F when the short format for private key storaged was used. The even-odd split allows us to write:

1 f = f 0 (X 2 ) -Xf 1 (X 2 ) (f 0 (X 2 ) + Xf 1 (X 2 ))(f 0 (X 2 ) -Xf 1 (X 2 )) = f 0 (X 2 ) -Xf 1 (X 2 ) (f 2 0 + Xf 2 1 )(X 2
) which reduces inversion modulo X n + 1 to a multiplication (modulo X n + 1) and an inversion modulo X n/2 + 1. Applied recursively, this method leads us to the simple problem of inverting an integer modulo q = 128, which can be done in a few inexpensive multiplications.

Decoding

Decoding involves computing polynomials with integer coefficients modulo q, q and Q. The final step requires solving for e and s ; we only need s in practice, since we can use encapsulation to verify the result. Moreover, there are only two possible values for each coefficient of s (for 1/2 and -1/2) and we merely need to disambiguate between these two values. To keep to integer values, we do not recover s but qq Qs ; moreover, we perform computations modulo an additional small prime distinct from q and q . In practice, when q = 257, we perform the last step by working modulo 769; when q = 128 or 769, we use computations modulo 257.

Encoding and storage

We defined compact encoding formats for public keys, private keys, and ciphertexts. Each format starts with a single header byte which identifies the object type and parameter set.

Public keys are polynomials with coefficients modulo q. When q = 257, we encode coefficients by groups of eight, each group using 65 bits: each coefficient is split into a low half (4 bits) and a high half (value 0 to 16, inclusive); eight "high halves" are encoded over 33 bits in base 17. For q = 769, a similar mechanism is used, with 5 coefficients being encoded over 48 bits. All encoding and decoding operations can be implemented with only simple 32-bit multiplications, and can be done efficiently in a constant-time manner (this last property does not nominally matter for public keys, which are public).

Ciphertexts are mainly polynomials with small, signed integer coefficients. When q = 257, coefficients of c 1 are in the -64 to +64 range; eight coefficients are encoded over 57 bits, in a way similar to public key encoding. For q = 769, coefficients of c are in the -96 to +96 range, and five coefficients are encoded over 38 bits in base 193. The value c 2 , which is a fixed-size binary value, is simply appended to the encoding of c 1 .

Private keys have a "short" and a "long" formats. The long format includes the 32-byte seed that was used to generate f , g, and the 32-byte value r (which is used when decapsulation fails). This seed is followed by a copy of r, then the polynomials f , g, F , G and w themselves, and the public key h. Coefficients of f and g are encoded over 4 bits each, in two's complement notation; for F and G, 6 bits are used per coefficient, and 17 bits for w. The public key h uses the same encoding as in the public key. The short format only stores the 32-byte seed, and the polynomial F : the value r and the polynomials f and g are regenerated with the same pseudorandom (deterministic) process that was used during key pair generation; G is recomputed using the NTRU equation (modulo q); and w and h are recomputed. While the short format is substantially shorter, decoding a private key stored in the short format has a nonnegligible overhead, but is still much cheaper than key pair generation, since the most expensive part (solving the NTRU equation from f and g alone) is avoided.

The numbers for required storages are listed in Table 6.

A Proofs of Theorem 1

To prove Theorem 1, we need Lemma 1 to estimate the norm of the involved vectors.

Lemma 1. Let R = Z[x]/(x n + 1) with n a power-of-2. Let f, g ∈ R be iid-random over D Z,σ f , B f,g = g G f F ∈ R 2×2 be an NTRU basis. Let v = γ 2 F f +Gg γ 2 f f +gg with γ > 0. Let (G ⊥ , F ⊥ ) = (G -gv, γF -γf v) and (G , F ) = (G -g v q , F -f v q ). Let I(γ) = 2 ln(γ) ) for any f ∈ K n . Some routine computation yields that

(G ⊥ , F ⊥ ) 2 = q 2 γ 2 n n i=1 1 γ 2 f (ξ 2i-1 n )f (ξ 2i-1 n ) + g(ξ 2i-1 n )g(ξ 2i-1 n ) .

B Changes with respect to Last Submission

In the following we list the changes we made as per the reviews on our last submission "TCHES 2021, issue2 Paper #22".

Editorial quality. First we added more connections between sections and explained why some presented results are relevant for this paper. To improve the paper's organization, security arguments and implementation details have been split into two sections. Secondly, some missing references and backgrounds on Falcon have been added. Thirdly, we included "Comparison with Falcon" and an intuitive explanation of why BAT achieves smaller parameters in Section 1, which may help readers to better understand our work. Finally, we proofread the whole paper and clarify the variables and terms before they are used.

Changed algorithms and parameters. The encryption (Algorithm 4.2) was modified: the new encryption is IND-CPA secure rather than OW-CPA as the old one. This modification leads to a simpler security proof while increasing a little the cost on the ciphertext size. Also we refined the key generation as per Section 3: the trapdoor of the updated BAT does not always satisfy (f, g) ≈ (F * , G * ) , which is different from Falcon. This improves the decryption failure rate. All parameters were changed accordingly.

Decryption failure. To reduce the decryption failure rate, we increased q to 64513 and modified the key generation (explained above). In the previous submission, our estimate of decryption failure was heuristic (Theorem 1). In the updated version, we also presented exact values computed for actual secret keys: exact values are even smaller than heuristic ones. Detailed numbers and explanations were shown in Section 4.2.

Security arguments.

All security arguments including the assumptions, the security proof and the concrete security estimates are now in Section 5. Some references were added after each used assumption to show why it is assumed to hold. We gave a formal security proof of CPA security and followed the updated results of FO transformation. The modifications on concrete security estimates are significant including 1. more details about considered attacks and their relevance to the used assumptions, 2. costing hybrid attacks, and 3. re-estimates made by open-source scripts of the state-of-the-art works.

Implementation and benchmarking.

We explained more about the fixed-point approximation in Section 6.1. We also compared with SIKE and compressed SIKE in Table 2 as suggested by Review A. Yet we did not report the full timings including random generation, hashing and encoding/decoding, as we explained in the rebuttal. Again, the costs of random generation, hashing and encoding/decoding are not included in the timings of other algorithms in Table 2, even though these operations are more costly than the core process that we measured. Moreover, we cannot provide them for the other schemes.

3 4 :

 4 if (γs, e) > 1.08 n(k 2 -1)

3 4 : 7 :

 47 if (γs, e) > 1.08 n(k 2 -1) if c 1 = (hs mod q)

γ 2 - 1 for γ = 1

 11 and I(1) = 1. Then -(G ⊥ , F ⊥ ) ≈ qγ √ n•σ f I(γ); -(G , γF ) ≤ qγ √ n•σ f I(γ) + n 1.5 √ γ 2 +1 2q σ f . Proof. First, it can be verified that (G ⊥ , F ⊥ ) = qγ -γf γ 2 f f +gg , g γ 2 f f +gg . Let ξ n be a 2n-th primitive root of 1, then f 2 = 1

Table 1 :

 1 The parameter restrictions for correct decryption. The parameter τ is the tail-bound parameter determining the decryption failure rate.

		Requirement for correct decryption
	NTRU Ring-LWE BAT	τ σ e σ f (p 2 + 1)n < q 2 τ σ e σ f √ 2n < q 4 τ σ e σ f √ 2n < q

Table 3 :

 3 Suggested parameters for BAT.

	Security	n	(b, k, q)	σ f	q	τ	Decryption Failure
	128 bits	512	(128, 2, 257)	0.596	64513	9.46	2 -146.7
	256 bits	1024	(192, 4, 769)	0.659	64513	10.42	2 -166.7

Table 4 :

 4 Suggested parameters for LW-BAT.

	Security	n	(b, k, q)	σ f	q	τ	Decryption Failure
	80 bits	256	(64, 2, 128)	0.595	64513	6.71	2 -71.9

Table 5 :

 5 Concrete security estimate for BAT. The item "A/B" denotes the attack cost A and the required BKZ blocksize B. The item "A" denotes the attack cost A.

	Security	Key Recovery primal hybrid	Message Recovery primal hybrid
	80 bits	87.8 / 236	90.3	83.3 / 219	79.5
	128 bits	152.1 / 475	164.1	144.6 / 447	140.1
	256 bits	274.4 / 933	314.4	278.6 / 949	275.7

Table 6 :

 6 The required storage of BAT (full format, including the header byte).

	Security	Public Key	Ciphertext	Private key	Secret Key
		(bytes)	(with FO, bytes)	(short, bytes)	(long, bytes)
	80 bits	225	203	225	1473
	128 bits	521	473	417	2953
	256 bits	1230	1006	801	6030

https://en.wikipedia.org/wiki/Maximum_transmission_unit and Distributions on IP packets.

BAT stands for "Basis with Attractive Trapdoor".

The actual distribution is within statistical distance 1/q of U (Z n k ).

The specific definitions of δ and η are given in[START_REF] Bindel | Tighter proofs of cca security in the quantum random oracle model[END_REF].

https://github.com/lducas/leaky-LWE-Estimator

https://github.com/lducas/LatRedHybrid

A very recent work[START_REF] Chung | NTT Multiplication for NTT-unfriendly Rings[END_REF] shows that by introducing an extra prime p such that p > nq 2 /2 and p = 1 mod 2n, one can implement the multiplication over Rq with NTT over Rp.

Acknowledgements

This work was partly supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701). Paul Kirchner is partly funded by the Direction Générale de l'Armement (Pôle de Recherche CYBER). This work is also partly supported by the National Natural Science Foundation of China (No. 62102216), the National Key Research and Development Program of China (Grant No. 2018YFA0704701), the Major Program of Guangdong Basic and Applied Research (Grant No. 2019B030302008) and Major Scientific and Technological Innovation Project of Shandong Province, China (Grant No. 2019JZZY010133).

Proof. We prove via a sequence of games. Let Pr[W i ] denote the probability of the adversary winning Game i.

Game 0 is the classical bit-guessing version of the IND-CPA security game, thus Pr[W 0 ] = 1 2 + Adv IND-CPA Π (A). The challenger in Game 0 proceeds as follows: Initialization:

(1) (pk = h, sk) ← KeyGen Enc () (2) s ← U (R mod 2); c 1 ← (hs mod q) k initialize an empty associative array M ap : R mod 2

Game 1 and Game 0 only differ in the generation of pk: line (1) in Game 0 is replaced by "pk = h ← U (R × q )". We define A 1 for the decision NTRU problem. Upon input h ∈ R × q , A 1 plays the challenger in Game 0 except for setting pk = h in line [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes![END_REF]. Then it is easy to see that

Game 2 is precisely the same as Game 1, except that we delete line [START_REF] Avanzi | CRYSTALS-Kyber[END_REF]. Let E be the event that the adversary queries the random oracle at the point s in Game 2. Clearly, Game 1 and Game 2 proceed identically unless E occurs. Therefore,

If E happens, then one of the random oracle queries made by the adversary is s such that c 1 = (hs mod q) k , which gives a solution to the search Ring-LWR problem with input (h, c 1 ). Precisely, we define A 2 for the search Ring-LWR problem. Upon input (h, c), A 2 plays the challenger in Game 2 except for setting pk = h and c 1 = c. Additionally, when A 2 terminates, if there is some s ∈ Domain(M ap) such that c = (hs mod q) k , then A 2 outputs s otherwise outputs "failure". By definition, E happens if and only if s ∈ Domain(M ap), then we have

In Game 2, v is uniformly random drawn from M and independent of other intermediate variables. Therefore, (m 0 , m 1 ) is completely indistinguishable, i.e. Pr[W 2 ] = 1 2 . It immediately follows that

The BAT KEM is obtained via applying a tweaked Fujisaki-Okamoto transform [START_REF] Bindel | Tighter proofs of cca security in the quantum random oracle model[END_REF][START_REF] Kuchta | Measure-rewind-measure: Tighter quantum random oracle model proofs for one-way to hiding and cca security[END_REF] to the IND-CPA secure encryption. Theorem 3 gives the concrete security statement of the IND-CCA security of BAT when Hash m , Hash s and Hash k are modeled as quantum random oracles.

Speed benchmarks

We provide two implementations -(1) plain portable C version and (2) AVX2 version. We measured the speed on an Intel i5-8259U CPU clocked at 2.3 GHz; TurboBoost is disabled. Compiler is Clang-10.0, with optimization flags "-O3". The AVX2 implementation uses intrinsic functions, and an additional optimization flag "-march=native". For key pair generation, reported value is an average over several hundreds of key pairs (by nature, that process takes a varying time, since each candidate (f, g) may or may not lead to a successful key pair generation; it is still "constant-time" in that timing variations are independent of the value of the private key which is ultimately generated). For encapsulation and decapsulation, reported value is the core process, without random generation (from the operating system), hashing to derive the shared secret, and encoding/decoding costs; on the test system, these extra operations add up to about 20k extra cycles.

The timing data for two implementations are illustrated in Tables 7 and8 respectively. We heuristically model all these f (ξ 2i-1

) as independent random variables drawn from the chi-square distribution of parameter k = 2 scaled by

Further, we get the following approximation

This completes the proof.

Remark 4. When γ = 1, our estimation of (G ⊥ , F ⊥ ) is q √ n•σ f . This implies that for optimal trapdoor, σ f should be 4 √ 2 q 2n ≈ 1.19 q 2n slightly larger than the previous heuristic bound 1.17 q 2n suggested in [START_REF] Ducas | Efficient Identity-Based Encryption over NTRU Lattices[END_REF]. The explanation of the factor 1.17 is given in [START_REF] Prest | Gaussian Sampling in Lattice-Based Cryptography[END_REF]: the argument makes use of the projection heuristic on both (g, f ) and (G, F ) two parts. In fact, this explanation seems problematic: as B f,g is symplectic, once the Gram-Schmidt norms of the (f, g) part are fixed, those of the (G, F ) part are determined as well. Thus, the optimal bound for the Gram-Schmidt norm of B f,g is entirely determined

it follows that c = Q(gs + f e ) and c = Q(F d e + G d s ), which ensures a correct decoding similar to the RO algorithm.

Let T 1 = f e + gs and T 2 = F d q e + G d q s . We approximate T 1 , T 2 by two random Gaussian vectors of standard deviations σ T1 = √ nσ f σ s γ 2 + 1 = σ 1 and σ T2 = σs q (G d , γF d ) . By Lemma 1, we have σ T2 ≤ σ 2 and then τ ≤ min

. Therefore, the probability of correct decoding is at least 1 -2n • (1 -erf(τ )).