Charbel Saliba

My most sincere gratitude goes to my supervisor Dr. Laura Luzzi, who, through her intellectual rigor, her always relevant comments, her knowledge of the subject and methodological aspects

Context and motivation

Nowadays, many of our daily activities are dependent on the web, so various forms of communication, entertainment, finance and work related tasks are handled online. Personal and financial information is highly desirable for cyber attackers. An attacker can passively observe the transmitted data without making any changes so that the victim is not aware of the eavesdropper's presence. Furthermore, an attacker can modify or damage data in order to confuse and harm victims. This is why it is crucial to protect our devices against these malicious activities of attackers.

Cryptography is the basic technology used to ensure the privacy and security of data as it travels over the Internet. It takes advantage of mathematical problems that are thought to be computationally difficult to solve in order to design algorithms that ensure security and reliability. Most of these cryptographic algorithms fit into one of two classifications: symmetric and asymmetric. Symmetric protocols are mostly used to encrypt and decrypt data using a shared private key, and they are usually much faster than asymmetric algorithms. The most popular example of symmetric cryptography algorithms is the Advanced Encryption Standard (AES). Asymmetric cryptography (or Public-key cryptography) relies on two pairs of keys: the first is a public key that can be revealed to the public, and the second key, called a secret key, must be kept secret and unknown to others. Applications of asymmetric cryptography involve encryption protocols, digital signatures, key establishment schemes and many other use cases. Examples of asymmetric algorithms include RSA, ElGamal, Diffie-Hellman and ECC (elliptic-curve cryptography). Breaking such schemes involves solving difficult problems like prime factorization and discrete logarithm in polynomial time, which has so far been impractical on classical computers.

Post-quantum Cryptography

In recent years, research on quantum computing has seen significant progress. These machines will be capable of solving mathematical problems that were thought to be intractable for conventional computers, and therefore of breaking many existing public key cryptosystems currently in use. In fact, Shor [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF] proposed a polynomial time quantum algorithm for the integer factorization problem which can be adapted into an efficient quantum algorithm to solve the discrete logarithm problem [START_REF] Jozsa | Quantum factoring, discrete logarithms, and the hidden subgroup problem[END_REF]. This poses a real threat to almost all existing public key cryptosystems.

Another important quantum algorithm that needs to be mentioned is Grover's algorithm. It provides a quadratic speedup compared to classical solutions [START_REF] Lov | A fast quantum mechanical algorithm for database search[END_REF], allowing faster brute force attacks on a wide range of unstructured search problems, including searching for a symmetric key and finding pre-images of hash functions. For instance, a 128-bit symmetric private key can be cracked within 2 64 iterations, and therefore, this kind of attack can be prevented by doubling the size of the private key.

Consequently, there is a pressing need to develop new cryptographic systems that are secure against quantum attacks. Post-quantum cryptography offers solid alternatives for cryptographic systems that ensure security against quantum and classical computers.

The NIST post-quantum cryptography challenge

Over the past few years, many organizations have started researching public-key cryptographic algorithms that might be candidates for a new standardization process. In December 2016, the U.S. National Institute of Standards and Technology (NIST) launched a challenge to collect quantum-resistant algorithms covering public-key encryption schemes, key-establishment protocols and digital signature methods. In July 2020, NIST selected for its third round seven algorithms to be shortlisted for the standardization process, while keeping eight algorithms aside as alternate candidates in case security concerns arise (see Table 1.1).

Signatures KEM/Encryption Overall

Lattice Most of them are built using lattice-based and code-based cryptography, while few others use multivariate equations hash functions, and isogenies of elliptical curves. Seven of these schemes rely on lattice cryptography constructions and are among the leading candidates for public-key post-quantum cryptography.

Lattice-based cryptography

Lattice-based cryptography is one of the most promising candidates for post-quantum cryptography because it enjoys strong theoretical security guarantees and is effective in practice. It allows the construction of various cryptographic schemes such as public-key encryption schemes, key encapsulation mechanisms, digital signatures, hash functions, fully homomorphic encryption and much more, while ensuring security reductions to computational problems which are considered hard to break even on quantum computers.

Computationally hard lattice problems

The most important problem that is involved in such constructions is the shortest vector problem (SVP) for which the γ-approximation version (SVP γ ) is intensively study. A large family of SVP γ variants follows such as the decision shortest vector problem (GapSVP γ ), unique shortest vector problem (unique-SVP γ ), the closest vector problem (CVP γ ) and the bounded distance decoding (BDD γ ) [START_REF] Micciancio | Complexity of lattice problems: a cryptographic perspective[END_REF].

These lattice problems are easy to solve once one chooses a "good" basis, that is, a nearly orthogonal basis with relatively short vectors. Lattice reduction algorithms seek to produce such a good basis when the input is an arbitrary basis for a lattice. An early efficient algorithm which can output an almost reduced lattice basis is the LLL algorithm presented in [START_REF] Arjen K Lenstra | Factoring polynomials with rational coefficients[END_REF], adapted by Lenstra, Lenstra, and Lovász in 1982. This algorithm has several applications such as factoring polynomials over the rational numbers [START_REF] Arjen K Lenstra | Factoring polynomials with rational coefficients[END_REF], integer programming [START_REF] Kannan | Improved algorithms for integer programming and related lattice problems[END_REF] and many other applications in cryptanalysis. Moreover, it runs in polynomial time and approximates the shortest vector inside an n-dimensional lattice within a factor of 2 O(n) . Solving SVP γ within a constant approximation factor, or even within a factor n c/ log log n for some c > 0 is conjectured to be hard [START_REF] Micciancio | The shortest vector in a lattice is hard to approximate to within some constant[END_REF][START_REF] Khot | Hardness of approximating the shortest vector problem in lattices[END_REF][START_REF] Haviv | Tensor-based hardness of the shortest vector problem to within almost polynomial factors[END_REF], and there's no polynomial time algorithm capable of doing it.

The best known algorithm for solving SVP has a provable running time of 2 O(n) [START_REF] Ajtai | A sieve algorithm for the shortest lattice vector problem[END_REF], and several improvements are found in [NV08, PS09, MV10, ADRSD15, ASD17] that led to 2 n+o (n) time and space algorithms. In terms of space-time trade-off, the best current known result was

given in [START_REF] Aggarwal | Improved (provable) algorithms for the shortest vector problem via bounded distance decoding[END_REF] and solves SVP in 2 1.740n+o(n) time and 2 0.5n+o(n) space.

A question that arises is whether these families of problems remain difficult for quantum computers. So far, the most plausible quantum algorithm (that is also the fastest classical algorithm for SVP) is given in [START_REF] Aggarwal | Solving the shortest vector problem in 2 n time using discrete gaussian sampling[END_REF] and requires 2 n+o(n) time and space. An improvement from the quantum side was proposed in [START_REF] Aggarwal | Improved (provable) algorithms for the shortest vector problem via bounded distance decoding[END_REF] that solves SVP in 2 0.9533n+o(n) time and classical 2 0.5n+o(n) space. Heuristically, the best known result in [START_REF] Laarhoven | Search problems in cryptography: From fingerprinting to lattice sieving[END_REF] can solve SVP within 2 0.265n+o(n) times and space. Quite recently, there is also a new heuristic quantum algorithm by "random walk" [START_REF] Chailloux | Lattice sieving via quantum random walks[END_REF] which achieves 2 0.257n+o(n) by relying on exp(n) many quantum bits (instead of poly(n) quantum bits in [START_REF] Laarhoven | Search problems in cryptography: From fingerprinting to lattice sieving[END_REF]). This algorithm is far from being realistic due to the need of a large amount of q-bits. That's why it is believed that it is hard to construct a polynomial time quantum algorithm that approximates lattice problems to within polynomial factors. This justifies the use of lattice-based cryptosystems for post-quantum cryptography.

Worst-case to average-case reduction

A significant advantage of lattice-based cryptography compared to other cryptographic techniques is that the security of most lattice-based cryptographic primitives is based on the worstcase hardness of lattice problems. In cryptography a problem is considered to be hard only if it is hard in the average-case, i.e. it is hard for all but a negligible fraction of instances, whereas in complexity theory, hardness is described in terms of worst-case hardness, which means that it is difficult to solve the problem for some given instance, even though a large collection of instances might be easy to solve. In 1996, a breakthrough paper by Ajtai [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF] showed that solving SVP on a random lattice on average according to a certain distribution which is easy to sample, involves a solution for the approximate SVP for any lattice within a polynomial approximation factor n c . This connection illustrates the worst-case to average-case reduction. It shows that if the second mentioned problem is hard in some (worst) cases, then the first problem is also hard on average. Based on this concept, many cryptographic primitives were constructed such as Ajtai's one way function [START_REF] Ajtai | Generating hard instances of lattice problems[END_REF] and collision resistant hash functions [START_REF] Goldreich | Collision-free hashing from lattice problems[END_REF] illustrating the role of lattices in building cryptographic functions that are as difficult to break as the worst-case scenario of certain lattice problems.

Learning With Errors

A very versatile lattice primitive called Learning With Errors (LWE) was introduced by Regev in 2009 [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. The LWE problem guarantees a worst-case reduction from the shortest independent vector problem (SIVP) and the decision version of the shortest vector problem (GapSVP)

for reasonable approximation factors in generic lattices. Therefore, it can be used to build

Ring-LWE and Module-LWE

A structured variant of LWE, the decision Ring Learning With Errors (R-LWE) was proposed in [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] by Lyubashevsky et al. to allow more compact representations and shorter public and secret keys. It consists in distinguishing polynomially many samples (a i , a i • s + e i ) ∈ R q × R q from uniform samples (a i , b i ) ∈ R q × R q , where R is taken to be the ring of integers of some cyclotomic number field, i.e., the field K = Q(ζ N ) with ζ N being any primitive N -th complex root of unity. Note that each a i is generated uniformly from R q , whereas e i and s are generated from a well defined distribution on R.

Solving R-LWE was shown to be at least as hard as solving approximate SIVP on ideal lattices, a special class of lattices generated from fractional ideals in the underlying field. Based on this hardness, many cryptographic applications were proposed including efficient signature schemes [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF][START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF], fast encryption [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF], fast homomorphic encryption [GHS12, [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Brakerski | Fully homomorphic encryption from ring-lwe and security for key dependent messages[END_REF] and pseudo-random functions [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF].

The R-LWE problem inspired the authors of [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF] to introduce the Module Learning With Errors (M -LWE) variant. This new generalized form seems to offer better security guarantees and more flexibility in designing cryptographic schemes. Mathematically speaking, the problem consists in distinguishing uniform samples (

#» a i , b i ) ← R d q × R q from samples ( #» a i , b i ) ← R d q × R q where #» a i ← R d q is uniform, b i = #» a i , #» s + e i
with a fresh e i generated from a well defined distribution Ψ on R q , and #» s ← Ψ d . Similar to its former counterparts, M -LWE also enjoys worst-case to average-case reductions from lattice problems such as Mod-GapSVP γ and Mod-SIVP γ that are conjectured to be hard to solve on module-lattices, i.e., lattices corresponding to modules over the ring R, for γ polynomial in the lattice dimension. Note that Mod-GapSVP γ is easy for module rank equals 1, and conjectured to be hard when the rank is at least 2. The Module-LWE problem is attractive for cryptographic cryptosystems as it offers a trade-off between concrete security and efficiency depending on the dimension d.

Key encapsulation mechanisms (KEMs) based on LWE and its variants

The LWE problem, as well as its variants, have various applications in cryptographic systems and protocols due to their flexibility and efficiency. A great number of schemes have been proposed in the literature and it would be outside the scope of this thesis to illustrate all known applications. We will focus on two schemes that were submitted to the NIST challenge.

FrodoKEM A key encapsulation mechanism called FrodoKEM [N + 20], which is based on the LWE problem, has been selected as an alternate candidate for the third round of the challenge.

The core of FrodoKEM is a public-key encryption scheme called FrodoPKE which uses the method from Regev's LWE encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] in order to encrypt multiple bits at a time. This scheme benefits from IND-CPA security. FrodoKEM is built from FrodoPKE by applying the Fujisaki-Okamoto transformation [START_REF] Hofheinz | A modular analysis of the Fujisaki-Okamoto transformation[END_REF] in order to obtain IND-CCA security for the resulting key encapsulation mechanism.

KyberKEM

Error-correction and reconciliation for noisy Diffie-Hellman

As mentioned above, many cryptographic schemes are based on LWE and its variants. In order to motivate the sequel of this thesis, we give explicit examples of such constructions. We present a common setting for LWE-based key encapsulation mechanisms (KEM) in Table 1.2. Parameters: m, n, q and error distribution χ on Z q Alice (Server) Bob (Client) We consider two terminals, Alice and Bob (Server and Client), whose aim is to generate the same private key on both sides. For concreteness we fix the set Z m×n q for integers m, n, together with a modulus integer q. Alice chooses a uniformly random matrix A ∈ Z m×n q as well as two random 'small' error matrices S, E such that each component is generated from the Gaussianlike error distribution χ, and sends the LWE sample pair (A, B) as a public key to Bob. Bob on his side generates S , E and E and computes the LWE samples U = S A + E mod q, V = S B + E mod q.

A $ ← -Z m×n q S $ ← -χ m×m , E $ ← -χ m×n S $ ← -χ n×n , E $ ← -χ m×n E $ ← -χ m×n B = AS + E ∈ Z m×n q (A,B) ----→ m $ ← -{0, 1} U ← - U = S A + E V = US V = S B + E
The term U is sent back to Alice who uses it to calculate V = US with her secret key S. Note that V -V = S E + E -E S mod q.

(1.1)

When the distribution χ is chosen appropriately, the term (S E + E -E S) is small with high probability, and therefore the values V and V are close to S AS. This observation is the basis of lattice-based encryption schemes and key encapsulation mechanisms.

The structure of the protocol brings to mind the Diffie-Hellman protocol [START_REF] Diffie | New directions in cryptography[END_REF] where the public parameter A ∈ Z m×n q corresponds to the generator g and the noise-free product is analogous to exponentiation. The presence of noise due to error terms leads to what we call Noisy Diffie-Hellman protocols. The term "Noisy Diffie-Hellman" was first used in a talk by P.

Gaborit at PQCrypto 2010 [AGL + 10b, AGL + 10a] and also described in [START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF]. In this kind of protocols, if the random noise terms are large, an error will occur during the recovery of the private key, affecting the reliability of the scheme. As a result, it is necessary to choose the error distribution in such a way that the failure probability is guaranteed to be exponentially small.

As mentioned previously, thanks to the Fujisaki-Okamoto transform, one can transform an IND-CPA secure public-key encryption scheme into an IND-CCA secure key encapsulation mechanism. However, and especially when working in lattice-based cryptosystems, having small error probability is important not only for reliability, but also for security when going from IND-CPA to IND-CCA. For instance, an insufficiently small error probability can cause a leakage of information due to decryption failure attacks [DGJ + 19] where a failure boosting technique is used to increase the failure rate. To keep the error probability small, one can use either error correction or reconciliation approaches. These techniques make it possible to agree on an exact shared private key (instead of an approximation) by providing Bob with some additional information.

Encryption-based approach. This first approach is used in many LWE-based encryption schemes, such as [LP11, N + 20, A + 20]. Table 1.3 illustrates this approach.

Parameters: m, n, m, n, q and error distribution χ on Z q Alice (Server) Bob (Client)

A $ ← -Z m×n q S $ ← -χ m×m , E $ ← -χ m×n S $ ← -χ n×n , E $ ← -χ m×n E $ ← -χ m×n B = AS + E ∈ Z m×n q (A,B) ----→ m $ ← -{0, 1} U = S A + E V = S B + E V = US (U, C) ← ---- C = V + Encode(m) m = Decode(C -V ) Table 1.3: Encryption-based KEM.
As shown, Bob unilaterally generates a uniform message m ∈ {0, 1} and encodes it using some well defined encoding function Encode that maps {0, 1} into Z m×n q . He then sends the cyphertext C = V + Encode(m) to Alice so that she can recover m by applying the decoding function Decode(C -US). Note that in the context of public-key encryption, the encoding function Encode has to be injective so that Alice can recover the original message using Decode.

Reconciliation-based approach. This approach was originally described in [START_REF] Ding | A simple provably secure key exchange scheme based on the learning with errors problem[END_REF]. The reconciliation method allows two parties who have obtained noisy observations to come to an exact agreement about the value of the key, and consists in sending an auxiliary message from Bob to Alice in order to help her recover the private key from her noisy observation. The reconciliation approach in [START_REF] Peikert | Lattice cryptography for the internet[END_REF], with priority to keep a low bandwidth, uses the one dimensional lattice Z in order to agree on one bit of private key. Other papers proposed reconciliation steps using higher-dimensional lattices, for instance [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] considers the four dimensional lattice D4 .

Parameters: m, n, m, n, q and error distribution χ on Z q Alice (Server) Bob (Client) In this setting, Bob and Alice observe two correlated sources X n and Y n respectively. After receiving X n , Bob sends a codeword R to Alice, who uses it together with her observation Y n in order to reconstruct an estimate Xn of X n with respect to a chosen distortion measure.

A $ ← -Z m×n q S $ ← -χ m×m , E $ ← -χ m×n S $ ← -χ n×n , E $ ← -χ m×n E $ ← -χ m×n B = AS + E ∈ Z m×n q (A,B) ----→ U = S A + E V = S B + E V = US (U, R) ← ---- R = HelpRec(V) µ = Rec(V , R) µ = Rec(V, R)
We note that in Table 1.4, V plays the role of X n and V plays the role of Y n , but these observations do not have an i.i.d. distribution.

It is known that for jointly Gaussian sources with mean squared error distortion, the optimal Wyner-Ziv distortion function can be achieved using nested lattice codes [START_REF] Zamir | Nested linear/lattice codes for structured multiterminal binning[END_REF].

Wyner-Ziv reconciliation using lattices has already been used in physical layer security, i.e.

for key generation from Gaussian sources [START_REF] Ling | Secret key generation from gaussian sources using lattice hashing[END_REF]. In this work, the key generation problem was decoupled into two problems: randomness extraction (in order to extract from Bob's signal a private key which is independent from the eavesdropper's observations) and source coding with side information (sent by Bob to help Alice reconstruct the private key from her observation). It was shown that both objectives can be achieved with lattices. In particular, a lattice partition

chain Λ 3 ⊆ Λ 2 ⊆ Λ 1 is used, where
• Λ 1 is good for quantization and serves as the "source-code" component of Wyner-Ziv coding;

• Λ 2 serves as the "channel-code" component in Wyner-Ziv coding;

• Λ 3 is used for randomness extraction.

Based on this, Bob computes the reconciliation message R as

R = Q Λ 1 (V) mod Λ 2
and transmits it to Alice. Furthermore, Bob computes the private key µ as

µ = Q Λ 2 (V, R) mod Λ 3 .
Here, the notations Q Λ and mod Λ indicate the lattice quantization function and modulo lattice operation corresponding to the lattice Λ.

In order to get the optimal rate-distortion function one needs to consider a sequence of lattices whose dimension tends to infinity [START_REF] Zamir | Nested linear/lattice codes for structured multiterminal binning[END_REF]. However, this is not practical for cryptographic applications as the decoding complexity would become too large. Moreover, the result in [START_REF] Ling | Secret key generation from gaussian sources using lattice hashing[END_REF] is based on random lattices, and does not specify how to choose practical lattices in finite dimension.

Impact of error dependencies Developing error correction and reconciliation mechanisms

for lattice-based protocols is a difficult challenge since the target error probability is far beyond the range of numerical simulations, and moreover the components of the error distribution are not independent. Some papers which use error correcting codes to improve the performance [LLZ + 18,L + 19] compute the error probability under an independence assumption which does not hold in practice. However, this has been shown to lead to underestimating the error probability by a very large exponential factor [START_REF] Anvers | The impact of error dependencies on Ring/Mod-LWE/LWR based schemes[END_REF]. In this thesis, we choose instead to derive rigorous error probability bounds following the example of [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]. Evaluating those bounds still requires extensive numerical simulations which become very complex when the coding lattice Λ 2 is high-dimensional.

Contributions and main results

In this work, we aim to improve some of the existing key encapsulation mechanisms proposed for the NIST challenge in terms of security, reliability and bandwidth. One possible method of achieving these improvements is to introduce lattice-based error correction mechanisms or reconciliation techniques that improve performance, as has been done in previous works [START_REF] Peikert | Lattice cryptography for the internet[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF][START_REF] Ah Van Poppelen | Cryptographic decoding of the Leech lattice[END_REF][START_REF] Saliba | A reconciliation approach to key generation based on Module-LWE[END_REF].

Our main inspiration comes from the method of [START_REF] Ling | Secret key generation from gaussian sources using lattice hashing[END_REF], but we focus on reconciliation/error correction using a sublattice Λ 2 of small dimension in order to keep the complexity of the protocol low. This can be seen as an extension of the reconciliation/error correction mechanisms in NewHope [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] and its successor NewHopeSimple [START_REF] Alkim | NewHope without reconciliation[END_REF]. In particular, we look for a lattice that admits low-complexity quantization, and so we choose the Gosset lattice, as well as the small dimensional Barnes-Wall lattices. To go further with our study, we also consider higher dimensional Barnes-Wall lattices which admit an efficient bounded distance decoding algorithm up to half of the minimum distance [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF].

Main results

• We first consider the alternative NIST candidate FrodoKEM [N + 20], which is an LWEbased key encapsulation mechanism, and propose a modification at the level of the encoding function. We define a new encoder which maps the private key block-wise into the 8-dimensional Gosset lattice E 8 . We propose three sets of parameters for our modified implementation. Thanks to the improved error correction, the first implementation allows to reduce the bandwidth by 7% by halving the modulus q; the second outperforms FrodoKEM in terms of plausible security by 10 to 13 bits by increasing the error variance, and the third one aims to increase the key size by approximately 50%. In all cases, our scheme can ensure a smaller decryption failure probability compared to the original FrodoKEM.

• Next, we focus on the KyberKEM protocol [A + 20]. We propose a modification of Ky-berKEM featuring a reconciliation mechanism based on E 8 . Similarly to KyberKEM, our scheme generates 256 bits of key and requires 5 or 6 bits of reconciliation per dimension. We show that it can outperform KyberKEM in terms of the modulus q with comparable error probability and similar requirements in terms of bandwidth. For instance, our construction guarantees a smaller error probability than KyberKEM-768's, i.e.

P e ≤ 2 -174 < 2 -164 , with a smaller modulus q = 2 11 < 3329, using 5 bits of reconciliation per dimension. For this choice of q, our scheme achieves 176 bits of post-quantum security compared to 164 bits. Such improvement can also be applied to KyberKEM-512, but it failed to extend to KyberKEM-1024. Note that unlike KyberKEM, where the modulus q is prime and the Number Theoretic Transform [CT65, LN16, Sei18] is used for fast polynomial multiplication, we choose q to be a power-of-two. In this case, efficient polynomial multiplication is still possible using Karatsuba / Toom-Cook algorithms such as [BCLV17, DWZ18, DKRV18]. Moreover, unlike [START_REF] Peikert | Lattice cryptography for the internet[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF], we don't need dithering anymore to obtain a uniform key thanks to the fact that q is even.

In Appendix D, we investigate the use of Barnes-Wall lattices for reconciliation, but we are not able to improve KyberKEM's performance with this construction.

Organization of the thesis

A brief summary of each chapter is presented below where we highlight the main contributions and the tools used to achieve our results.

proofs of some theorems cited in Chapter 2.

• Chapter 3 -Error correction for FrodoKEM. We recall the LWE problem in Section • Conclusion and Perspectives. This chapter concludes the thesis and provides some perspectives for future improvements. Chapter 2

Publications

Preliminaries

This chapter covers the preliminaries made use of in the next chapters. First, we give some guideline for the notation used in the manuscript. Next we present general background about lattices and study their properties. We give examples that are relevant in our work, along with some computationally hard problems on which we can define. After that, we cover cryptographic definitions around some basic protocols and provide security description. Finally, we recall some Gaussian-like distributions related to our work.

Notation

Throughout this thesis all logarithms are base 2 unless otherwise indicated. ). We write X ∼ Y to denote that two random variables X and Y have the same distribution. For a discrete distribution P , Supp(P )

denotes the support of P , i.e., the set of points where the distribution is not zero. When an element a is taken uniformly at random from a set A we write a $ ← -A, and when it is an output of some function f we write a ← f .

A function (n) is called negligible if for every positive polynomial P , there exist a range N such that for all n ≥ N we have (n)

< 1 P (n) .
We present some common asymptotic notation in Table 2.1 which can be used to describe the running time of algorithms.

Main Notation Asymptotic Behaviour

Limit Definition f ∈ O(g) f ≤ g lim n→∞ f (n)/g(n) < ∞ f ∈ o(g) f < g lim n→∞ f (n)/g(n) = 0 f ∈ Ω(g) f ≥ g lim n→∞ f (n)/g(n) > 0 f ∈ ω(g) f > g lim n→∞ f (n)/g(n) = ∞ f ∈ Θ(g) f = g lim n→∞ f (n)/g(n) ∈ (0; ∞) f ∈ Õ(g) ⇐⇒ f ∈ O g • log k (g) for some integer k

Lattices

In this section we introduce the main definitions about lattices that will be needed in the sequel, and define some well known related computational problems.

Definitions and properties

Before we can proceed to the definitions of a lattice and its properties, it is first necessary to formalize the concept of a discrete subset.

Definition 2.1 (Discrete subset). Let S ⊆ R n . We say that S is discrete if

∀x 0 ∈ S, ∃ ε > 0 : B n (x 0 , ε) ∩ S = {x 0 }.
An n-dimensional lattice is a discrete subset of R n that it is closed under reflection and real addition, namely, it is a discrete subgroup of R n . Mathematically speaking, it can be defined using a set of linearly independent vectors as follows:

Definition 2.2 (Lattice). Let b 1 , b 2 , . . . , b m ∈ R n be a sequence of m linearly independent row 1 vectors (m ≤ n).
The lattice Λ is the set of all integral combinations of these vectors, i.e.,

Λ = m i=1 x i • b i : x i ∈ Z .
The set {b 1 , b 2 , . . . , b m } is called a basis for Λ, and it is not unique. The integer m is its rank and n is its dimension. The lattice is called full-rank if n = m. Throughout this thesis we will only consider full-rank lattices unless otherwise indicated. The norm of the shortest non-zero vector in Λ is denoted by λ 1 (Λ). Similarly, we define the i-th successive minimum for i ≥ 2 as follows (see Figure 2.1):

λ i (Λ) = inf r : Bn (0, r) contains at least i linearly independent lattice vectors .

λ 1 ( Λ ) λ 2 ( Λ )
Figure 2.1: The first two successive minima λ 1 (Λ) and λ 2 (Λ).

Definition 2.3 (Generator matrix).

A generator matrix G of Λ ⊆ R n is an n × n matrix whose rows form a basis of Λ, i.e.,

G =         b 1 b 2 . . . b n        
, where b 1 , b 2 , . . . , b n is a basis for Λ. In this case, the lattice is given by

Λ = {x • G : x ∈ Z n } .
and will be denoted Λ(G).

Since a basis for a given lattice Λ is not unique, the generator matrix is also not unique. If G 1 and G 2 are two generator matrices for Λ, they only differ by a unimodular matrix U, i.e.,

G 2 = U • G 1 with U ∈ GL (n, Z) = {A ∈ M n,n (Z) : det(A) = ±1}
. This allows us to define a lattice invariant called lattice determinant and formalized as follows:

Definition 2.4 (Lattice determinant). The lattice determinant det(Λ) is defined as the absolute determinant of its generator matrix |det(G)|.

The determinant of a lattice is independent of the choice of the generator matrix since the determinant of any unimodular lattice is ±1. This invariant quantity is also called volume of the lattice and denoted Vol(Λ). Furthermore, one can obtain a transformed version of a given lattice which retains its structure, simply by applying a rotation and/or by multiplying by a constant. This leads to the following definition:

Definition 2.5 (Similar lattices). Two lattices Λ 1 (G 1 ) and Λ 2 (G 2 ) are similar if there exist an orthogonal matrix O ∈ O(n), a unimodular matrix Z ∈ GL(n, Z) and a scalar α such that

G 2 = α • O • G 1 • Z.
Fundamental region. Given a lattice, one can tile the entire space R n using its fundamental region as a building block. This can be formalized as follows:

Definition 2.6 (Fundamental region). A bounded set F ⊆ R n is a fundamental region of Λ ⊆ R n if, when shifted by the lattice points, it generates a partition of R n ; that is:

• λ∈Λ (λ + F) = R n .
• For any distinct lattice points λ 1 and λ 2 , (λ

1 + F) ∩ (λ 2 + F) = ∅.
e Q = x mod F (Λ) = x -Q F (Λ) (x)
to be the quantization error. Some properties that will be used implicitly in our proofs can be found in [START_REF] Zamir | Lattice Coding for Signals and Networks: A Structured Coding Approach to Quantization, Modulation, and Multiuser Information Theory[END_REF] and are listed in the following lemma:

Lemma 2.1. Let Λ be an n-dimensional lattice with some predefined fundamental region F.

For all x, y ∈ R n and ∀λ ∈ Λ we have:

(P1) Distributive law: (x mod F (Λ) + y) mod F (Λ) = (x + y) mod F (Λ) (P2) Shift-invariance: (x + λ) mod F (Λ) = x mod F (Λ) (P3) Q F (Λ) (λ + x) = λ + Q F (Λ) (x) (P4) ∀ α ∈ R, Q αF (Λ) (x) = α • Q F (Λ) 1 α x
Fundamental regions allow us to represent any point in space, in a lattice dependent way.

Interestingly, their volume is a lattice invariant.

Theorem 2.1. All the fundamental regions of a lattice Λ have the same volume, namely det(Λ).

Voronoi region and Voronoi relevant vectors.

Here we will introduce one of the most important fundamental regions called the Voronoi region.

Definition 2.7 (Voronoi Region). For any lattice Λ ∈ R n , the Voronoi region V λ 0 (Λ) associated with a lattice point λ 0 contains all points in R n that are closest to λ 0 than any other lattice point. More formally,

V λ 0 (Λ) = {x ∈ R n : x -λ 0 ≤ x -λ , ∀λ ∈ Λ \ {λ 0 }} .
When λ 0 = 0, we use the notation V(Λ). Note that xa = xb ⇐⇒ xa, xa = xb, xb , which is equivalent to

x 2 -2 a, x + a 2 = x 2 -2 b, x + b 2
. This leads to the following equivalent formula for the bisector normal hyperplane:

B(a, b) = x ∈ R n : x, b -a = b 2 -a 2 2 (2.1)
Definition 2.9 (Voronoi relevant vectors). Let Λ be an n-dimensional lattice and V(Λ) its Voronoi region. A point λ ∈ Λ is a Voronoi relevant vector, and we write λ ∈ VR Λ , if the intersection of the bisecting normal hyperplane between 0 and λ with V is an (n-1)-dimensional face of V. So if Γ is the set of all such faces of V, the definition can be reformulated as

λ ∈ VR Λ ⇐⇒ {x ∈ R n : x, λ = λ 2 /2} ∩ V ∈ Γ.
Note that from Definition 2.9 we deduce that

∀ x ∈ R n , x ∈ V ⇐⇒ x, λ ≤ λ 2 2 for all Voronoi relevant vectors λ ∈ Λ. (2.2)
For an n-dimensional Euclidean lattice, the number of Voronoi relevant vectors is at most 2(2 n -1) in the worst-case [START_REF] Minkowski | Diskontinuitätsbereich für arithmetische äquivalenz[END_REF]. Calculating the Voronoi relevant vectors is not an easy problem and no polynomial algorithm is currently known. The diamond-cutting algorithm [START_REF] Viterbo | Computing the Voronoi cell of a lattice: the diamondcutting algorithm[END_REF] can be used to determine a complete description of the Voronoi cell, which is unfavorable if used only to describe the Voronoi relevant vectors. In [START_REF] Micciancio | A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations[END_REF] the authors propose a deterministic Õ 2 2n -time and Õ (2 n )-space algorithm that calculates the Voronoi relevant vectors. For small dimensional lattices one can use the Magma software2 in order to calculate our Voronoi relevant vectors. A concrete example will be given in Subsection 2.2.3 while reviewing the Gosset lattice.

Sublattice, quotient group and dual lattice. Defining a lattice Λ as a discrete group in R n allows us to define a sublattice Λ ⊆ Λ as a subgroup of Λ.

Definition 2.10 (Sublattice). Given an n-dimensional lattice Λ ⊆ R n , a sublattice Λ is a subset of Λ satisfying:

• 0 ∈ Λ • ∀ α ∈ Z, ∀ x, y ∈ Λ , the vector αx + y ∈ Λ .
A criterion which allows us to know when a lattice is a sublattice of another is given in the proposition below.

Proposition 2.1. Let Λ (G ) and Λ(G) be two n-dimensional lattices with generator matrices G and G respectively. If G • G -1 is an integer matrix, then Λ ⊆ Λ.

Proof. Suppose G • G -1 is an integer matrix and let x ∈ Λ . Then ∃y ∈ Z n such that x = y • G .

Therefore,

x = y • G • G -1 z∈Z n •G = z • G ∈ Λ.
If Λ ⊆ Λ is a sublattice, then one can define the concept of the quotient group. For our interest, the quotient group between two lattices is defined with respect to the Voronoi region.

Definition 2.11 (Quotient group). Let Λ ⊆ Λ be a sublattice of Λ ⊆ R n . The quotient Λ/Λ is the set of cosets (λ + Λ ) with λ ∈ Λ. Note that it can be identified with the set of coset leaders, i.e. the points in Λ ∩ V(Λ ).

Since V(Λ ) is bounded, the set Λ/Λ is finite and the number of points inside this quotient can be determined by using the volume measure. In fact, |Λ/Λ | = Vol(Λ )/Vol(Λ). A useful lemma for our purposes is given below.

Lemma 2.2. Let Λ ⊂ Λ and λ ∈ Λ a fixed vector. The map π : Λ/Λ → Λ/Λ given by

π : v → π(v) = (v + λ) mod Λ is a permutation of Λ/Λ . Proof. Let v, v ∈ Λ/Λ such that π(v) = π(v ). Then (v + λ) mod Λ = (v + λ) mod Λ .
This by definition can be written as

v + λ -Q Λ (v + λ) = v + λ -Q Λ (v + λ), which means that v -v = λ ∈ Λ .
Using Lemma 2.1 we deduce that v mod Λ = v mod Λ . This proves injectivity. Since Λ/Λ is a finite set, we obtain bijectivity.

We end up by giving the notion of the dual lattice, which is the set of points in space whose inner products with all the vectors in the original lattice are all integers.

Definition 2.12 (Dual lattice). The dual lattice of a lattice Λ is defined as

Λ * = {x ∈ R n : x, Λ } ⊆ Z.
In the next section, we study lattices from a computational perspective. We introduce some fundamental hard problems that are considered in lattice-based cryptography.

Computational problems on lattices

Several problems on lattices have fascinated scientists for many years, and so far, many of them are difficult to attack even on quantum computers. That's why the conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems. This vast area cannot be covered throughout this thesis and we only present the lattice problems that are most relevant to our study.

The most famous and widely studied computational problem on lattices is the shortest vector problem:

Definition 2.13 (Shortest vector problem SVP). Given a lattice Λ in R n , the shortest vector problem asks to find a non-zero vector v such that v = λ 1 (Λ).

Note that we have used the Euclidean norm here which is the most common, but it is important to mention that the problem can be posed with respect to any norm. This problem was extensively studied by mathematicians in the 19 th century and to date there is no polynomial time algorithm (with respect to the lattice dimension n) capable of solving it. For the Euclidean norm, the SVP problem has been conjectured to be NP-hard by van Emde Boas in 1981 [START_REF] Van | Another NP-complete problem and the complexity of computing short vectors in a lattice[END_REF] before appearing in Ajtai's breakthrough where he showed the NP-hardness of the problem under randomized reductions [START_REF] Ajtai | The shortest vector problem in L 2 is NP-hard for randomized reductions[END_REF].

An exact computation of SVP that runs in 2 O(n log n) time was proposed in [START_REF] Kannan | Minkowski's convex body theorem and integer programming[END_REF] via the enumeration method, and requires polynomial space in n. Enumeration is simply an exhaustive search for an integer combination of the basis vectors such that the lattice vector is the shortest, inside some given region. Later in 2001, Ajtai et al. [START_REF] Ajtai | A sieve algorithm for the shortest lattice vector problem[END_REF] proposed a sieving probabilistic algorithm that solves SVP in time 2 O(n) . The sieve algorithms perform some kind of randomized enumeration on a smaller set. These algorithms have a better asymptotic running time, but they all require exponential space. Another algorithm based on constructing the Voronoi cell was presented in 2001 by Micciancio and Voulgaris [START_REF] Micciancio | The shortest vector in a lattice is hard to approximate to within some constant[END_REF] with a time complexity of 2 2n+o(n) and a space complexity of 2 n+o (n) . The fastest known algorithm [START_REF] Aggarwal | Solving the shortest vector problem in 2 n time using discrete gaussian sampling[END_REF] runs in provable 2 n+o (n) time and is based on discrete Gaussian sampling. Note that for most existing algorithms, the constants hidden in the exponents are relatively large, and the enumeration methods are in fact faster than other methods and commonly used in practice to find the shortest vectors in high dimensions [START_REF] Micciancio | Fast lattice point enumeration with minimal overhead[END_REF]. Regarding the sieving methods, recent heuristic analyses show that one can solve SVP in time 2 0.298n+o(n) and space 2 0.208n+o(n) [START_REF] Laarhoven | Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing[END_REF].

The result by [START_REF] Aggarwal | Solving the shortest vector problem in 2 n time using discrete gaussian sampling[END_REF] was known to be the best in the classical and quantum perspective, but more recently, [START_REF] Aggarwal | Improved (provable) algorithms for the shortest vector problem via bounded distance decoding[END_REF] give a quantum algorithm that solves SVP in 2 0.9533n+o(n) time and classical 2 0.5n+o(n) space. By applying a quantum search algorithm, the authors of [START_REF] Laarhoven | Finding shortest lattice vectors faster using quantum search[END_REF] make asymptotic improvements regarding the resolution of the shortest vector problem. They improve the classical result of [START_REF] Micciancio | The shortest vector in a lattice is hard to approximate to within some constant[END_REF] from 2 2n+o(n) to 2 1.799n+o(n) , while heuristically they obtain 2 0.268n+o(n) time complexity rather than the classical result of 2 0.298n+o(n) time in [START_REF] Laarhoven | Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing[END_REF].

In practice, finding a reasonably short vector instead of a shortest vector is also sufficient for many applications, and the question of whether we can find a vector that approximates the A reduction from SVP γ to CVP γ was given in [START_REF] Goldreich | Approximating shortest lattice vectors is not harder than approximating closest lattice vectors[END_REF] showing that approximating the closest lattice vector is at least as hard as approximating the shortest lattice vector. A reduction in the other direction that preserves the dimension is still unknown. CVP has been proven in [START_REF] Van | Another NP-complete problem and the complexity of computing short vectors in a lattice[END_REF] to be NP-hard, just as CVP γ for γ = n c/ log log n and c < 1/2 [START_REF] Dinur | Approximating-CVP to within almostpolynomial factors is NP-hard[END_REF]. A polynomial time algorithm that solves CVP γ is the Babai nearest plane algorithm for γ = 2(2/ √ 3) n [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]. An exact solution for CVP is given in [START_REF] Kannan | Minkowski's convex body theorem and integer programming[END_REF] using an enumeration method that runs in time n O(n) , and many other improvements with better running times can be found in [START_REF] Helfrich | Algorithms to construct Minkowski reduced and Hermite reduced lattice bases[END_REF][START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF][START_REF] Micciancio | Fast lattice point enumeration with minimal overhead[END_REF].

shortest
Another algorithm that solves exact CVP in 2 n+o(n) -time is given in [START_REF] Aggarwal | Solving the Closest Vector Problem in 2 n Time-The Discrete Gaussian Strikes Again![END_REF].

We end up our discussion with one more problem connected to lattices which is considered a special version of the closest vector problem, namely the Bounded Distance Decoding problem.

Definition 2.17 (Bounded Distance Decoding α-BDD). Given a lattice Λ in R n and a point t such that its distance from the lattice is at most α • λ 1 (Λ), find the closest lattice vector to t.

Klein [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF] solves the problem for α = O(1/n) in polynomial time, and [START_REF] Liu | On bounded distance decoding for general lattices[END_REF] improve the factor α to O log n/n using pre-processing. The α-BDD problem is known to be NP-hard

for α > 1/ √ 2 [LLM06].
Many other lattice problems exist in the literature and it is infeasible to include them all in one context. SVP γ and CVP γ admit various variations such as:

• unique-SVP γ : Given a lattice Λ such that λ 2 (Λ) > γλ 1 (Λ), find the shortest non-zero lattice vector in Λ.

• GapSVP γ : Given a lattice Λ, the problem is to decide whether λ 1 (Λ) < 1 or λ 1 (Λ) > γ.

The Gosset lattice E 8

In this subsection, we are going to introduce the most relevant lattice for our study which will be used in the sequel. The Gosset lattice E 8 is the densest 8-dimensional lattice [START_REF] Maryna | The sphere packing problem in dimension 8[END_REF] defined as

E 8 = (x 0 , . . . , x 7 ) ∈ Z 8 ∪ Z + 1 2 8 : 7 i=0 x i = 0 mod 2 .
In particular, E 8 is generated by the following matrix:

G E 8 =                    2 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 -1 1 0 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2                    (2.3) As a result of how E 8 is defined, it is important to note that 2Z 8 ⊆ E 8 ⊆ 1 2 Z 8 . The volume of E 8 is |det(G E 8 )| = 1 and its minimal norm is λ 1 (E 8 ) = √ 2.
The Voronoi relevant vectors can be divided into two sets. The first set VR

(1) E 8 contains 112 vectors of the form (±1 2 , 0 6 ), while the second set VR

(2) E 8 consists of 128 vectors of the form (±0.5 8 ), giving a total of 240 vectors [START_REF]John Conway and Neil Sphere packings, lattices and groups[END_REF]. The list of Voronoi relevant vectors can be obtained via a simple Magma code which can be found in Appendix A.3.

Finding the closest point of E 8

We present here an efficient algorithm to find the closest point in E 8 to a vector x ∈ R 8 , which was proposed in [START_REF] Conway | Fast quantizing and decoding algorithms for lattice quantizers[END_REF]. We first define f (x) = x , and g(x) = x to be the same as x except that the worst component -that furthest from an integer -is rounded the wrong way. More formally, if i 0 = argmax

0 ≤ i ≤ 7 |x i -x i | then for i = 0, . . . , 7 we have x i =      x i if i = i 0 x i + sign (x i ) • sign (|x i | -|x i | ) if i = i 0
The algorithm computes f (x) and g(x), and selects the one that has an even sum of components.

Call that vector y. Then it computes f (x -1/2) and g(x -1/2), and selects whichever has an even sum of components; adds 1/2 and calls the result y . At the end, the output vector is the closest one to x among y and y . A pseudo-code for the algorithm is presented in Algorithm 1.

Algorithm 1 Closest Vector Point in E 8 1: function CVP E 8 (x ∈ R 8 ) 2: f = x ; g = x 3: y = (1 ⊕ f i ) f + (1 ⊕ g i ) g 4: f = x -1 2 ; g = x -1 2 5: y = (1 ⊕ f i ) f + (1 ⊕ g i ) g + 1 2 6: return argmin λ∈{y,y } x -λ ∈ E 8
An infinite family of lattices with good (although not optimal) packing properties which generalizes the E 8 lattice was introduced by Barnes and Wall [START_REF] Barnes | Some extreme forms defined in terms of abelian groups[END_REF] and is discussed in the next section.

Barnes-Wall lattices

Barnes-Wall lattices BW n form a sequence of full-rank lattices whose dimension n is a power-oftwo. These lattices are attractive due to their simplicity and relevance for practical applications

[AV00, BB98, For88, FV96].
Definition 2.18 (Barnes-Wall lattice). For a power-of-two integer n ≥ 2, a generator matrix of BW n can be defined recursively as:

• G BW 2 =   1 0 0 1   • For n ≥ 4, G BW n =   G BW n 2 G BW n 2 0 Φ n 2 • G BW n 2   , with Φ n = I n 2 ⊗   1 -1 1 1   .
Remark 2.1. We note that this definition is equivalent to the definition of Barnes-Wall lattices as n 2 -dimensional complex lattices over the Gaussian integers [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF], by converting complex numbers into matrices as

C → R 2×2 a + ib →   a -b b a  
The Barnes-Wall lattice BW n has volume Vol(BW n ) = (n/2) n/2 and minimal distance [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF] give a polynomial time algorithm to solve the bounded distance decoding ( 1 2 -BDD) for Barnes-Wall lattices: given a vector s ∈ R n within distance d min (BW n ) /2 = n/8 from some lattice point λ in BW n , find λ. This algorithm called ParBW has complexity O n log 2 n and induces a partition of the space R n as a result of the following theorem:

d min (BW n ) = n/2.

Micciancio and Nicolosi

Theorem 2.2. Let s ∈ R n . For a fixed λ ∈ BW n , we have ParBW(λ + s) = λ + ParBW(s).
In other words, ParBW induces a partition of R n into fundamental cells.

A proof of this theorem can be found in Appendix A.5. Another important property that characterizes the scaling of integer lattices inside BW n is given below, with a proof in Appendix A.6.

Proposition 2.2. For n ≥ 2 and k ≥ log n 2 , 2 k Z n ⊆ BW n ⊆ Z n .

The lattice BW 16

The densest known lattice in R 16 is the 16-dimensional Barnes-Wall lattice BW 16 that was first introduced in [BW59], and appears later in [START_REF] Conway | Laminated lattices[END_REF][START_REF] Leech | Sphere packings and error-correcting codes[END_REF][START_REF] Conway | On the voronoi regions of certain lattices[END_REF]. This lattice is obtained through different constructions such as applying Construction B to the first-order Reed-Muller code [16, 5, 8], as well as through Construction C (or D) and many other methods [START_REF]John Conway and Neil Sphere packings, lattices and groups[END_REF].

The generator matrix of this lattice is given in [Slo81, page 336] by the following triangular matrix

G BW 16 = 1 2                            4 2 2 2 0 2 2 0 0 2 2 0 0 0 2 2 0 0 0 0 2 2 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 2 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1                            .
(2.4)

The volume for the corresponding scaling is 1/16 and the minimal distance is √ 2. The Voronoi relevant vectors can be divided into three sub-types:

(±1 2 , 0 14 ) ∈ VR (1)
BW 16 , (±0.5 8 , 0 8 ) ∈ VR

(2)

BW 16 , and (±0.5 8 , ±1, 0 7 ) ∈ VR

(3)

BW 16 ,
with cardinality

VR

(1)

BW 16 = 480, VR (2)
BW 16 = 3839 and VR

(3)

BW 16 = 61441.
The Barnes-Wall lattice BW 16 contains the sublattice 2D 16 for which BW 16 /2D 16 = 32 [START_REF] Conway | On the voronoi regions of certain lattices[END_REF].

Recall that the lattice D n is defined by

D n = (x 1 , . . . , x n ) : n i=1 x i = 0 mod 2 .
A low-complexity algorithm to find the closest lattice point in D n to a point x ∈ R n is given in [START_REF] Conway | Fast quantizing and decoding algorithms for lattice quantizers[END_REF]. Using the decomposition of BW 16 into cosets of D 16 , it is possible to obtain a CVP algorithm for BW 16 from the CVP algorithm for D 16 . In fact, if Λ = d-1 i=0 (r i + Λ ) is a union of cosets of Λ and Φ is an algorithm that calculates the CVP on Λ , then the closest point to x in Λ is obtained by comparing each of Φ(x -r i ) + r i with x and choosing the closest [START_REF] Conway | Fast quantizing and decoding algorithms for lattice quantizers[END_REF]. In our case, Λ = BW 16 , Λ = 2D 16 and r i are the codewords of the [16, 5, 8] first-order Reed-Muller code.

Cryptographic definitions

Security protocols today are based either on private key cryptosystems or on public key cryptosystems. Private key cryptography uses the same shared key to ensure communication between the parties. For the most part, the generation of this shared key is performed through public key protocols.

Public-key encryption scheme (PKE)

Public-key encryption is a procedure that allows to encrypt messages using a pair of keys known as a public key (which is available for anyone to use) and a secret key (kept secret by the intended receiver). Given a finite message space M and a ciphertext space C, public-key encryption involves three efficient algorithms (Gen, Enc, Dec) define as follows:

• Gen(pp) is a probabilistic algorithm that outputs a secret key sk and a public key pk using a public parameter pp as input.

• Enc(pp, pk, m) is a probabilistic algorithm that encrypts an input message m ∈ M using the public key pk and the parameter pp, in order to return a ciphertext c ∈ C.

• Dec(sk, c) is a deterministic decryption algorithm that operates on the secret key sk and ciphertext c and delivers a message m ∈ M or an error symbol ⊥ denoting decryption failure.

Figure 2.4 illustrates the public-key encryption scheme. In order for Bob to send a message m to Alice, she produces the public key pk as well as the secret key sk. Upon receiving the public key, Bob encrypts m using pk and sends it to Alice who can now decrypt the message using sk and obtain m or an error symbol ⊥. Note that in some schemes, particularly in lattice-based cryptography, the recovered message m may be different from the transmitted one. That's why we define the correctness of the scheme in Definition 2. [START_REF][END_REF]

Definition 2.19 (Correctness for PKEs). A public-key encryption PKE is δ-correct if

P m = m (pk,sk)←-Gen(pp) c←-Enc(pp,pk,m) m←-Dec(sk,c) ≤ δ.
Remark 2.2. Sometimes we also associate a randomness space R to the PKE to denote the fact that the randomness used in Enc is picked uniformly from R on every execution. Note that if R is an empty set, then the encryption algorithm is purely deterministic. In some cases, the public parameter pp is excluded from Enc(pp, pk, m) as input, and replaced instead by an element of R if such a randomness space R is taken into account.

Key encapsulation mechanism (KEM)

We define the notion of key encapsulation mechanism (KEM) as the procedure for transmitting an ephemeral private key to a receiver using the latter's public key. Given a ciphertext space C and finite key space K, it consists of a tuple of efficient algorithms (Gen, Encaps, Decaps):

• Gen(pp) is a probabilistic algorithm that takes a public parameter pp as input and returns a secret key sk and a public key pk.

• Encaps(pp, pk) is a probabilistic algorithm that takes (pp, pk) as input and produces a ciphertext c ∈ C and a private key k ∈ K.

• Decaps(sk, c) is a deterministic algorithm that takes the secret key sk and ciphertext c to return a key k ∈ K or a special symbol ⊥ to indicate that c is not a valid encapsulation.

A visual representation of the scheme is given in

Definition 2.20 (Correctness for KEMs).

A key encapsulation mechanism KEM is δ-correct if

P k = k (pk,sk)←-Gen(pp) (c,k)←-Encaps(pp,pk) k←-Decaps(sk,c) ≤ δ.

Cryptographic attacks and security

Cryptographic systems have always been vulnerable to malicious attackers who aim to find out something about the transmitted information or even the secret key. There are different types of attacks that can be applied to different encryption systems, each with a different level of effectiveness. One can analyze security with regard to the most well-known attacks existing in the literature, or through a theoretical approach by measuring the probability that an attacker could guess the encrypted data. The advantage of an adversary measures its ability to attack a cryptographic algorithm by comparing the actual algorithm to an idealized version of that type of algorithm. One useful tool for security proofs is the concept of random oracle model (ROM). A random oracle is a designed strategy in which a "black box" takes some input data and generates an output, uniformly and randomly, in some conventional space (the space of oracle outputs). Usually the black box is modeled as a hash function. Given an already seen input, the random oracle returns the same output it returned the last time. This model turns out to be very useful for analyzing the security of cryptographic schemes. Referring to [Puc05],

a system is secure in the random oracle model if its security can be proven, supposing all parties (including the adversary) have access to the random oracle. Most random oracle systems to date are only proven secure in the context of classical attacks, that is, the attacker can only learn an output value by querying the oracle at the classical state input x. We call this the classical random oracle model. It turns out that as we move beyond classical computing, the random oracle model needs to be revisited in the context of quantum attacks. In this model, the attacker may query the random oracle in superposition over multiple x's. We call this the quantum random oracle model.

One of the simplest attacks is brute force attack. The attacker tries to check all the differ-ent possibilities in order to get the information he wants. Modern cryptographic systems are secure against these types of attacks because they impose an exponential number of different possibilities that make searching impractical for an attacker. Even quantum computers can only provide a quadratic speedup for black-box queries over a classical brute-force attack using Grover's algorithm, and this can be settled by doubling the size of the underlying security parameters.

Attacks can also target the weakness in physical implementation by analyzing the different run times with different plaintexts or secret keys. This is what we call a timing attack. To prevent this kind of attack from happening, a constant-time implementation independent of the input is required.

In public key cryptography, since the public key allows anyone to encrypt any desired message, an attacker could have the ability to obtain ciphertexts corresponding to arbitrary plaintexts. This kind of attack, called chosen plaintext attack (CPA), could lead to extracting the secret key used in the underlying cryptosystem. A basic requirement for most modern cryptographic schemes is the property of indistinguishability under chosen-plaintext attack (IND-CPA)

for which an attacker is unable to distinguish to which message corresponds a given ciphertext.

A more powerful form of attack called a chosen ciphertext attack (CCA) is a scenario in which the attacker is able to not only encrypt the chosen message, but also collect a piece Finally, when talking about practical perspectives, a cryptosystem can have different forms of attacks for which we can estimate concrete security. It consists in exploring the minimum attack requirements in terms of computational complexity in order to quantify the amount of computations necessary for an adversary to break the system. It provides an upper bound on the advantage of the opponent to break the system according to the existing resources in hand, which are usually running time and memory.

IND-CPA security for PKE

We define a game to examine whether an attacker is able to identify which message has been encrypted into a given ciphertext with significantly better probability than random guessing.

We consider the following game between a challenger and an adversary:

• The challenger derives a public and secret key pk and sk using Gen().

• The adversary sends the challenger two messages m 0 and m 1 in order to launch the game.

• The challenger chooses a uniformly random bit b bit and encrypts the message m b message using Enc() to obtain the ciphertext c * .

• The attacker receives the decrypted message c * and tries to guess the original message m b using Enc() itself (since it is public). He then outputs its guess b .

• If b = b, the adversary wins the game. Otherwise, he loses. The public-key encryption scheme is considered IND-CPA secure if any polynomial time adversary has only a negligible advantage over random guessing. This advantage is defined as

Adv IND-CPA PKE = P b = b - 1 2 .
Deterministic encryption algorithms cannot be IND-CPA secure. In fact, if the scheme were deterministic, then the adversary could directly use the encryption algorithm to distinguish which message was encrypted. In contrast, if the underlying encryption scheme is probabilistic, the encrypted message will be only one of many valid ciphertexts, and hence comparing between Enc(m 0 ) and Enc(m 1 ) does not provide any non-negligible advantage to the adversary.

IND-CPA security for KEM

The notion of IND-CPA security has been extended to also apply to key encapsulation mechanisms. It considers how well an adversary is able to distinguish the real shared private key from a random one, using the public Encaps function. The corresponding indistinguishability game can be illustrated as follows:

• The challenger obtains the public key pk and the secret one sk with the aid of the Gen function.

• The challenger picks a uniform bit b and obtains (c * , k 0 ) = Encaps(pp, pk).

If b = 0, it outputs (pk, c * , k 0 ). If b = 1, it outputs (pk, c * , k 1 )
where k 1 is generated uniformly at random in the key space K.

• The adversary tries to guess whether k b corresponds to k 0 or k 1 , using Encaps() and returns a guessing bit b .

• If b = b, then the attacker was able to distinguish the two games and therefore wins the challenge.

Figure 2.7 illustrates the game above.

Challenger sk A more compact interpretation is given below. A KEM satisfies IND-CPA security if the outputs of the following "real" and "ideal" games are computationally indistinguishable:

(c * , k 0 ) = Encaps(pp, pk) k 1 $ ← -K b $ ← -{0, 1} Attacker Encaps() b ∈ {0, 1} (c * , k b ) pk
Real Game Ideal Game (pk, sk) ← Gen(pp) (pk, sk) ← Gen(pp) (c * , k0) ← Encaps(pp, pk) (c * , k0) ← Encaps(pp, pk) k1 $ ← -K Output(pp, pk, c * , k0) Output(pp, pk, c * , k1)
The advantage of an adversary to distinguish between the two games is defined by:

Adv IND-CPA KEM = P b = b - 1 2 .

IND-CCA security for PKE

In this setting, we consider a classical or quantum algorithm A Dec in possession of the adversary that can be used many times, and is capable not only of encrypting messages, but also of decrypting arbitrary ciphertexts at the adversary's demand. Similarly to the IND-CPA definition, a game between the adversary and the challenger is set up to examine whether the adversary is now able to predict with probability better than 1/2 which message was encrypted given the more powerful algorithm A Dec :

• The challenger generates the pair (pk, sk) using Gen().

• The adversary assigns two messages m 0 and m 1 to the challenger. The encryption algorithm is said to be IND-CCA secure if the adversary has a negligible advantage in winning the above game. The advantage can be similarly defined as

Adv IND-CCA PKE A Dec = P b = b A Dec - 1 2 .

IND-CCA security for KEM

In this setup, the adversary is endowed with a decapsulation algorithm A Decaps that is able to recover the private key given a specific ciphertext. Once again, we are building a game between the adversary and the challenger to explore the attacker's potential to distinguish the true private key from a uniformly random key. Note that A Decaps outputs the failure symbol ⊥ once it receives the challenge ciphertext. The game works as follows:

• The challenger produces a secret key sk and a public one pk using the Gen function.

• The adversary knows that the challenger will generate (k 0 , c * ) from Encaps (pk) and k 1 uniformly at random from the key space K.

• The challenger chooses a uniform b in {0, 1} and generates (c

* , k 0 ) = Encaps(pp, pk). If b = 0, he sends (c * , k 0 ). If b = 1, he sends (c * , k 1 ),
where k 1 is uniformly random.

• Using A Decaps as additional weapon, the adversary tries to guess if the key k b corresponds to k 0 (the output of Encaps) or to k 1 (uniform key) and outputs a guessing bit b .

• If b = b, the adversary passes the challenge. The KEM is defined to be IND-CCA secure if the adversary has a negligible advantage in gaining the above game. We give the formal definition of the advantage as:

Adv IND-CCA KEM A Decaps = P b = b A Decaps - 1 2 .

Fujisaki-Okamoto transform

The Fujisaki-Okamoto (FO) transform was first introduced in [FO99] and aims to transform an IND-CPA secure PKE into an IND-CCA KEM in the classical random oracle model (assuming the distribution of ciphertexts for each plaintext is sufficiently close to uniform). This transformation uses some hash functions which are modeled as random oracles in the security proof. Moreover, the encryption scheme is required to be deterministic and bijective, but such restrictions have been removed in [START_REF] Fujisaki | Secure integration of asymmetric and symmetric encryption schemes[END_REF]. Targhi and Unruh (TU) [START_REF] Ebrahimi | Post-quantum security of the fujisakiokamoto and oaep transforms[END_REF] deliver a variant of the Fujisaki-Okamoto transform against a quantum adversary in the quantum random oracle model under similar assumptions. However, these two transformations assume that the publickey encryption scheme is perfectly correct, i.e., not having a decryption error, which is not the case for lattice-based schemes.

1. µ $ ← -M 2. (r, mh) ← G 2 (pkh||µ) 3. c ← PKE.Enc(r, pk, µ) 4. k ← F (c||mh) 5. return (c, k) kol khara KEM ⊥ .Decaps(c, sk ) 1. µ ← PKE.Dec(c, sk) 2. (r , mh ) ← G 2 (pkh||µ ) 3. k 0 ← F (c||mh ) 4. k 1 ← F (c||s) 5. If c = PKE.Enc(r , pk, µ ): k ← k 0 . Else: k ← k 1 6. return k
The outputs of the hash functions are marked in bold. Note that pkh, mh are "hashed" versions of the public key and intermediate shared secret. Moreover,

• The FO ⊥ transform outputs a shared private key k of length k ;

• A hashed public key pkh of length pkh is generated from pk;

• A binary vector s of length s (not smaller than k ) is used for pseudo-random shared secret generation in the event of decapsulation failure in the FO ⊥ transform ;

• An intermediate shared secret mh of length mh is generated from pkh and a message µ.

KEM ⊥ differs from [START_REF] Hofheinz | A modular analysis of the Fujisaki-Okamoto transformation[END_REF] in the following points:

• A single hash function (with longer output) is used to compute r and mh, whereas FO ⊥ uses two separate functions, but these are equivalent when the hash functions are modeled as independent random oracles and have appropriate output lengths.

• The public key pk is used as input for G 1 in order to deliver r and mh from pkh = G 1 (pk), whereas FO ⊥ does not; this change preserves the relevant theorems (with trivial changes to the proofs), and has the potential to provide stronger multi-target security.

• The computation of the shared private k takes the encapsulation c as input to F .

Remark 2.3. It is important to mention that during decapsulation in KEM ⊥ .Decaps(), it is crucial to execute step 5 in constant time, because otherwise, a timing attack enables key recovery. This was observed by Guo, Johansson, and Nilsson in [START_REF] Guo | A key-recovery timing attack on post-quantum primitives using the fujisaki-okamoto transformation and its application on frodokem[END_REF].

Error distributions

In this work, we will deal with error terms that will be included in various definitions and applications. In the following, we present some possible choices for the error distribution that have been introduced in lattice-based cryptography. Note that for practical applications, we will need distributions that can be sampled efficiently.

Discrete and rounded Gaussian

We start by defining the Gaussian function.

Definition 2.22 (Gaussian function). For any s > 0, the Gaussian function on R n centered at c with parameter s is defined as follows:

∀x ∈ R n , ρ s,c (x) = exp -π x -c 2 s 2
When c = 0, the distribution is simply denoted by ρ s (x). Note that

x∈R n ρ s,c (x)dx = s n .
This allows us to derive the continuous Gaussian distribution from it.

Definition 2.23 (Continuous Gaussian distribution). The continuous Gaussian distribution centered at c with standard deviation σ = s/ √ 2π is given by:

∀x ∈ R n , D s,c (x) = 1 s n • ρ s,c (x)
Discrete Gaussian. Definition (2.23) can be extended to any countable set A ⊆ R n in the usual way; e.g.

D s,c (A) = 1 s n • ρ s,c (A) = 1 s n • x∈A ρ s,c (x)
Since a lattice is a countable set, we can thus introduce the concept of discrete Gaussian distribution defined on each point of the lattice as follows:

Definition 2.24 (Discrete Gaussian distribution). Given a lattice Λ, we define the discrete Gaussian distribution over the lattice to have the following probability density function:

∀λ ∈ Λ, D Λ,s,c (λ) = D s,c (λ) D s,c (Λ) = ρ s,c (λ) ρ s,c (Λ)
Rounded Gaussian. Informally, the rounded Gaussian distribution is obtained by rounding the samples of a continuous Gaussian distribution to the nearest integer. We will only consider centered distributions.

Definition 2.25 (Rounded Gaussian distribution). The rounded Gaussian distribution Ψ s with parameter (or width) s > 0 is obtained from D s as follows:

∀ a ∈ Z n , Ψ s (a) = {x : x =a} D s (x)dx n
This distribution is also centered at zero and has standard deviation close to σ 2 + 1 12 .

-18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18

Centered binomial distribution

Since it is challenging to implement a discrete Gaussian sampler to be efficient and protected against timing attacks, one can replace the former distribution by a discrete distribution that is easier to sample. In particular, [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] proposed to use the centered binomial distribution ψ k of standard deviation k/2, which is the distribution of the random variable B k is defined as

B k = k i=1 (b i -b i )
where b i , b i are independent and uniformly distributed in {0, 1}, for i = 1, . . . , k. Note that B k takes values in {-k, . . . , k} and it is a centered and symmetric random variable. As an example, the distribution ψ 16 is illustrated in Figure 2.10. The following result allows to calculate the distribution ψ k :

Proposition 2.3. Let B k denote the random variable that corresponds to the centered binomial distribution ψ k . Then,

∀ t ∈ {-k, . . . , k}, P{B k = t} = 1 2 2k • min(k+t,k) j=max(0,t) k j k j -t Proof. Note that X = k i=1 b i has a binomial distribution B k, 1 2 , as well as Y = k i=1 b i .
Combining the cases for positive and negative t into one case we obtain the following:

P{B k = t} = min(k+t,k) j=max(0,t) P {X = j} • P {Y = j -t} = min(k+t,k) j=max(0,t) k j 1 2 k • k j -t 1 2 k = 1 2 2k • min(k+t,k) j=max(0,t) k j k j -t

Subgaussian distribution

Definition 2.26 (Subgaussian distribution in R). For any δ ≥ 0, a distribution X over R is called subgaussian with parameter s > 0, if ∀t ∈ R, E e 2πtX ≤ e πt 2 s 2 . Remark 2.4. If X is subgaussian with parameter s, then for any c ∈ R, cX is subgaussian with parameter |c|s. Moreover, using the inequality cosh(x) ≤ exp(x 2 /2), it can be shown that any B-bounded centered random variable X (i.e. E[X] = 0 and |X| ≤ B) is subgaussian with parameter B √ 2π [LPR].

We extend the definition to R n as follows:

Definition 2.27 (Subgaussian distribution in R n ). We say that a random vector X n in R n is subgaussian with parameter s > 0 if for any unit vector u ∈ R n , the inner product X n , u is subgaussian with parameter s > 0, i.e., ∀t ∈ R, and

∀u ∈ R n : u = 1, E e 2πt X n ,u ≤ e πt 2 s 2 .
Proposition 2.4. Let X 1 , . . . , X k be independent subgaussian random variables over R with

parameters s i . Then k i=1 X i is subgaussian with parameter s = k i=1 s 2 i 1 2 .
Proof. It suffices to prove the proposition for k = 2.

E e 2πt(X 1 +X 2 ) = E e 2πtX 1 • e 2πtX 2 = E e 2πtX 1 • E e 2πtX 2 ≤ e πt 2 (s 2 1 +s 2 2 )
Proposition 2.5. Let X n be a centered random variable in R n such that each component is s-subgaussian. Then X n is subgaussian with parameter s √ n.

Proof. We need to show that for every unit vector u, X n , u is subgaussian with parameter

s √ n. In fact, E e 2πt X n ,u = E e 2πt(X 1 u 1 +•••+Xnun) = E e 2πtX 1 u 1 • • • • • e 2πtXnun ≤ E e 2πtnX 1 u 1 • • • • • E e 2πtnXnun 1/n (using Hölder's inequality) ≤ e πu 2 1 t 2 n 2 s 2 • • • • • e πu 2 n t 2 n 2 s 2 1/n = e πt 2 s 2 ns 2 (u 2 1 +•••+u 2 n ) = e πt 2 s 2 n .
This shows that X n is subgaussian with parameter

√ s 2 n = s √ n.
The following theorem inspired from [START_REF] Hsu | A tail inequality for quadratic forms of subgaussian random vectors[END_REF] establishes a tail inequality for subgaussian random variables.

Theorem 2.3. Let X n be a subgaussian vector in R n with parameter s. Then ∀ > 0:

P X n > s √ 2π √ n • 1 + 2 + 2 2 ≤ e -n 2
The proof of this theorem can be found in Appendix A.7.

Theorem 2.4. The centered binomial distribution ψ k is subgaussian with parameter √ kπ.

Proof. Remark that the distribution ψ 1 is subgaussian with parameter s = √ π. In fact, B 1 takes values in {-1, 0, 1} with probabilities 1 4 , 1 2 , 1 4 respectively. So

E e 2πtB 1 = k∈{-1,0,1} e 2πtk • P{B 1 = k} = 1 4 e -2πt + 1 2 e -2π•0 + 1 4 e 2πt = 1 2 + 1 2 e 2πt + e -2πt 2 = 1 + cosh(2πt) 2 ≤ e 4π 2 t 2 4 = e πt 2 •(π)
Hence using Proposition 2.4 we obtain the desired result.

Rényi divergence

Definition 2.28 (Rényi Divergence). Given two discrete probability distributions P and Q such that Supp(P ) is finite and α > 1, we define the Rényi divergence of order α between P and Q to be

D α (P ||Q) = 1 1 -α ln   x∈Supp(P ) P (x) P (x) Q(x) α-1   3 .
The Rényi divergence evaluates the closeness between two probability distributions. It can be seen as an alternative to the statistical distance and it was shown in [BLRL + 18] that using the Rényi divergence rather than the statistical distance yields tighter security reductions.

Although many security proofs in lattice cryptography assume that the error has a rounded Gaussian distribution, many lattice cryptosystems use a different error distribution which is more suitable for practical implementation yet is close to a rounded Gaussian in Rényi divergence. We give in Appendix A.2 an example of calculating the Rényi divergence between the rounded distribution Ψ √ 16π and the centered binomial ψ 16 .

Chapter 3

Error correction for FrodoKEM

Introduction

In this chapter, we will present an error correction mechanism for FrodoKEM, which is an IND-CCA secure key encapsulation mechanism that was selected to pass the third round of the NIST

Learning With Errors (LWE)

Definition 3.1 (Search-LWE problem: LWE q,χ ). For n ≥ 1, let q = q(n) ≤ poly(n) be an integer. Choose a secret s ∈ Z n q . Choose a polynomial number of samples a 1 , . . . , a m from Z n q independently and uniformly random. Fix an "error" probability distribution χ : Z q → R + . For i = 1, . . . , m, set b i = a i , s + e i mod q, where each e i ∈ Z q is chosen independently according to χ. The goal is to recover the secret s given these m equations.

It is important to mention that the instances of the LWE problem can be given in matrix form b = As + e where A is an m × n matrix. More precisely,

     b 1 . . . b m      =      . . . a 1 . . . . . . . . . a m . . .      •      s 1 . . . s n      +      e 1 . . . e m      mod q.
One of the possible choices for the error distribution χ is the rounded Gaussian distribution with parameter αq for α ∈ (0, 1), and reduced modulo q. For a suitable choice of q and α, a solution to LWE q,χ implies a quantum solution to worst-case lattice problems as the theorem below indicates.

Theorem 3.1 ( [Reg09]

). Let n, q be integers and α ∈ (0, 1) be such that αq > 2 √ n. Let Ψ s be a rounded Gaussian with parameter s = αq. Solving LWE q,Ψs efficiently implies an efficient quantum algorithm that approximates the decision version of the shortest vector problem GapSVP Õ(n/α) and the shortest independent vectors problem SIVP Õ(n/α) in the worst case.

The value of α is usually taken to be 1/poly(n) due to the approximations factors of the underlying lattice problem. The modulus q cannot be taken to be greater than polynomial since it may affect the efficiency for the underlying cryptographic applications as it increases the size of the input As + e. The ratio between the modulus q and the noise width, called modulusto-noise ratio, is simply 1/α, and the security is enhanced once this ratio becomes smaller1 .

The second form of LWE is the decision version which provides a simpler security analysis related to indistinguishability proofs.

Definition 3.2 (Decision-LWE)

. Consider the same settings as in Definition 3.1. The goal is to distinguish with some non-negligible advantage between polynomially many pairs of the form:

(a i , b i = a i , s + e i mod q) and (a i , b * i ) , with b * i uniformly random in from Z m q .
Note that search-LWE and decision-LWE are equivalent problems [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF][START_REF] Stehlé | Advanced cryptographic primitives -The Learning With Errors Problem[END_REF][START_REF] Mahmoody | Topics in cryptography -CS 4501-650[END_REF].

Definition 3.3 (LWE advantage)

. For an attacker A, we define the advantage Adv LWE n,m,q,χ as

P      b = 1 A $ ← -Z m×n q (s,e)←χ n ×χ m b=As+e b ←A(A,b)      -P    b = 1 A $ ← -Z m×n q b $ ← -Z m q b ←A(A,b)   
where b = 1 is the output of the distinguisher A.

Solving LWE. Most of the literature considers the hardness of the LWE problem asymptotically. Herold et al. show that when taking a polynomial number of samples, all known algorithms that solve LWE in dimension n run in time 2 O(n) [START_REF] Herold | On the asymptotic complexity of solving LWE[END_REF]. [START_REF] Kirchner | An improved BKW algorithm for LWE with applications to cryptography and lattices[END_REF] considers the case when the LWE error term is binary in {0, 1} m , and shows that in this case, the LWE problem can be solved in subexponential time, indicating that LWE with binary error is weaker than general LWE. However, the asymptotic regime can mask some logarithmic and constant factors which are relevant when choosing parameters in finite dimension. When constructing an LWE-based cryptosystem, the choice of parameters should take into account the complexity of the fastest known algorithm that resolves LWE, and ensure that the attack requires a prohibitively large number of operations in order to provide a well-defined security bound.

There are many algorithms to consider in general such as BKW attacks [KF15, HKM18, BGJ + 20] and the Arora-Ge algorithm (linearization attack) [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] that proposed a new algebraic technique for solving LWE. The latter algorithm has a total complexity (time and space) of 2 Õ(σ 2 ) . This implies that taking a small modulus q in LWE-based cryptosystems would trigger an LWE attack. In fact, choosing a small modulus requires taking small values of σ in order to guarantee a correct decryption. These attacks are generally exhaustive search attacks; there exist other types of attacks via lattice reduction. The exhaustive search strategies solve LWE by directly finding a vector s for which As is close to b in terms of Euclidean distance, and require an exponential number of LWE samples. Lattice reduction attacks require a polynomial number of samples and can be divided in two categories: Primal attack and Dual attack. These two attacks use efficient lattice reduction algorithms such as the BKZ algorithm [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF][START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] with block-size b, which requires up to polynomially many calls to an SVP oracle in dimension b, but some heuristics allow to decrease the number of calls to be essentially linear [START_REF] Chen | Lattice reduction and concrete security of fully homomorphic encryption[END_REF]. A brief description of these attacks is given below. That's why dim (Ker (A )) = n + 1, which means that there are q n+1 integer solutions in the cube of side q. Hence, the volume of Λ is q m . Moreover, Λ has a unique-SVP solution v = (s, e, 1) of norm ≈ σ √ n + m, where σ is the standard deviation of the noise. The integer m represents the number of used LWE samples that is usually bounded by poly(n)

and can be optimized numerically.

Using the typical models of BKZ (geometric series assumption, Gaussian heuristic [Che13, APS15]), one can derive the success condition for the primal attack, which is is satisfied if

and only if σ √ b ≤ δ 2b-d-1 • q m/d , where δ = (πb) 1/b • b/(2πe) 1/(2b-2)
.

The BKZ algorithm can now search for the unique solution using the resulting value b of the block dimension.

• The dual attack [AAB + ] consists in finding a short vector inside the dual lattice

L * = (v, w) ∈ Z m × Z n : v T A = w T mod q
in order to solve the decision version of the problem. This lattice is of dimension d = n+m, volume q n and generated by the rows of the basis matrix

B =   qI n 0 A mod q I m   .
As above, the BKZ algorithm with block size b will output such a short vector of length δ d-1 q n/d . The dual attack then uses this vector as a distinguisher for LWE. In fact, given a short pair (v, w) one can compute

z = v T b mod q = v T (As + e) mod q = w T s + v T e mod q.
If (A, b) is an LWE sample, this is distributed as a discrete Gaussian of standard deviation σ||(v, w)|| and often returns small samples. If b is uniform modulo q, then z is also uniform modulo q.

As mentioned above, the BKZ algorithm calls SVP several number of time. This number of calls is hard to estimate but it is polynomial, so one can give a conservative estimate of the cost of the primal and dual attacks by considering a single call to SVP, which is called the core SVP hardness [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF].

Enumeration and sieve algorithms discussed in Subsection 2.2.2 are used to implement the SVP oracle used by BKZ. The main idea of lattice enumeration is to systematically enumerate all lattice points in a bounded region of space. On the other hand, the sieve algorithms perform some kind of randomized enumeration of a smaller set. Asymptotically, enumeration is superexponential, while sieve algorithms are known to run in exponential time. Consequently, we choose the latter to predict the cost of solving SVP and will argue that for the targeted dimension, enumerations are expected to be greatly slower than sieving.

Classical lattice sieve algorithms [MV10, NV08] have been improved in terms of complexity from 2 0.415b down to 2 0.292b [START_REF] Becker | New directions in nearest neighbor searching with applications to lattice sieving[END_REF][START_REF] Laarhoven | Sieving for shortest vectors in lattices using angular locality-sensitive hashing[END_REF]. With a quantum computer, it would be possible to reduce the complexity of lattice sieve algorithms to 2 0.265b [START_REF] Laarhoven | Search problems in cryptography: From fingerprinting to lattice sieving[END_REF][START_REF] Laarhoven | Finding shortest lattice vectors faster using quantum search[END_REF]. Moreover, all of them depend upon classically building lists of size 2 0.2075b , which makes it uncertain whether one could build a quantum SVP algorithm that performs in time better than 2 0.2075b . This running time gives a plausible estimate of the cost of the best attack.

Reduction to BDDwDGS. The choice of the error distribution for LWE will be reduced to the choice of its "width". As we saw in Theorem 3.1, when the standard deviation σ of the discrete Gaussian is greater than 2/π √ n, then an appropriate quantum reduction from GapSVP γ and SIVP γ to LWE is established in the worst-case, with γ = Õ(n/α). The value of σ can be improved

to any σ > 1 2π √ n as [N + 20] mentioned out.
The security of FrodoKEM is based on a reduction from a variant of the worst-case boundeddistance decoding (BDD) problem to LWE that supports a smaller error width (i.e. σ <

1 2π √ n).
This variant called bounded-distance decoding with discrete Gaussian samples (BDDwDGS) requires a discrete Gaussian sampler over the dual lattice. A formal definition is given below.

Definition 3.4 (BDD with discrete Gaussian samples (BDDwDGS Λ,d,r ) [N + 20]). Let Λ be an n-dimensional lattice with d < λ 1 (Λ)/2 and let r > 0. The BDD with discrete Gaussian samples is defined under two hypotheses:

• A target point t ∈ R n such that dist(t, Λ) ≤ d
• Having access to an oracle that samples from D Λ * ,s for any adaptively queried s ≥ r.

The goal is to output the closest lattice point to t.

Note that in this case the parameter s for D Λ * ,s has the ability to vary, while the existing There is a probabilistic polynomialtime (classical) algorithm that, given access to an oracle that solves DLWE n,m,q,α with nonnegligible advantage and input a number α ∈ (0, 1), an integer q ≥ 2, a lattice Λ ∈ R n , and a parameter r ≥ Cq • η (Λ * ), solves BDDwDGS Λ,d,r , using N = m • poly(n) samples, where

d = 1 -1/C 2 • αq/r.
We note here that the BDDwDGS problem hasn't been as extensively studied as SIVP, and the known approaches to solving BDDwDGS are limited when

d > 1 r ln N/(2π) [AR05, LLM06, DRSD14]. In particular, if αq ln N/2π, (3.1)
then the BDDwDGS problem is plausibly hard in the worst case. In terms of efficiency, the main operations in the FrodoKEM protocol require a matrixvector product modulo a power-of-two integer q yielding a straightforward modular arithmetic implementation that is resistant to timing attacks.

FrodoKEM

Presentation of the algorithm

Our discussion in this section will mainly focus on FrodoPKE that will be used as a building block for FrodoKEM. FrodoPKE is designed to guarantee IND-CPA security at three levels:

Frodo-640, Frodo-976 and Frodo-1344. The corresponding message space is M = {0, 1} 64B for B ∈ {2, 3, 4} which depends on the chosen level. Each level is parameterized by an integer dimension n such that n ≡ 0 mod 8, a standard deviation σ and a discrete error distribution χ Frodo which is close to the rounded Gaussian Ψ σ √ 2π in Rényi divergence (see Table 3.2). The LWE modulus q is a power-of-two integer such that q ≤ 2 16 . A sketch of the FrodoPKE protocol is given in Table 3.1. Parameters: q; n ∈ {640, 976, 1344}; n = 8; B ∈ {2, 3, 4} FrodoKEM's distribution χ Frodo Alice (server) Bob (Client) for j=0 to 7 do

A $ ← -Z n×n q S, E ← -χ n×n Frodo S , E ← -χ n×n Frodo , B := AS + E ∈ Z n×n q (A,B) ----→ E ← -χ n×n Frodo U := S A + E ∈ Z n×n q V := S B + E ∈ Z n×n q m $ ← -{0, 1} 64B V := C -US ∈ Z n×n q (U,C) ← ----C = V + Frodo.Encode(m) m = Frodo.Decode(V )
3: k ← B-1 l=0 k (8i+j)B+l • 2 l 4: K i,j ← ec(k) = k • q/2 B 5: return K = (K i,j ) 0≤i≤7 0≤j≤7 Algorithm 3 Frodo.Decode Input: Matrix K ∈ Z 8×8 q Output: Bit string k ∈ {0, 1} , = B • 64 1: for i=0 to 7 do 2:
for j=0 to 7 do

3: k ← dc (K i,j ) = K i,j • 2 B /q mod 2 B 4: k = B-1 l=0 k l • 2 l where k l ∈ {0, 1} 5: for l = 0 to B -1 do 6: k (8i+j)B+l ← k l 7: return k
The algorithms above use the encoding function ec : Z 2 B → Z q and the decoding function dc : Z q → Z 2 B defined as follows:

ec : k → k • q 2 B and dc : c → c • 2 B q mod 2 B
One can easily verify that dc (ec(k)) = k.

Reliability and bandwidth

The decryption error probability of FrodoPKE is P e = P{m = m}. The value of V before decrypting it with the function Frodo.Decode(•) can be simplified as follows:

V = V + Frodo.Encode(m) -S A + E S (3.2) = S B + E + Frodo.Encode(m) -S AS -E S = S (AS + E) + E + Frodo.Encode(m) -S AS -E S = Frodo.Encode(m) + S E + E -E S E Hence, m = Frodo.Decode V = Frodo.Decode Frodo.Encode (m) + E . (3.3)
The following Lemma was proven in [N + 20] and shows that whenever the entries of E are small enough, the expression of m is simply the original message m.

Lemma 3.1. Let e ∈ -q 2 B+1 , . . . , q

Proof.

dc(ec(k) + e) = (ec(k) + e) • 2 B q mod 2 B = k q 2 B + e • 2 B q mod 2 B = k + e 2 B q mod 2 B But -q 2 B+1 < e < q 2 B+1 implies that -1 2 < e 2 B q < 1 2 , so k + e 2 B q = k. Corollary 3.1. Let K ←-Frodo.Encode (•) and E ∈ Z 8×8 q
such that each entry of E is in the intervalq 2 B+1 , . . . , q 2 B+1 , then, Frodo.Decode(K + E) = Frodo.Decode(K).

Proof. This follows from Lemma 3.1. and the fact that Frodo.Decode uses dc (K i,j + E i,j ) in the third line of Algorithm 3, where K i,j ←-ec in Algorithm 2.

From Corollary 3.1 we deduce that Frodo.Decode(V ) is equal to m if each entry of E is inq 2 B+1 , . . . , q 2 B+1 . Due to matrix multiplication, each entry of E is the sum of 2n products of two independent samples from χ Frodo and one more independent sample from χ Frodo . The support of χ Frodo is rather small (see Table 3.2), and hence the distribution of the product with itself can be efficiently computed. Moreover, the distribution of the sum of such 2n terms, as well as the additional error term, is obtained by applying the standard convolution approach.

The overall error probability is given by

P e ≤ 0≤i,j<8 P E i,j / ∈ - q 2 B+1 , . . . , q 2 B+1 .
We note that FrodoKEM admits the same failure probability as the underlying FrodoPKE as computed in Subsection 3.3.2.

In FrodoKEM, the transmitted information between Alice and Bob is compressed using 3.1 to a bit string of length log(q) • n • n and log(q) • n • n respectively. For example in Frodo-640, the ciphertext size is 15 × 640 × 8 + 15 × 8 × 8 = 82944 bits = 9720 bytes.

Security

In [N + 20] the security of the FrodoKEM protocol is evaluated with respect to three criteria:

IND-CPA security for FrodoPKE, IND-CCA security for FrodoKEM as well as concrete security against known attacks. We provide a brief summary of this security analysis.

IND-CPA security for FrodoPKE. The public-key encryption scheme FrodoPKE is considered IND-CPA secure assuming the hardness of decision-LWE. The proof follows the steps in [START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF]. Informally speaking, the idea is to prove that for any encrypted message m, the adversary cannot distinguish a communicated information which appears clearly to the public from uniformly random. First of all by looking at Table 3.1, the public key (A, B) is computationally indistinguishable from a uniform one (A, B * ) assuming the hardness of decision-LWE (see Definition 3.2). Moreover, the matrices U and V are likewise indistinguishable from uniformly random matrices U * and V * for the same reason. This implies that C = V + Frodo.Encode(m) is also indistinguishable from uniform using the following lemma:

Lemma 3.2. Let G be a finite group and b ∈ G a fixed element. Taking uniformly random elements a ∈ G implies that a + b will also be uniformly distributed in G.

So as a result, the pair (U, C) is indistinguishable from uniform.

In order to give a concrete bound on the advantage Adv IND-CPA FrodoPKE , a combination of both Theorem 5.9 and Theorem 5.10 in FrodoKEM [N + 20] leads to the following final result: Theorem 3.3 (Uniform-secret DLWE =⇒ IND-CPA security of FrodoPKE). Let n, q, n, k be positive integers with q ≥ 2 a power-of-two, and let Ψ s>0 be a probability distribution on Z. There exist classical algorithms B 1 , B 2 that use any quantum or classical algorithm A that attacks the IND-CPA security of FrodoPKE as a "black-box" subroutine in order to provide the following advantage:

Adv IND-CPA FrodoPKE (A) ≤ n • Adv DLWE n,2n+k,q,Ψs B 1 + n • Adv DLWE n,2n+n+k,q,Ψs B 2 + 2 • 2 -k ,
where k is some security parameter such that 2 -k is negligible. The running times of B 1 and B 2 are approximately that of A. ). Let PKE X = (Gen; Enc; Dec) be a δ-correct public-key encryption scheme with message space M that is parameterized by a distribution X, and let t be an upper bound on the total number of samples drawn from X by Gen and Enc combined. Let G 1 , G 2 and F be independent random oracles, and let KEM ⊥ X = FO ⊥ (PKE X , G 1 , G 2 , F ) be the KEM obtained by applying the FO ⊥ transform from Definition 2.21 to PKE X . Let P , Q be any discrete distributions. There exists a classical algorithm (a reduction) B against the IND-CPA security of PKE Q , which uses as a "black box" subroutine any A against the IND-CCA security of KEM ⊥ P that makes at most q RO oracle queries, for which

IND-CCA security for

Adv IND-CCA KEM (A) ≤ q RO |M| + 2•q RO +1 |M| + q RO • δ + 3 • Adv IND-CPA PKE • e t•Dα(P ||Q) 1-1 α (3.4)
The total running time of B is about that of A plus the time needed to simulate the random oracles.

The bound in (3.4) is generic and can be applied to any PKE scheme with its transformation KEM.

Drawbacks of the FrodoKEM protocol

The plain-LWE scheme FrodoKEM was selected as an alternate candidate for the NIST challenge which may provide better longer-term security guarantees since it has the least amount of structure and thus less susceptible to algebraic attacks. From the NIST's perspective, although

FrodoKEM can be used in the event that new cryptanalytic results targeting structured lattices emerge, the first priority for standardization is a KEM that would have acceptable performance across widely used applications. With regards to FrodoKEM, the cost of the high security feature is paid for by a much worse performance on all metrics compared to other lattice schemes (see Figures 3.1 and 3.2), and so the protocol must be improved further before it is suitable for standardization. In particular, the communication bandwidth required by the protocol is too large and should be reduced. Moreover, increasing its security level against known attacks would give FrodoKEM a better security margin to resist enhanced computing power in the future. In fact, although the current security estimate is already greater than the brute-force security, the plausible security is not and should be improved in order to prevent future attacks.

Error correction for FrodoKEM: state of the art. A modification of FrodoKEM has been proposed in [L + 19] using Gray labeling and error correcting codes in order to improve the performance. However, the decryption failure analysis in [L + 19] assumes that the coefficients of the error are independent. Unfortunately this assumption does not hold for FrodoKEM, and as

shown in [START_REF] Anvers | The impact of error dependencies on Ring/Mod-LWE/LWR based schemes[END_REF], it can lead to underestimating the decryption failure by a large exponential factor.

Error correction for FrodoKEM using the Gosset lattice

In this section, we propose our modified version of FrodoKEM which provides improvements in bandwidth, private key size or plausible security, depending on the chosen parameters. The new encoder maps the message m into a suitably scaled version of the 64-dimensional lattice (E 8 ) 8 , i.e., the product of 8 copies of the Gosset lattice. This lattice has been used before to improve the performance of lattice-based KEMs [START_REF] Zhao | A modular and systematic approach to key establishment and public-key encryption based on LWE and its variants[END_REF][START_REF] Jin | AKCN-E8: Compact and Flexible KEM from Ideal Lattice[END_REF] We choose E 8 since it gives the densest 8-dimensional packing, resulting in a more efficient decoding, and also admits a lowcomplexity optimal decoding (see Subsection 2.2.3). Since all integer operations in FrodoKEM are performed modulo q, we identify the lattice points that are equivalent modulo qZ 64 .

Improving performance using error correction

Our main modification focuses on the FrodoPKE encryption scheme, and the resulting adjustments to FrodoKEM will be discussed later.

Referring to Table 3.1, the main changes in our modified protocol are made in the encryption and decryption algorithms Frodo.Encode(•) and Frodo.Decode(•) respectively. Following the approach in [vP16], we search for a suitable scaling parameter β such that

qZ 64 ⊆ (βE 8 ) 8 ⊆ Z 64 . (3.5)
The first inclusion is required because we identify points that are equivalent modulo q, while the second one is required because all computations in FrodoKEM are done with integer coefficients.

The scalar β is examined in the following. Our aim is to choose the scaling parameter β that verifies condition (3.5) knowing that 2Z 8 ⊆ E 8 ⊆ 1 2 Z 8 , so as to obtain an injective function from {0, 1} to (βE 8 ) 8 /qZ 64 ⊆ Z 8×8 q . In order for such an injective function to exist, the number of points in (βE 8 ) 8 /qZ 64 must be greater or equal to 2 . This can be translated into the following volume condition:

Vol

qZ 64 Vol ((βE 8 ) 8 ) ≥ 2 ⇐⇒ q 64 β 64 ≥ 2 ⇐⇒ β ≤ q/2 /64 .
Clearly, it is better to choose β satisfying the equality β = q/2 /64 since this value yields the best possible minimum distance in the output lattice and thus the best error correction. Note that in this case, each element in βE 8 /qZ 8 is now identified with the corresponding coset leader in E 8 /2 /64 Z 8 .

If we consider the three security levels of FrodoKEM, must be in {128, 192, 256}, which implies β = q/2 /64 ∈ {q/4, q/8, q/16}. The construction of the encoder proceeds as follows.

First, m ∈ {0, 1} is partitioned into 8 substrings m i ∈ {0, 1} /8 , i = 0, . . . , 7. Each substring is mapped into the set E 8 /2 /64 Z 8 of cardinality 2 /8 , so that the whole message is mapped into

E 8 /2 /
                   f (b) = [b 1 , . . . , b 7 , -1] • G E 8 mod 2 if b 1 = 0 && b 8 = 0 f (b) = [b 1 , . . . , b 7 , 0] • G E 8 mod 2 if b 1 = 0 && b 8 = 1 f (b) = [b 1 , . . . , b 7 , 1] • G E 8 mod 2 if b 1 = 1 && b 8 = 0 f (b) = [b 1 , . . . , b 7 , 2] • G E 8 mod 2 if b 1 = 1 && b 8 = 1
A simple Matlab simulation shows that f is a bijective function. As an example, for = 128, the value of β is q/4. Hence mapping 8 bits of information into E 8 /2Z 8 allows to map 16 bits into E 8 /4Z 8 , which is extended to q 4 E 8 /qZ 8 in the standard way by multiplying by q/4. We can map 16 bits into the quotient E 8 /4Z 8 as follows: map the first 8 bits into E 8 /2Z 8 using f , and the remaining ones into 2Z 8 /4Z 8 . This last mapping is obtained by simply multiplying the input string by 2. This example can be extended to the cases = 192 and = 256 by considering the chain E 8 ⊇ 2Z 8 ⊇ 4Z 8 ⊇ 8Z 8 ⊇ 16Z 8 . We denote the function that maps the remaining /8 -8 bits by g and can be defined as follows: The function g is bijective and the inverse g -1 can be obtained by

          
           g -1 (y) = y 2 ∈ {0, 1} 8 if = 128 g -1 (y) = y mod 4 2 || y-y mod 4 4 ∈ {0, 1} 16 if = 192 g -1 (y) = y mod 4 2 || y mod 8-y mod 4 4 || y-y mod 8 8 ∈ {0, 1} 24 if = 256
The encoding function Frodo.Encode(•) can now be changed to E8.Encode(•) as shown in Algorithm 4. Moreover, as a result, each substring m i ∈ {0, 1} /8 is mapped into a vector in βE 8 /qZ 8 ⊆ Z 8 q that corresponds to a diagonal block of the output matrix O. In fact, each diagonal block is equal to the 8-dimensional row-vector S i that can be expressed as Block i (O) = (O i mod 8,0 , O i+1 mod 8,1 , . . . , O i+7 mod 8,7 ) , i = 0, . . . , 7.

Algorithm 4 Encoding bits into βE 8 /qZ 8 8

Input: m = (m 0 , . . . , m -1 ) ∈ {0, 1} Output: O ∈ βE 8 /qZ 8 8 ⊆ Z 8×8 q 1: function E8.Encode(m)

2:

for i=0 to 7 do 3: m i = (m i( /8) , m i( /8)+1 , . . . , m i( /8)+ /8-1 ) ∈ {0, 1} /8 4:

X i = f (m i,0 , . . . , m i,7 ) ∈ E 8 /2Z 8
Encoding the first 8 bits of m i 5:

X i = g(m i,8 , . . . , m i, /8-1 ) ∈ 2Z 8 /2 /64 Z 8
Encoding the remaining bits of m i 6:

S i = X i + X i ∈ E 8 /2 /
Input: N ∈ R 8×8 q Output: m = (m 0 , . . . , m -1 ) ∈ {0, 1} 1: function E8.Decode(N) 2:
for i=0 to 7 do 3:

Y i = β • CVP E 8 1 β Block i (N) mod q 8-dimensional
O i,j = Y (8-i+j) mod 8,j Y i,j is the j-th component of Y i 6: return m = E8.Encode -1 (O) ∈ {0, 1}
Remark 3.1. A discussion of the efficiency of those algorithms is given in Appendix B.1.

Error distribution

As in the FrodoKEM specifications, we use a discrete and symmetric error distribution χ on Z, centered at zero and with finite support {-s, . . . , s}, which approximates a rounded Gaussian distribution with standard deviation σ. In our case, χ is generated for different values of σ, and the support {-s, . . . , s} depends on the chosen σ value. Sometimes the support is taken to be the same as for the rounded Gaussian, and sometimes it is narrowed (to allow fast simulations), keeping a small Rényi divergence with respect to the rounded Gaussian.

Given the target standard deviation σ, we first construct a function χ on {-s, . . . , s} ⊆ Z from 2 16 samples as follows:

∀i ∈ {-s, . . . , s}, χ(i) = 1 2 16 2 16 • [i-1 2 ,i+ 1 2 ] D σ √ 2π (x)dx .
The distribution χ is obtained from χ by making small changes in the numerator values of χ(i) in order to obtain a probability distribution The sampling algorithm for such a distribution is

given in [N + 20, Algorithm 5]. Note that it is possible to perform this sampling in constant time in order to avoid cache and timing side-channels attacks. We compute the Rényi divergence of χ from the rounded Gaussian Ψ σ √ 2π via the script scripts/Renyi.py in [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]. Explicit examples for our chosen distributions are given in Subsection 3.4.4.

Reliability analysis

In this section we aim to provide an upper bound for the decryption error probability for our algorithm. Clearly, an error occurs whenever the received message m differs from the original one m, i.e., P e = P {m = m }. From Table 3.1 and following equation (3.2), the expression of V can be simplified as Each entry E i,j in the matrix E is the sum of 2n products of two independent samples from χ, adding to it another independent sample also from χ:

V = E8.Encode(m) + S E + E -E S E . ( 3
∀ 0 ≤ i, j ≤ 7, E i,j = n-1 k=0 S i,k E k,j -E i,k S k,j + E i,j (3.8)
The distribution of E i,j , denoted by χ , can be efficiently computed (see Appendix B.2.1) using the product of probability generating functions explicitly defined in Appendix A.1. From equation (3.8), it is easy to see that two entries of the matrix E which are not on the same row or column are independent, and hence we can extract 8 identically distributed blocks of 8 independent coordinates from this error matrix as represented below. Decoding is correct whenever E8.Decode (E ) = 0. For this it is sufficient to have

E =                 E 0,0 E 0,1 E 0,2 E 0,3 E 0,4 E 0,5 E 0,6 E 0,7 E 1,0 E 1,1 E 1,2 E 1,3 E 1,4 E 1,5 E 1,6 E 1,7 E 2,0 E 2,1 E 2,2 E 2,3 E 2,4 E 2,5 E 2,6 E 2,7 E 3,0 E 3,1 E 3,2 E 3,3 E 3,4 E 3,5 E 3,6 E 3,7 E 4,0 E 4,1 E 4,2 E 4,3 E 4,4 E 4,5 E 4,6 E 4,7 E 5,0 E 5,1 E 5,2 E 5,3 E 5,4 E 5,5 E 5,6 E 5,7 E 6,0 E 6,1 E 6,2 E 6,3 E 6,4 E 6,5 E 6,6 E 6,7 E 7,0 E 7,1 E 7,2 E 7,3 E 7,4 E 7,5 E 7,6 E 7,7                
Block k (E ) ∈ V (βE 8
) for all k = 0, . . . , 7, i.e.,

Block k E , v < v 2 2 2 , ∀v ∈ β VR (1) E 8 ∪ VR (2) E 8 ,
where the sets VR

(1) E 8 and VR

(2) E 8 refer to the two types of Voronoi relevant vectors for E 8 (see Subsection 2.2.3). The error probability can thus be bounded by

P e ≤ 2 j=1 7 i=0 P ∃ v j ∈ VR (j) E 8 : Block k E , v j ≥ β v j 2 2

2

(3.9)

Since the error probability is independent of the choice of Voronoi relevant vector for vectors of the same type (because the distribution of each entry of E is symmetric, centered at 0), without loss of generality we can choose v 1 = (1, 1, 0, 0, 0, 0, 0, 0) and

v 2 = ( 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1
2 ). This reduces the computations to just two cases. Choosing the value of n and the modulus q, we can compute an upper bound for the above expression for different values of σ. Recalling that VR

(1)

E 8 =

and VR

(2) E 8 = 128, equation (3.9) becomes:

P e ≤ 8 • 112 • P E 0,0 + E 1,1 ≥ β + 8 • 128 • P E 0,0 + • • • + E 7,7 ≥ 2β .
(3.10)

In order to upper bound P e , we use the following.

Remark 3.2. We say that a discrete distribution p taking values in Z is unimodal with mode 0 if p(n + 1) ≤ p(n) ∀n ≥ 0, and p(n + 1) ≥ p(n) ∀n < 0.

Note that the convolution of two symmetric discrete unimodal distributions is symmetric unimodal [DJD88, Theorem 4.7].

Since the distribution χ is symmetric unimodal, so are the distributions χ 2 , χ 4 , χ 8 of the sum of two, four and eight independent copies of E i,j respectively. While χ 2 and χ 4 can be calculated efficiently, the computation of χ 8 is slow. Thanks to unimodality, we can estimate the term P E 0,0 + • • • + E 7,7 ≥ 2β by upper bounding χ 8 by a piecewise constant function after computing a small number of values. Details are illustrated in Appendix B.2.2 and the error probabilities for the chosen parameters will be presented in Subsection 3.4.4.

Performance comparison

In this section we propose three sets of parameters: the first aims at improving the security level, the second at reducing the bandwidth and the third at increasing the private key size. We

show the impact of the proposed modification of FrodoKEM in terms of the performance of the protocol. Note that for all sets of parameters, n and n will remain unchanged.

In terms of security against known attacks, our analysis focuses on the dual and primal attacks, which are more relevant for polynomial number of LWE samples as in our case. Table 3.7 represents the concrete security bounds calculated via the FrodoKEM script pqsec.py (including parameters n, σ, q) with regard to classical, quantum and plausible attacks for the different parameter sets, compared to the original FrodoKEM.

The communication requirements regarding the protocol are computed using the functions

Frodo.Pack and Frodo.Unpack presented in [N + 20, Algorithm 3, Algorithm 4]. In our case we pack both U ∈ Z n×n and C ∈ Z n×n . Those two vectors, concatenated together, carry about (log(q) × n + log(q) × 8) bytes.

Parameter set 1 -Improving the security level. For the first parameter set (see Table 3.7), we aim at increasing the plausible security level while keeping the same bandwidth and a similar error probability level as in the original FrodoKEM protocol. The security level of FrodoKEM with respect to primal/dual attacks (see Paragraph 3.2) is already higher than the brute force security level, but this might change due to improvements in the best known attacks.

So this choice of parameters represents an even more conservative option for long-term security.

In order to increase the security, we increase the variance σ while keeping q unchanged. Note that we can increase σ because of the higher error correction capability provided by our modified encoder. The error distribution χ corresponding to each level is presented in Table 3.5.

As shown in Table 3.7, compared to the original versions of FrodoKEM, the plausible security level is increased by 7 bits, while the error probability is slightly improved.

Parameter set 2 -Reducing the bandwidth. For the second set of parameters in Table 3.7, we aim at reducing the bandwidth while keeping the same security level. This is achieved by reducing the modulus q by half, which in turn requires a reduction in standard deviation σ in order to preserve a low error probability3 (see Parameter set 3 -Increasing the private key size. For the last set of parameters in Table 3.7, we aim to increase the private key size compared to original FrodoKEM with comparable security and error probability. We generate 192 bits from Frodo-640 instead of 128 bits, as well as 256 bits instead of 192 bits in Frodo-976 with lower bandwidth requirements. The modulus q remains unchanged. Regarding Frodo-1344, increasing the private key size above 256 bits is not required by NIST cryptography standards.

IND-CPA / IND-CCA security

IND-CPA security. The proposed modifications in our scheme affect the choice of parameters q and σ, the error distribution and the encoding and decoding functions. As already discussed in Subsection 3.3.3, the IND-CPA security proof of the FrodoPKE protocol relies on the pseudorandomness of the adversary's observation, and the advantage of an attacker is given in Theorem 3.3. We can use the same argument for our modified protocol. This shows that the choice of encoding function has no effect on the security level, which is only affected by the parameters and error distribution. In particular for parameter sets 1 and 2, the modulus-tonoise ratio is reduced compared to the original FrodoKEM (see Table 3.7), and hence Adv DLWE in Theorem 3.3 is not increased (see Corollary 3.2 in [BLP + 13]). In fact, referring to parameter set 1, the improved security level requires a larger standard deviation σ, and therefore the Adv DLWE doesn't increase. Also, regarding parameter set 2, we note that a slightly lower standard deviation is applied while reducing the modulus q by half, which also means that our

Adv DLWE is decreased compared to FrodoKEM. In contrast, for Parameter set 3, the increase in private key size comes at the cost of an increased modulus-to-noise ratio (since the error width is decreased and q is unchanged). This means that Adv DLWE will be increased compared to the original FrodoKEM.

IND

Conclusion

In this chapter we used the β-scaled version of the 64-dimensional lattice (E 8 ) 8 in order to modify the underlying public-key encryption scheme for FrodoKEM [N + 20]. Our encoding function creates first a bijection between {0, 1} 8 and E 8 /2Z 8 which can be extended to a bijection from {0, 1} to (βE 8 ) 8 /qZ 64 . In addition, we modify the standard deviation σ of the error distribution and the modulus q depending on the chosen security level and the improvement we aim to make, keeping the error probability unchanged compared to FrodoKEM. Moreover, we preserve the same matrix dimensions n and n. The main improvements are classified between two sets of parameters and can be summarized as follows:

• The first set of parameters aims to improve plausible security against attacks on LWE. This is done by widening the standard deviation, or error width, keeping the same modulus q.

This results in an improvement of about 8% to 9% with respect to classical, quantum and plausible attacks. IND-CCA security remains unchanged, as does the bandwidth and the error probability bound.

• The second set of parameters is intended to improve the communication bandwidth. By halving the modulus q, we obtain a reduction of about 7% in terms of bandwidth, keeping the same bound for the error probability and a slightly enhanced plausible security.

• The last set of parameters increases the number of private key bits sent for both Frodo-640 and Frodo-976 from 128 to 192 bits and 192 to 256 respectively. This is paid for by a slight reduction in concrete security. In the final part of the chapter we will propose our own modification of KyberKEM by introducing a reconciliation technique.

Module Learning With Errors (M -LWE)

LWE has shown to be amazingly versatile, serving in the construction of cryptographic protocols and providing long-term high security against both chosen-plaintext and chosen-ciphertext attacks. Unfortunately, these protocols are often inefficient due to their large public key sizes (quadratic in dimension). This inspired the authors of [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] to develop a more efficient variant of LWE called Ring Learning With Errors (R-LWE). This variant has a more compact form due to its additional algebraic structure and offers many cryptographic applications including efficient signature schemes [Lyu12, MP12], fast encryption [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF], fast homomorphic encryption [GHS12, BGV14, BV11a] and pseudo-random functions [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF]. Solving R-LWE is at least as hard as solving approximate SIVP on ideal lattices -which correspond to ideals of the ring of integers R of a number field K.

Later, an extension of R-LWE based on module lattices, called Module Learning With Errors

(M -LWE), was proposed in [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF]. In fact, R-LWE can be seen as a special case of M -LWE where the module dimension is 1. Moreover, from the cryptographic construction viewpoint, most constructions based on R-LWE can be adapted to M -LWE with an efficiency slowdown bounded by a constant factor.

Cyclotomic rings and modules. Before introducing M -LWE, we need to introduce some background notions related to cyclotomic rings and modules. Let K = Q(ζ N ) be the N -th cyclotomic number field of degree n = ϕ(N ), where ζ N is any primitive N -th complex root of unity, e.g. ζ N = exp (2πi/N ). We consider the ring of integers R of K which can be explicitly expressed as R = Z[X]/(X n + 1). For any integer q ≥ 2, the quotient ring modulo q is defined as R q = Z q [X]/(X n + 1). We take N to be a power-of-two integer, and hence n = N/2 is also a power-of-two. Any element a ∈ R can be expressed as a = a 0 + a 1 X + • • • + a n-1 X n-1 for some integers a 0 , . . . , a n-1 . Using the naive "coefficient embedding" enables to identify a ∈ R with the vector (a 0 , . . . , a n-1 ) ∈ Z n . Given a ring R, an R-module is an additive Abelian group M endowed with a multiplication

function R × M → M such that ∀r, r ∈ R and ∀ #» m, # » m ∈ M , r( #» m + # » m ) = r #» m + r # » m , (r + r ) #» m = r #» m + r #» m, and r(r #» m) = (rr ) #» m.
In this thesis, we will consider the product R d which can be seen as an R-module with the multiplication r(r 0 , . . . , r d-1 ) = (rr 0 , . . . , rr d-1 ).

Given a discrete error distribution χ on Z, one can define an error distribution on the ring R as follows: if a ∈ R, the notation a ← χ means that a is a ring sample such that the coefficients a 0 , . . . , a n-1 are generated independently according to χ. Furthermore, a ddimensional vector -→ a = (a 0 , . . . , a d-1 ) ∈ R d can be generated according to the distribution χ d in which the coefficients a 0 , . . . , a d-1 are generated independently from χ. For -→ a = (a 0 , . . . , a d-1 ) and

- → b = (b 0 , . . . , b d-1 ) in R d , the dot product - → a , - → b is defined as - → a , - → b = d-1 i=0 a i • b i ∈ R,
where a i • b i is the multiplication operation on R.

Definition 4.1 (Decision Module Learning With Errors (M -LWE q,χ )). Let d be a positive integer parameter and R q = Z q [X]/(X n + 1) for some prime integer q ≥ 2. Let χ be a discrete distribution on R. The problem consists in distinguishing uniform random samples ( #»

a i * , b * i ) ← R d q × R q from samples ( #» a i , b i ) ← R d q × R q where #» a i ← R d q is uniform and b i = #» a i , #» s + e i with #» s ← χ d common
P      b = 1 A←R m×d q ( #» s , #» e )←χ d α ×χ m α #» b =A #» s + #» e b ←A(A, #» b )      -P b = 1 A←R m×d q #» b ←R m q b ←A(A, #» b )
where b = 1 is the output of the distinguisher A.

A reduction from approximate SIVP on the set of so-called module lattices to M -LWE has been shown to exist in [LS15, Theorem 4.7] for prime modulus q. Module lattices are a special class of lattices than can be obtained by embedding a module

M ⊆ K d into (R n ) d
, where K is a number field and d is a positive integer. We refer to the SIVP problem over module lattices as Module-SIVP.

Later, C. Peikert and Z. Pepin showed that given a number field extension K /K of degree r, where K and K have rings of integers R and R respectively, there exists a reduction from

M -LWE for M = (R ) d to M -LWE for M = R d , where d = rd (see [PP19, Theorem 6.1]).
Taking d = 1 and by using the results from [START_REF] Peikert | Pseudorandomness of ring-LWE for any ring and modulus[END_REF] on the hardness of Ring-LWE which hold for any q, this implies hardness of Module-LWE for general modulus q. A classical reduction from standard worst-case lattice problems to M -LWE with arbitrary polynomial-sized modulus q was also proven in [START_REF] Boudgoust | Towards classical hardness of module-lwe: The linear rank case[END_REF] provided that the module rank d is not smaller than the number field degree n.

A restricted variant of the SVP γ to ideal lattices has been widely studied in recent years, and recent works suggest that this problem may be easier to solve on an ideal lattices than on an arbitrary ones, contrary to what was previously believed. In [START_REF] Pellet-Mary | Approx-SVP in ideal lattices with pre-processing[END_REF] the authors introduce the PHS algorithm that solves SVP γ on ideal lattices with γ = 2 Õ(log ω+1 |∆ K |/n) , where ∆ K is the discriminant of K and ω is arbitrary in [0, 1/2]. This algorithm requires a pre-processing phase that runs exponentially in log |∆|, and a query phase that runs classically in time and space exp Õ (log |∆|) max(2/3,1-2ω) , while it is exp Õ (log |∆|) 1-2ω in the quantum setting. A twisted version which was proposed in [START_REF] Bernard | Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices[END_REF] seems to have better approximation factors in terms of practical implementation, while in theory it performs as well as the original PHS algorithm.

A proposition to apply the LLL algorithm on module lattices was given in [START_REF] Fieker | Short bases of lattices over number fields[END_REF] in order to find short vectors in polynomial time. This inspires the authors of [START_REF] Lee | An LLL algorithm for module lattices[END_REF] to construct an algorithm that efficiently finds short vectors in rank-2 modules given access to a CVP oracle for a lattice that is defined only in terms of K. Based on this, they also construct an algorithm that efficiently finds short vectors in rank-n modules when given access to an oracle that finds short vectors in rank-2 modules. This reduction is polynomial and runs in time log |∆ K |.

Parameters: n = 256; q = 3329 (k 1 , k 2 , d, b #» u , b v ) ∈ {(3, 2, 2
, 10, 4), (2, 2, 3, 10, 4), (2, 2, 4, 11, 5)} As we can see, additional parameters appear in the algorithm settings. For instance, k 1 and k 2 refer to the centered binomial width, while b #» u and b v are inputs to the compression and decompression functions in Definition 4.3 above. Those parameters are chosen to balance between security, ciphertext size, and failure probability, whereas the compression and decompression functions aim to reduce the communication requirements between Alice and Bob, while still guaranteeing a very small decryption failure probability. Using a similar notation as in Subsection 2.3.1, the algorithm proceeds as follows:

Alice (server) Bob (Client)

A $ ← -R d×d q #» s , #» e ← -Ψ d k 1 #» s ← -Ψ d k 1 , #» e ← -Ψ d k 2 e ← -Ψ k 2 #» b := A #» s + #» e ∈ R d q (A, #» b ) ----→ m $ ← -{0, 1} 256 #» u := A T #» s + #» e #» û = Decompress q Compress q ( #» u, b #» u ) , b #» u Compress q ( #» u ,b #» u ) ← ----------- Compress q (v,bv) v := #» b, #» s + e + q 2 m v = Decompress q Compress q (v, b v ) v := #» s , #» û ∈ R q m = Compress q (v -v , 1)
• Public parameter: Alice samples a uniform random matrix A from R d×d q which is referred to as the public parameter pp of the PKE.

• ( #» s , #» b) ← Gen(A): Alice chooses #» e , #» s ← Ψ d k 1 , computes #» b = A #» s + #» e ,
• ( #» u, v) ← Enc(A, #» b, m): Bob chooses independent #» s ← -Ψ d k 1 , #» e ← -Ψ d k 2 and e ← -Ψ k 2 , then computes #» u = A T #» s + #» e ∈ R d
q and compresses it using the Compress q function described in Definition 4.3. After generating the message m that needs to be encrypted,

Bob computes v = #» b, #» s + e + q
2 m and compresses it as well. He outputs c = ( #» u, v)

and forwards the compressed terms to Alice.

• m ← Dec ( #» s , c): Alice decompresses these terms into #» û and v respectively, then computes

v = #» s , #» û .
She recovers the message m by applying Compress q (vv , 1).

Reliability

This section provides a proof of the δ-correctness for KyberPKE following [BDK + 18], with an exponentially small decryption failure probability δ, depending on the selected parameters.

Table 4.2 contains the δ values for the three levels of KyberKEM. An important lemma for the analysis of the proof is given below.

Lemma 4.1 ( [N + 20]). Let mod ± denote the operation defined in Section 2.1, i.e., that produces values in the range that goes from the negative half excluded, to the positive half included. The compression and decompression functions in Definition 4.3 satisfy:

Decompress q Compress q (x, b) , b = x with x -x mod ± q ≤ q/2 b+1 .
Theorem 4.1. Let d be positive integer and #» s , #» e , #» s , #» e , e be distributed as in Table 4.1. Let #» c 1 and c 2 be distributed according to the following distribution:

1. Chose uniformly random #» y ← R d (or y ← R in case of c 2 ), 2. return #» y -Decompress q Compress q ( #» y , b) , b mod ± q.
Then KyberKEM is δ-correct where

δ = P #» e , #» s + e + c 2 -#» s , #» e -#» s , #» c 1 ∞ > q/4
Proof. During the decryption procedure, the vector #» û in Table 4.1 is recovered by applying

Decompress q Compress q ( #» u, b #» u ) , b #» u which leads to write #» û = A T #» s + #» e + #» c 1 for some #» c 1 ∈ R d . Furthermore, v = Decompress q Compress q #» b, #» s + e + q/2 • m, b v , b v = #» b, #» s + e + q/2 • m + c 2 = A #» s + #» e , #» s + e + q/2 • m + c 2
for some c 2 ∈ R. Note that the distribution of the terms #» c 1 and c 2 is indistinguishable from the distribution in the theorem statement. This is true because #» c 1 and c 2 are of the form y -Decompress q Compress q (y, b) , b mod ± q where y is pseudo-random based on the hard-ness of Module-LWE. Using the above we get:

v -#» s , #» û = #» e , #» s + e + c 2 -#» s , #» e -#» s , #» c 1 ω + q/2 • m
On the other hand, m = Compress q v -#» s , #» û , 1 . So decompressing from both sides we obtain

Decompress q m , 1 = q/2 m = Decompress q Compress q v -#» s , #» û , 1 , 1 which gives using Lemma 4.1 q/2 m -v -#» s , #» û ∞ ≤ q/2 2 ,
or equivalently,

ω -q/2 (m -m) ∞ ≤ q/4 .
Suppose that ω ∞ ≤ q/4 with probability 1 -δ. The triangular inequality yields

q/2 (m -m ) ∞ < 2 q/4 .
Since q is odd, this implies that m = m and hence the δ-correctness of the scheme.

The value of δ that corresponds to the probability that ω ∞ > q/4 is calculated via a Python script as indicated in [BDK + 18]. Table 4.2 illustrates the different values of δ for the three different KyberKEM levels.

n d q k 1 k 2 (b #» u , b v ) δ KyberKEM-

Security

The security of KyberKEM depends on the security of KyberPKE. In order to show IND-CCA security for the former, IND-CPA security must be demonstrated for the latter. The corresponding advantage is given in [BDK + 18, Theorem 2] and reformulated as follows:

For any IND-CPA adversary A, there exists a M -LWE adversary B such that

Adv IND-CPA KyberPKE (A) ≤ Adv M -LWE d+1,d,Ψ k 1 (B) + Adv M -LWE d+1,d,Ψ k 2 (B)
where the notation Adv Theorem 4.2 ( [BDK + 18]). For any classical adversary A that makes at most q RO many queries to G 1 and G 2 , there exists an adversary B such that

Adv IND-CCA KyberKEM (A) ≤ 3Adv IND-CPA KyberPKE (B) + q RO δ + 3q RO 2 256 (4.1)
where δ is the decryption failure probability of KyberPKE.

A security reduction can also be derived in the quantum random oracle model (see [A + 20, Subsection 4.3.2]) but it's not tight and therefore can only serve as an asymptotic indication of KyberKEM's CCA-security in the QROM.

Concrete security.

The concrete security of KyberKEM is analysed similarly to [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] by treating the M -LWE problem as a general LWE problem without taking the algebraic structure into account, since at present no attacks that exploit this structure are known. The best known attacks are the primal and dual attacks discussed in Section 3.2. Table 4.3 shows the concrete security bounds in log 2 scale as an example for the most well-known classical, quantum and plausible attacks.

Kyber with reconciliation

In this section we consider a key encapsulation mechanism based on Module-LWE using the reconciliation technique discussed in Section 1.2. Our protocol mainly focuses on modifying the three levels of KyberKEM, namely, KyberKEM-512, KyberKEM-768 and KyberKEM-1024, with the aim of improving their security level thanks to a better error correction.

Attack Known Classical Known Quantum Best Plausible KyberKEM-512: q = 3329, n = 256, We consider the cyclotomic ring of degree n = 256 as in KyberKEM. We use an 8-dimensional lattice for reconciliation in order to generate one bit of private key per dimension. As in Chapter 3, the chosen lattice is the Gosset lattice E 8 due to its optimal density and low-complexity quantization. We will show that our scheme can guarantee smaller error probability, smaller modulus and better security compared to the original first two levels at the price of a slightly increased bandwidth.

k 1 = 3, k 2 = 2, d =
In our modified version, we choose the modulus to be a power-of-two. In fact, by choosing q to be a prime number as in KyberKEM, one can use the NTT to speed up polynomial multiplication [PG13, Pei14, ADPS16b]. However, prime q is not required for security since the hardness of Module-LWE has been established for general modulus q (see discussion in Section of choosing an even q is that a dither is not required to obtain a uniform key with the reconciliation method, unlike [START_REF] Peikert | Lattice cryptography for the internet[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF].

Polynomial splitting

Before presenting the details of our reconciliation mechanism, we need to consider what is called polynomial splitting as in [ADPS16b, Section C]. This will be used to define our protocol as well as to analyze our error probability bound in later section.

Given an integer n 0 such that n = n 0 L, we take S = Z[Y ]/ (Y n 0 + 1). Given a polynomial a(X) ∈ R, we define for κ = 0, 1, . . . , L -1 the vectors a (κ) as:

a (0) = (a 0 , a L , a 2L , . . . , a n-L )
a (1) = (a 1 , a 1+L , a 1+2L , . . . , a 1+n-L ) a (2) = (a 2 , a 2+L , a 2+2L , . . . , a 2+n-L ) . . .

a (L-1) = (a L-1 , a 2L-1 , a 3L-1 , . . . , a n-1 )
Taking Y = X L allows to write a(X) = L-1 κ=0 a (κ) (Y )X κ . Accordingly, given two polynomials a(X) and b(X), one can express the multiplication a(X)b(X) as p(X)

:= a(X)b(X) = L-1 κ=0 p (κ) (Y )X κ in which p (κ) (Y ) = L-1 i=0 Y δ i,κ a (i) (Y ) • b (κ-i mod L) (Y ), (4.2)
where δ i,κ is either 0 or 1. In the sequel we omit the mod L operation to simplify notations.

Reconciliation mechanism for key generation

We present here our modified key encapsulation mechanism by adding a reconciliation step in order to improve the reliability of key agreement between Alice and Bob (see discussion in Section 1.2).

We show that our scheme can guarantee a smaller error probability than both KyberKEM-512 and KyberKEM-768, with a smaller modulus q = 2 11 , using 4 bits of reconciliation per dimension. For this choice of q, the post-quantum security is enhanced. Our protocol makes use of the following lattices of dimension n = 256: the quantization lattice Λ 1 = q 2 p E 8 32 for some integer p ≥ 1, the coding lattice Λ 2 = q 2 E 8 32 and the shaping lattice Λ 3 = q Z 8 32 . The purpose of the lattice Λ 1 is to quantize the reconciliation message in order to reduce the transmission requirements from Bob to Alice. The lattice Λ 2 is used for error correction, and the choice of the lattice Λ 3 corresponds to the fact that all operations in the protocol are performed modulo q. Since 2Z 8 ⊆ E 8 ⊆ 1 2 p-1 E 8 , this choice implies that Λ 3 ⊆ Λ 2 ⊆ Λ 1 .

Parameters: q = 2 11 ; n = 256; k 1 , k 2 ∈ {2, 3}; d ∈ {2, 3, 4} Alice (server) Bob (Client) A $ ← -R d×d q #» s , #» e ← -Ψ d k 1 #» s ← -Ψ d k 1 , #» e ← -Ψ d k 2 , e ← -Ψ k 2 #» b := A #» s + #» e ∈ R d q (A, #» b ) ----→ #» u := A T #» s + #» e ∈ R d q v := #» b, #» s + e ∈ R q ( #» u ,r) ← --- r = HelpRec(v) = Q Λ 1 (v) mod Λ 2 v := #» u, #» s ∈ R q k = Rec(v , r) = Q Λ 2 (v -r) mod Λ 3 k = Rec(v, r) = Q Λ 2 (v -r) mod Λ 3
Referring to Table 4.4, our protocol is the same as KyberPKE (Table 4.1) with regard to the generation of the public and secret keys, the generation of the error terms, as well as the calculation of v and the vector #» u. Since encryption is replaced by reconciliation, the message m (which in Table 4.1 was generated unilaterally at Bob's side) is now replaced by a private key k.

Note that we eliminate the use of the compression and decompression functions. We could have included a compression step, but decided against it because computing the decryption failure probability would have been too complicated.

Bob sends to Alice the pair c = (

#» u, r) ∈ R d q × Λ 1 /Λ 2 with r = HelpRec(v) := Q Λ 1 (v) mod Λ 2
being the reconciliation message. The private key k in Λ 2 /Λ 3 is such that Remark 4.1. When v ∈ R q , the notation Q Λ 1 (v) means that we perform Q q 2 p E 8 on each component v (κ) (see Subsection 4.4.3) where n 0 = 8 and L = 32. Similarly for Q Λ 2 (•), mod Λ 2 and mod Λ 3 operations.

k = Rec(v, r) := Q Λ 2 (v -r) mod Λ 3 .
The number of bits of the private key is calculated as

log |Λ 2 /Λ 3 | = log Vol(Λ 3 ) Vol(Λ 2 ) Vol(E 8 ) = 1 = log q 256 (q/2) 256 )
= 256, so that the protocol provides 256 bits of key. Furthermore, the number of reconciliation bits transmitted from Bob to Alice is

log |Λ 1 /Λ 2 | = log Vol(Λ 2 ) Vol(Λ 1 ) = log (q/2) 256 (q/2 p ) 256 ) = 256(p -1).
Remark 4.2 (Comparison with NewHope [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]). We remark that our protocol has a similar form to the reconciliation-based protocols in [START_REF] Peikert | Lattice cryptography for the internet[END_REF] and the first version of the NewHope

Reliability

In this section, we provide technical details on estimating the error probability P e = P{k = k}.

We will prove that in our described protocol, the parameter set we recommend in Table 4.4

yields P e < 2 -141 for KyberKEM-512 (with p = 6), P e < 2 -174 for KyberKEM-768 (with p = 5)

and P e < 2 -168 for KyberKEM-1024 (with a very large p).

Reliability condition According to Table 4.4, the two private keys k and k are identical whenever

Q Λ 2 (v -r) mod Λ 3 = Q Λ 2 v -r mod Λ 3 . (4.3) Setting e Q = v -Q Λ 1 (v)
we can show that a sufficient condition to achieve equation (4.3) is

Q Λ 2 ((v -v) + e Q ) = 0.
In fact, using properties (P1), (P2), (P3) or (P4) from Lemma 2.1, we can write

Q Λ 2 (v -r) (P 3) = Q Λ 2 (e Q + Q Λ 1 (v) -Q Λ 1 (v) + Q Λ 2 (Q Λ 1 (v))) (P3) = Q Λ 2 (e Q ) + Q Λ 2 (Q Λ 1 (v)) (P 3) = Q Λ 2 (Q Λ 1 (v)) , because e Q ∈ V(Λ 1 ) ⊆ V(Λ 2 );
and

Q Λ 2 v -r (P 3) = Q Λ 2 v -Q Λ 1 (v) + Q Λ 2 (Q Λ 1 (v)) (P3) = Q Λ 2 v + e Q -v + Q Λ 2 (Q Λ 1 (v)) .
We recall that the operation Q Λ 1 (•) when applied on x ∈ R 256 is actually Q q 2 p E 8 (•) applied on each component x (κ) (Remark 4.1). Similarly, the Q Λ 2 (•), mod Λ 2 and mod Λ 3 operations can be applied component-wise.

The condition Q Λ 2 ((v -v) + e Q ) = 0 is realized whenever Q q 2 1-1 2 p-1 E 8 (v -v ) (κ) = 0 for κ = 0, . . . , L -1. (4.4) In fact, =⇒∀κ = 0, . . . , L -1, Q q 2 1-1 2 p-1 E 8 (v -v ) (κ) = 0 =⇒ ∀κ = 0, . . . , L -1, (v -v ) (κ) ∈ V q 2 1 -1 2 p-1 E 8 =⇒ ∀κ = 0, . . . , L -1, (v -v ) (κ) -e (κ) Q ∈ V q 2 1 -1 2 p-1 E 8 + V q 2 p E 8 ⊆ q 2 V (E 8 ) =⇒ ∀κ = 0, . . . , L -1, Q q 2 E 8 (v -v ) (κ) -e (κ) Q = 0 ⇐⇒ ∀κ = 0, . . . , L -1, Q q 2 E 8 (v -v) (κ) + e (κ) Q = 0, because V q 2 E 8 has central symmetry =⇒ Q Λ 2 (v -v) + e Q = 0.
For clearer notations, we assign C := q 2 1 -1 2 p-1 . Let ω denote the error difference between v and v such that

ω = v -v = #» b, #» s + e -#» u, #» s = A #» s + #» e , #» s + e -A T #» s + #» e , #» s = #» s , A T #» s + #» e , #» s -A T #» s , #» s - #» e , #» s + e = #» e , #» s - #» e , #» s + e = e 1 • s 1 + • • • + e d • s d -e 1 • s 1 + • • • + e d • s d + e = ω 1 + ω 2 + • • • + ω d + e
where ω i = e i • s i -e i • s i for i = 1, . . . , d. This can be written in polynomial form as:

ω(X) = ω 1 (X) + ω 2 (X) + • • • + ω d (X) + e (X).
So for κ = 0, . . . , L -1 and using equation (4.2), the expression of ω (κ) (Y ) will be:

ω (κ) (Y ) = d j=1 L-1 i=0 Y δ i,κ e j (i) • s (κ-i) j (Y ) -e (i) j • s (κ-i) j (Y ) + e (κ) (Y ). (4.5)
As in [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF][START_REF] Ah Van Poppelen | Cryptographic decoding of the Leech lattice[END_REF], we will consider a union bound over all Voronoi relevant vectors. Note that ω (κ) (Y ) is still a polynomial with 8 coefficients. From condition (4.4), decoding will be correct if ω (κ) ∈ C • V(E 8 ) for all κ = 0, 1, 2, . . . , L -1. Referring to condition (2.2), ω (κ) ∈

C • V(E 8 ) ⇐⇒ ω (κ) , λ ≤ λ 2 2 2 , ∀λ ∈ C VR (1) E 8 ∪ VR (2)
E 8 , where VR

(1) E 8 and VR

(2) E 8 are defined in Subsection 2.2.3.

We mention that multiplying a vector a (i) (Y ) by Y is equivalent to a right shift so that the last term becomes the first one with a minus sign on it. In other words we can write

Y • a (i) (Y ) = Y • a i + a i+L Y + • • • + a i+n-L Y n 0 -1 = -a i+n-L + a i Y + • • • + a i+n-2L Y n 0 -1 .
Another thing to be mentioned is the conjugation function. Consequently, one can express the dot product of ω (κ) with λ ∈ C VR (1)

E 8 ∪ VR (2)
E 8 using the above definition and equation (4.5) as:

ω (κ) , λ = d j=1 L-1 i=0 Y δ i,κ e (i) j s (κ-i) j -e (i) j s (κ-i) j , λ + e (κ) , λ = d j=1 L-1 i=0 Y δ i,κ e (i) j • s (κ-i) j , λ -Y δ i,κ e (i) j • s (κ-i) j
, λ + e (κ) , λ

( * ) = d j=1 L-1 i=0 Y δ i,κ s (i) j • e (κ-i) j , λ -Y δ i,κ s (i) j • e (κ-i) j
, λ + e (κ) , λ can be identified with W λ,κ ≡ e (0) • λ, . . . , e (Ld-1) • λ , e (0) • λ, . . . , e (Ld-1) • λ , where each component e (i) • λ (and e (i) • λ) is a polynomial multiplication of an 8-dimensional vector e (i) (and e (i) ) by a Voronoi relevant vector λ. The multiplication is done modulo (Y 8 +1). Moreover, the e (i) s are independent with centered binomial coefficients, distributed also independently. For

( * * ) = d j=1 L-1 i=0 Y δ i,κ s (i) j , conj e (κ-i) j • λ -Y δ i,κ s (i) j ,
instance, if λ 1 ∈ C • VR (1)
E 8 is a Voronoi relevant vector of type 1, then W λ 1 ,κ is given by the general form

C • ±e (0) i 0 ± e (0) i 1 , . . . , ±e (Ld-1) i 2Ld-2 ± e (Ld-1) i 2Ld-1 , ±e (0) i 0 ± e (0) i 1 , . . . , ±e (Ld-1) i 2Ld-2 ± e (Ld-1) i 2Ld-1 . However, if λ 2 ∈ C • VR (2)
E 8 is a Voronoi relevant vector of type 2, then W λ 2 ,κ is of the form:

C 2 ±e (0) 0 ± • • • ± e (0) 7
, . . . , ±e

(Ld-1) 8Ld-8 ± • • • ± e (Ld-1) 8Ld-1 , ±e (0) 0 ± • • • ± e (0) 7
, . . . , ±e

(Ld-1) 8Ld-8 ± • • • ± e (Ld-1) 8Ld-1
.

Error probability calculations Recall that an error occurs if ω (κ) / ∈ C • V(E 8 ) for some κ = 0, . . . , L -1. So one can bound the decryption failure probability P e by P ∃κ ∈ {0, . . . , L -1}, ∃λ ∈ C VR

(1)

E 8 ∪ VR (2) E 8 : ω (κ) , λ > λ 2 2 2
Using the fact that ω (κ) , λ = (s , s), W λ,κ + e (κ) , λ we obtain:

P e ≤ L-1 κ=0 P ∃λ : (s , s), W λ,κ > λ 2 2 2 -e (κ) , λ (4.7)
Note that for λ ∈ C • VR The same way we prove that for type 2 vectors λ, ||λ|| 2 2 -e (κ) , λ ≥ C 2 -4k 2 C. It follows that we can bound each term by computing the distribution of (s , s), W λ,κ , which is a sum of 2Ld i.i.d. random variables of the form e (i) • λ. Details are discussed in Appendix C.2.

From our numerical simulations, we obtain the following table:

Security

Similarly to the original KyberKEM scheme, our modified scheme achieves IND-CPA security which is then transformed into IND-CCA security. In addition, we study security against known attacks, that is, concrete security.

Equivalence of Game 2 and

Proof. For fixed k, k ∈ Λ 2 /Λ 3 we define ∀ v ∈ R q π k,k (v) = v -k + k mod Λ 3 . Notice that π k,k (v) ∈ R q because (-k + k ) ∈ Λ 2 ⊆ Z n and hence π k,k (v) ∈ Z n
q . So π k,k is a permutation of R q by Lemma 2.2. The proof of Theorem 4.3 results from these lemmas:

Lemma 4.2. ∀ k, k ∈ Λ 2 /Λ 3 and ∀ v ∈ R q we have HelpRec(v) = HelpRec π k,k (v) .
Proof. The equalities below follow from the properties (P1), (P2), (P3) and (P4) cited in Lemma 2.1.

HelpRec π k,k (v) (P 2) = Q Λ 1 π k,k (v) mod Λ 2 (P 2) = Q Λ 1 v -k + k mod Λ 3 mod Λ 2 (P 2) = Q Λ 1 v -k + k -Q Λ 3 v -k + k mod Λ 2 (P3) = Q Λ 1 (v) -k + k -Q Λ 3 v -k + k mod Λ 2 (P2) = Q Λ 1 (v) mod Λ 2 = HelpRec(v). Lemma 4.3. Suppose that k = Rec(v, r) = Q Λ 2 (v -r) mod Λ 3 . Then ∀ k ∈ Λ 2 /Λ 3 we have k = Rec(π k,k (v), r).
Proof. As before, we will use the properties (P1), (P2), (P3) or (P4) from Lemma 2.1.

Rec(π k,k (v), r) (P 2) = Q Λ 2 v -k + k -Q Λ 3 v -k + k -r mod Λ 3 (P3) = Q Λ 2 (v -r) -k + k -Q Λ 3 v -k + k mod Λ 3 (P2) = Q Λ 2 (v -r) -k + k mod Λ 3 (P1) = Q Λ 2 (v -r) mod Λ 3 -k + k mod Λ 3 (P 2) = k -k + k mod Λ 3 (P 2) = k .
The Corollary below follows immediately from Lemma 4.2 and Lemma 4.3.

Corollary 4.1. ∀ k, k ∈ Λ 2 /Λ 3 and ∀ v ∈ R q , there exist v = π k,k (v) such that HelpRec(v) = HelpRec π k,k (v) , and k = Rec(v, r) ⇐⇒ k = Rec(π k,k (v), r).
We conclude the proof of Theorem 4.3 by showing that k is uniform and independent of r when v is uniform:

P{k | r} = v∈Rq P{v} • P{k | r, v} = v∈Rq 1 {r=HelpRec(v) , k=Rec(v,r)} • P{v} = v∈Rq 1 {r=HelpRec(π k,k (v)) , k =Rec(π k,k (v),r)} • P{v} = v ∈Rq 1 {r=HelpRec(v ) , k =Rec(v ,r)} • P{v } = v ∈Rq P{v } • P{k | r, v } = P{k | r}.
Returning to Game 2 and Game 3, we construct an efficient reduction S as follows: it takes as input two pairs (A, #» u), ( #» b, v), and outputs

A, #» b, ( #» u, r = HelpRec(v)) , k = Rec(v, r) .
Note that if two random variables X and Y are computationally indistinguishable and f is a polynomial time function, then f (X) and f (Y ) are computationally indistinguishable. Therefore, taking two indistinguishable inputs from S leads to indistinguishable outputs, due to its efficiency.

First suppose that the inputs are M -LWE instances; i.e. #»

u = A T #» s + #» e and v = #» b, #» s + e ,
where A is uniformly random and #» b is indistinguishable from uniform. Hence, the output of S will be exactly as in Game 2. Now suppose that the inputs given to S are uniformly random and independent, then the outputs of S are exactly as in Game 3. In fact, A, #» b, #» u, v are uniform, and hence by Theorem 4.3, k is uniformly random conditioned on r = HelpRec(v).

Equivalence of Game 3 and Game 4. To show that Game 3 and Game 4 are indistinguishable, we modify Game 1 and Game 2 by choosing k * $ ← -Λ 2 /Λ 3 and output it instead of k.

In this case Game 1 becomes Game 4. Let Game 2' be the modified version of Game 2. As a result we obtain the following:

Game 1' = Game 4 Game 2' Game 3 Game 4 A $ ← -R d×d q A $ ← -R d×d q (A, #» b ) $ ← -R d×d q × R d q A $ ← -R d×d q ( #» b , #» s ) ← Gen(A) #» b $ ← -R d q ( #» u , v) $ ← -R d q × Rq ( #» b , #» s ) ← Gen(A) (( #» u , r), k) ← Encaps(A, #» b ) (( #» u , r), k) ← Encaps(A, #» b ) r = HelpRec(v) (( #» u , r), k) ← Encaps(A, #» b ) k * $ ← -Λ2/Λ3 k * $ ← -Λ2/Λ3 k * $ ← -Λ2/Λ3 k * $ ← -Λ2/Λ3 Output A, #» b , ( #» u , r), k * Output A, #» b , ( #» u , r), k * Output A, #» b , ( #» u , r), k * Output A, #» b , ( #» u , r), k *
By the same reasoning as above, we can prove that Game 1' is computationally indistinguishable from Game 2', and Game 2' is computationally indistinguishable from Game 3. This proves that Game 4 (= Game 1') is computationally indistinguishable from Game 3.

IND-CCA security

Concrete security

We study the hardness of Module-LWE by considering it as an LWE problem, since, to date, the best known attacks don't make use of the module structure. There are numerous attacks to consider, however, we essentially deal with two BKZ attacks, namely primal and dual attacks as in KyberKEM. The cost of the primal attack and dual attack are computed using KyberKEM's script1 and presented in the next section.

Performance comparison

We make a comparison between our protocol and KyberKEM [A + 20] in terms of security, decryption error rate and bandwidth. The security against known attacks is increased by 6% to 8% for all KyberKEM levels. In terms of decryption error rate, our scheme guarantees a lower error probability for KyberKEM-512 and KyberKEM-768 compared to the original levels, namely P e < 2 -141 for p = 6 and P e < 2 -174 for p = 5 respectively; whereas for KyberKEM-1024 our error probability is not improved for any choice of the parameter p. For KyberKEM-512 and p = 6, the bandwidth is increased by 12.5%. Also for KyberKEM-768 and p = 5, the bandwidth is increased by 8.8%. Taking smaller p values will not guarantee smaller error probability compared to the original KyberKEM.

A summary of the results is illustrated in

Reconciliation using higher-dimensional Barnes-Wall lattices

It is natural to ask whether our technique could be improved by using higher-dimensional lattices for reconciliation. Therefore, we present some preliminary but inconclusive results in Appendix D.1. We replace E 8 by higher-dimensional Barnes-Wall lattices, and analogously to our previous construction, we choose

Λ 1 = q 2 p BW n 0 L , Λ 2 = (βBW n 0 ) L and Λ 3 = (qZ n 0 ) L (4.8)
with n 0 × L = 256. After that we focus on the case n 0 = 16 that has been studied in Subsection 2.2.4.

Up to now, higher-dimensional lattices don't appear to offer any benefit. On one hand, due to the scaling conditions imposed by the inclusions Λ 3 ⊆ Λ 2 , choosing higher-dimensional lattices doesn't result in a significant gain in terms of minimum distance. Moreover, the corresponding key sizes are not powers of two and thus are ill-suited to cryptographic applications. Finally, with higher-dimensional lattices, it is computationally difficult to obtain a tight bound for the error probability.

Conclusion

In this chapter, we have proposed a modification of KyberKEM which uses a reconciliation mechanism. Our choice of parameters is slightly modified with respect to the original KyberKEM and results are summarized in Table 4.8.

In terms of the Module-LWE instances, the ring R as well as the degree n = 256 and the dimension d ∈ {2, 3, 4} with respect to the chosen level remain unchanged. The modulus q is reduced from q = 3329 to q = 2 11 . Since q is a power-of-two, alternative Karatsuba/Toom-Cook algorithms should be used to perform multiplication within R q instead of using the NTT. The advantage of choosing an even q is that a dither is not required to obtain a uniform key with the reconciliation method. The centered binomial error distribution ψ k is used with the same parameter k ∈ {2, 3} as in the original KyberKEM for all case levels.

The reconciliation step is done using the 8-dimensional lattice E 8 that allows to generate one bit of key per dimension with a reconciliation rate of p -1. The total size of the shared private key is 256 bits. Our scheme excludes the use of compression and decompression functions which leaves us with a small increase in terms of bandwidth compared to KyberKEM.

In terms of security, our scheme achieves higher security against known attacks, namely an improvement by 6% to 8% as shown in Table 4.8, while IND-CCA security is still guaranteed.

In conclusion, we have shown that the reconciliation technique can provide a real gain in terms of security and reliability. In terms of efficiency, we haven't precisely quantified the complexity of hardware implementation of our protocol, which is left for future work.

Conclusions and perspectives

Throughout this thesis, we have devoted our research to examining and evaluating two key encapsulation mechanisms that have been submitted to the NIST Post-Quantum project in order to modify the parameter settings and therefore improve the overall security, decrease the decryption failure probability or reduce the communication requirements. The protocols selected are lattice-based protocols that rely on the Learning With Errors problem and its variants, in favor of robust security. The results obtained show that one can achieve better performance by applying an error correction mechanism as well as a reconciliation technique.

By adopting an error-correction technique based on the 8-dimensional lattice E 8 in both Chapters 3 and 4, we were able to perform the decryption operations with a lower error probability, which leads to an improvement in the IND-CCA advantage. However, one aspect that still needs to be investigated is the efficiency of our technique in terms of practical hardware implementation. The existing decoding algorithms which rely on simple rounding functions suggest that the efficiency will not be too affected.

Since it is well known that the minimum distance and error correction capabilities of lattice codes increase with the lattice dimension, in Appendix D we investigated the use of higherdimensional lattices, such as Barnes-Wall lattices, for reconciliation. However, our results are inconclusive and we were unable to obtain an error probability bound in the range required for post-quantum cryptography applications. In part, this is due to the fact that it is difficult to obtain rigorous and tight bounds for the error probability for high-dimensional lattices. Moreover, a rather counter-intuitive conclusion is that the use of higher-dimensional lattices does not necessarily bring a gain in terms of minimum distance due to the scaling constraints imposed by the modulo-q integer arithmetic of LWE protocols.

In alternative to lattice coding, we also investigated the use of polar codes and Reed-Muller codes for error correction in LWE-based protocols, but encountered some difficulties and we did not present our partial results in this report. Polar codes [START_REF] Arikan | Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[END_REF] are an attractive solution because of the low complexity successive cancellation (SC) decoding, but it is not easy to design and evaluate the performance of polar codes for the "LWE channel" in which the noise is not independent and identically distributed [START_REF] Wang | Coding techniques in lattice-based cryptography[END_REF]. Another option is to use Reed-Muller codes with the low-complexity decoder by Schnabl and Bossert [START_REF] Schnabl | Soft-decision decoding of reed-muller codes as generalized multiple concatenated codes[END_REF]. The advantage is that this decoder is a bounded distance decoder and one can use the sphere bound in order to estimate 0 ,1/2 ,1/2 ,1/2 ,1/2 ,0 ,1/2 ,0 ,1/2 ,1/2 ,0 ,0 ,1/2 ,0 ,0 ,0 , 0 ,0 ,1/2 ,1/2 ,1/2 ,1/2 ,0 ,1/2 ,0 ,1/2 ,1/2 ,0 ,0 ,1/2 ,0 ,0 , 0 ,0 ,0 ,1/2 ,1/2 ,1/2 ,1/2 ,0 ,1/2 ,0 ,1/2 ,1/2 ,0 ,0 ,1/2 ,0 , 1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2 ,1/2]; E := LatticeWithBasis (16 , G ) ;

V o r o n o i R e le va nt Vec to rs ( E ) ;

A.5 Proof of Theorem 2.2

Theorem 2.2 is presented in its real form instead of the complex form since throughout this thesis we are only working with real lattices. To provide concrete and elegant description, we use complex numbers following the notation in [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF]. For instance, the notation BW n is now a lattice of dimension N = 2 n in C N with generator matrix

G BW n =    G BW n-1 G BW n-1 0 φ • G BW n-1    with φ = 1 + i and initial condition BW 0 = [1].
Note that everything can be translated from complex space into the real space, and viceversa, using the following transformation:

C → R 2×2 a + ib →    a -b b a   
In fact,

λ ∈C N = [z 1 , . . . , z N ] • G BW n ∈C N ⇐⇒ λ ∈R 2N = [ (z 1 ), -(z 1 ), . . . , (z N ), -(z N )] • G BW n ∈R 2N
In the following we refer to the functions ParBW, SeqBW, RMdec in Algorithms 1,2 and 3 of Micciancio and Nicolosi's paper [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF].

A.5.1 Modification

We modify Algorithm 3 in [START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF] in the case r = 0 as follows: if

b j =0 ρ j = b j =1 ρ j , then return b 1 • [1, 1, . . . , 1].
It means that we choose the output vector based on the first bit of b. Note that the decoder is still BDD with this modification.

A.5.2 Linearity of ParBW

In this subsection we will prove the following proposition: We will prove this by induction on p and N . The cases p = 1 or N = 1 will be proven in the next subsection. Now consider the case where p ≥ 4 and s / ∈ C 1 . Suppose that Proposition A.1 holds for N/2-dimensional vectors and p/4 processors; we will show that it also holds for N -dimensional vectors and p processors.

Let λ = [λ 0 , λ 1 ] and w = [w 0 , w 1 ]. As defined in Algorithm 1, we have:

s : = [s 0 , s 1 ] = [λ 0 + w 0 , λ 1 + w 1 ] = [λ 0 , λ 1 ] + [w 0 , w 1 ],
and the candidate vectors are

           z 0 (s) z 1 (s) z -(s) z + (s)            :=            ParBW(p/4, λ 0 + w 0 ) ParBW(p/4, λ 1 + w 1 ) ParBW p/4, φ 2 [λ 0 -λ 1 ] + φ 2 [w 0 -w 1 ] ParBW p/4, φ 2 [λ 0 + λ 1 ] + φ 2 [w 0 + w 1 ]           
.

Here we use implicitly the fact that [λ

0 , λ 1 ] ∈ BW n =⇒ λ 0 , λ 1 ∈ BW n-1 . Note that z - 0 (s) := [z 0 (s), z 0 (s) -2φ -1 z -(s)] = λ 0 + ParBW(p/4, w 0 ), ......λ 0 + ParBW(p/4, w 0 ) -(λ 0 -λ 1 ) -2φ -1 ParBW p/4, φ 2 (w 0 -w 1 ) = [λ 0 , λ 1 ] + ParBW(p/4, w 0 ), ParBW(p/4, w 0 ) -2φ -1 ParBW p/4, φ 2 (w 0 -w 1 ) = λ + [z 0 (w), z 0 (w) -2φ -1 z -(w)] = λ + z - 0 (w).
Note that 2 α+1 (G BW 8n ) -1 an integer matrix if and only if 2 α+1 (G BW 4n ) -1 Φ -1 4n is an integer matrix. Accordingly,

2 α+1 (G BW 4n ) -1 Φ -1 4n =    2 α+1 (G BW 2n ) -1 Φ -1 2n -2 α+1 (G BW 2n ) -1 Φ -2 2n 0 2 α+1 (G BW 2n ) -1 Φ -2 2n    Again, 2 α+1 (G BW 4n ) -1 Φ -1
4n is an integer matrix if and only if 2 α+1 (G BW 2n ) -1 Φ -2 2n is an integer matrix. As a consequence,

2 α+1 (G BW 2n ) -1 Φ -2 2n =    2 α (G BW n ) -1 Φ -1 n • 2Φ -1 n -2 α (G BW n ) -1 Φ -1 n • 2Φ -2 n 0 2 α (G BW n ) -1 Φ -1 n • 2Φ -2 n   
This proves the result.

Consequently, we can now state our result as follows:

Proposition A.4. For n ≥ 2 and k ≥ log n 2 , 2 k Z n ⊆ BW n ⊆ Z n .
Proof. The second inclusion is obvious. Following proposition 2.1, the first inclusion is true if 2 k (G BW n ) -1 is an integer matrix. For n = 2 the proposition is easily verified. Note that for any power-of-two integer n ≥ 4, it has either the form n = 2 2α or n = 2 2α+1 for some integer α ≥ 1. For both cases, k = log n 2 = α, and that completes the proof using lemma A.6.

A.7 Proof of Theorem 2.3

We start our proof by the following lemma adopted from [HKZ12]:

Lemma A.7. Let z be a vector of n independent standard Gaussian random variables. Fix any non-negative vector ρ ∈ R n + and any vector

β ∈ R n . If 0 ≤ γ < 1/(2 ρ ∞ ) then E exp γ n i=1 ρ i z 2 i + n i=1 β i z i ≤ exp ρ 1 γ + ρ 2 γ 2 + β 2 /2 1 -2 ρ ∞ γ
Corollary A.1. Let X n be a subgaussian vector in R n with parameter s. Then

P X n 2 > s 2 2π • n + 2 √ nt + 2t ≤ e -t
Proof. By definition of X n we have ∀t ∈ R, and

∀ u ∈ R n : u = 1, E e 2πt X n ,u ≤ e πt 2 s 2
Let's verify that for all α ∈ R n and a fixed σ > 0, X n satisfies the condition:

E e α,X n ≤ e α 2 σ 2 /2
In fact, for any α ∈ R n , there exist t ∈ R and a unit vector u ∈ R n such that α = 2πtu. Hence, for this t and u we have

E e α,X n ≤ e πt 2 s 2 = e α 2 s 2 4π
Now, take σ = s √ 2π , (which is fix as s is) we get:

E e α,X n ≤ e α 2 σ 2 2 (A.2)
Let z be a vector of n independent standard Gaussian random variables (sampled independently from X n ). Then for any α ∈ R n ,

E exp z T α = exp α 2 /2 . Using the fact that E [X] = i E [X|Y = A i ] • P {Y = A i },
we obtain for any λ ∈ R and > 0:

E exp λz T X n ≥ E exp λz T X n X n 2 > • P X n 2 > But E exp z T (λX n ) = exp λX n 2 /2 ; so given that X n 2 > we get E exp λz T X n ≥ exp λ 2 2 • P X n 2 > (A.3)
Moreover, using the law of total expectation, we obtain:

E X n exp λz T X n = E z E X n exp λz T X n z (A.4) ≤ E z exp λ 2 σ 2 2 z 2 (by (A.2))
Now put ρ = (1, 1, . . . , 1). By Lemma A.7 with β = 0 we get:

E exp γ n i=1 z 2 i ≤ exp ρ 1 γ + ρ 2 γ 2 1 -2 ρ ∞ γ where 0 ≤ γ < 1/(2 ρ ∞ ) = 1/2; which is in fact E exp γ z 2 ≤ exp n • γ + n • γ 2 1 -2γ (A.5)
Combining (A.3), (A.4) and (A.5):

exp λ 2 2 • P X n 2 > ≤ E z exp λ 2 σ 2 2 z 2 (A.6) ≤ exp n • γ + n • γ 2 1 -2γ
where we set γ = λ 2 σ 2 2 ; and hence

P X n 2 > ≤ exp -γ/σ 2 + n • γ + n • γ 2 1 -2γ
(always under the condition that 0 ≤ γ < 1 2 ). Choose:

= σ 2 • (n + τ ) and γ = 1 2 • 1 - n n + 2τ < 1 2 .
Consequently, we obtain:

P X n 2 > σ 2 • (n + τ ) ≤ exp - n 2 1 + τ n -1 + 2τ n (A.7) = exp - n 2 • h τ n where h(x) = 1 + x - √ 1 + 2x defined from R + to R + with inverse h -1 (y) = √ 2y + y. Set τ = 2 √ nt + 2t so that τ n = 2 t n + 2 t n = h -1 2t n which leads to P X n 2 > σ 2 • (n + 2 √ nt + 2t) ≤ e -t
Corollary A.2. Let X n be a subgaussian vector in R n with parameter s. Then ∀ > 0:

P X n > σ √ n • 1 + 2 + 2 2 ≤ e -n 2
Proof. From Corollary 2.3, we know that for a general n-dimensional subgaussian X n with parameter s, we have The above term P E 0,0 + • • • + E 7,7 ∈ 2 13 ; 2 13 + 1024 is bounded by a constant cst. Moreover, the number of terms beyond 2 13 + 1024 is less than 2 20 . Thence, where i,j = 1 if i = j, and -1 otherwise. Note that, if i = j, then i,j (-1) δ j,i = -(-1) δ j,i = (-1) δ i,j ;

P X n 2 > s 2 2π n • 1 + 2 t n + 2 t n ≤ e -
P E 0,0 + • • • + E 7,
and if i = j, then i,j (-1) δ j,i = 1 = (-1) δ i,j .

This concludes the proof.

C.2 Computing the distribution of (s , s), W λ,κ

In this section, we explain how to compute the distribution of (s , s), W λ,k for KyberKEM, where W λ,k is defined in equation (4.6).

Recall that (s , s) = (s 0 , s 1 , . . . , s nd , s 0 , s 1 , . . . , s nd ), and hence (s , s), W λ,k = Z 1 +• • •+Z 2Ld is the sum of 2Ld i.i.d. random variables. Note that Z 1 ∼ (s 0 , s 1 , . . . , s 7 ), e (0) • λ and ∀ i = 2, . . . , 2Ld, Z i ∼ Z 1 . So we can focus on obtaining the PDF of Z 1 since the PDF of the sum Z 1 + • • • + Z 2Ld can be computed from the PDF of Z 1 using the probability generating function defined in Appendix A.1 and Lemma A.1.

C.2.1 PDF of the dot product Z 1 ∼ (s 0 , s 1 , . . . , s 7 ), e (0) • λ for λ ∈ VR

(1) E 8

We aim to find the probability density function of (s 0 , s 1 , . . . , s 7 ), e (0) • λ for each λ ∈ VR

(1) E 8 . For simplicity, we will take the vector λ = (1, 1, 0, 0, 0, 0, 0, 0). The computation for other values λ ∈ VR

(1) E 8 can be performed in a similar way. In polynomial form, for e (0) ≡ (e 0 , . . . , e 7 ), the product e (0) • λ modulo X 8 + 1 is equal to (e 0 -e 7 )+(e 0 +e 1 )X+(e 1 +e 2 )X 2 +(e 2 +e 3 )X 3 +(e 3 +e 4 )X 4 +(e 4 +e 5 )X 5 +(e 5 +e 6 )X 6 +(e 6 +e 7 )X 7 .

In vector form, this is equivalent to (e 0 -e 7 , e 0 + e 1 , e 1 + e 2 , e 2 + e 3 , e 3 + e 4 , e 4 + e 5 , e 5 + e 6 , e 6 + e 7 ).

It follows that the dot product (s 0 , s 1 , . . . , s 7 ), e (0) • λ can be rewritten as (e 0 -e 7 )s 0 +(e 0 +e 1 )s 1 +(e 1 +e 2 )s 2 +(e 2 +e 3 )s 3 +(e 3 +e 4 )s 4 +(e 4 +e 5 )s 5 +(e 5 +e 6 )s 6 +(e 6 +e 7 )s 7 . for each value of (e 0 , . . . , e 7 ) ∈ {-k, k} 8 . Note that conditioning on (e 0 , . . . , e 7 ), the sum in (C.1) is a sum of independent random variables, so one can calculate it using the probability generating function.

Let G s (X) be the probability generating function of s i , which is the same for all i = 0, . . . , 7, and k the parameter of the centered binomial distribution ψ k . Let p = ψ k for simplicity. The function G s can be expressed as G s (X) = p(-k)X -k + p(-(k -1))X -(k-1) + • • • + p(k -1)X (k-1) + p(k)X k .

For instance, the probability generating function of s 0 (e 0 -e 7 ) for a fixed integer value of (e 0 , e 7 ), denoted as F 0 , can be written as F 0 (X) = p(-k)X -k(e 0 -e 7 ) + p(-(k -1))X -(k-1)(e 0 -e 7 ) + • • • + p(k)X k(e 0 -e 7 ) (C.3) The equality ( * ) is true since p(-k) = p(k). Our aim is to let the exponent of X that is outside the parenthesis (i.e. the exponent of X -k|e 0 -e 7 | ) to be negative, and the exponents of X of G 0 (X) to be positive.

In the same way as (C.3), for i ≥ 1, we define F i to be the probability generating function of s i (e i-1 + e i ) and G i (X) = p(-k) + p(-k + 1)X |e i-1 +e i | + • • • + p(k)X 2k|e i-1 +e i | . Finally, the probability generating function F of the expression (C.1) is the product of each F i (X), i = 0, . . . , 7. In more details, F (X) = This array will have length of shift for arr = 1 + 2k(k + k). In the same way we construct the arrays arr1, . . . , arr7 that correspond to the functions G 1 , . . . , G 7 . The convolution product of these 8 arrays will contain the coefficients of the probability generating function of 7 i=0 G i (X). We aim to create an array scal pdf to store the probability distribution of the sum (C.1).

In Matlab, we shift the indices since negative indices are not allowed. The dot product in C.2.2 PDF of the dot product Z 1 ∼ (s 0 , s 1 , . . . , s 7 ), e (0) • λ for λ ∈ VR

(2) E 8

The simulations for λ ∈ VR

C.3 Distribution of Z

1 + • • • + Z 2Ld
Recall that the probability generating function F (X) of Z 1 is defined in (C.4). Hence, to obtain the probability generating function of the sum Z 1 + • • • + Z 2Ld , we need to multiply F (X) by itself 2Ld = 2 6 d times. For the sake of efficiency, we raise F (X) to the power of d, take the result and raise it to the power-of-two, and repeat the latter 5 times. We have used the Wolfram MATHEMATICA software for this part of the computation. By applying Proposition D.1, condition (D.2) is satisfied if for all κ = 0, . . . , L -1, Taking the term e s from some ∈ {1, . . . , d}, it is a polynomial multiplication modulo X n + 1.

n 0 k = log n0 2 d min q 2 1 -1 2 p -1 E 8 ≤ d min q 2 k 1 -1 2 p-
(v -v ) (κ) ≤ C • d min (BW n 0 ) 2 = q 2 k 1 - 1 2 p-k n 0 /2 2 = q √ n 0 2 k+1 √ 2 1 - 1 2 p-
It can be identified to (e ,0 , e ,1 , . . . , e ,n-1 ) • s ,0 , s ,1 , . . . , s ,n-1 mod X n + 1. (D.4) Since for 0 ≤ i, j ≤ n -1 the product of e ,i • s ,j is bounded by k 2 1 in absolute value (k 1 is the parameter of the centered binomial distribution ψ k 1 ), then by Proposition 2.4 and Remark 2.4, the resulting vector e s in (D.4) has subgaussian components with parameter

√ nk 2 1 √ 2π. 1
As a consequence, since by Theorem 2.4 e is subgaussian with parameter √ k 2 π, each component of the vector ω (κ) in (D.3) is subgaussian with parameter √ π 2dn(k 4 1 + k 2 1 k 2 2 ) + k 2 , and hence using Proposition 2.5, the whole vector ω (κ) is subgaussian with parameter ρ = √ n 0 √ π 2dn(k 4 1 + k 2 1 k 2 2 ) + k 2 . From condition (D.2), an error occurs while decoding if there exists κ ∈ {0, . . . , L -1} such that ω (κ) > q √ n 0 2 k+1.5 1 -

1 2 p-k . n 0 k = log n 0 2 p d min q 2 1 -1 2 p -

D.2 KyberKEM with BW 16

In this section, we will work with BW 16 defined in Subsection 2.2.4 with the generator matrix given in (2.4) in order to obtain a better scaling. With the new choice of the generator matrix, we can have a better inclusion and better minimum distance compared to Section D.1. In fact, the lattice Λ 2 defined in inclusion (D.1) as q 4 BW 16 16 can be replaced by Λ 2 = q 2 BW 16 16 , thus doubling the scalar β. Accordingly, we make the following choice:

Λ 1 = q 2 p BW 16 16 ⊇ Λ 2 = q 2 BW 16 16 ⊇ Λ 3 = qZ 16 16 .
The constant C here is C = q 2 1 -1 2 p-1 . The number of reconciliation bits transmitted is n(p -1) and the size of the key (in bits) is n + 64 = 1.25n = 320.

Note that BW 16 and E 8 have the same minimal distance equal to √ 2. However, in this section we will not use the sphere bound and we will consider a union bound over Voronoirelevant vectors similarly to Subsection 4.4.3. Unfortunately, estimating the bound of Subsection 4.4.3 for this lattice would require very cumbersome computations. In this section, we will use a different approach inspired by [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF].

Our main objective is to calculate the error probability given by Recall from Subsection 2.2.4 that there are three types of Voronoi-relevant vectors in this case.

Observing that the value of P λ is the same for vectors of the same type, it is enough to consider a fixed vector in VR (i) BW 16 for each type i = 1, 2, 3, such as λ 1 = (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) λ 2 = ( 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 0, 0, 0, 0, 0, 0, 0, 0) λ 3 = ( 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1 2 , 1, 0, 0, 0, 0, 0, 0, 0), and hence obtain the following bound: In order to work with integer-valued vectors, we define the following:

• λ 1 = λ 1 = (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

• λ 2 = 1 2 λ 2 = 1 2 (1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0)

• λ 3 = 1 2 λ 3 = 1 2 (1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0)

In order to go further in our analysis, we will need the following lemma:

Lemma D.1 (Lemma D.2 in [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]). Let X n be a subgaussian vector with parameter σ.

Then for any τ > 0 and any vector v ∈ R n we have:

P X n , v > v τ σ √ 2π ≤ e -τ 2 /2 .
We can apply the Lemma with X n = ( s , s), σ = √ k 1 π and v = W v i ,0 for v i ∈ VR Using the Cauchy-Schwarz inequality, and depending on how many zeros are in λ i , one can bound e (0) , λ i as follows:

• e (0) , λ 1 ≤ e (0) , λ 1 ≤ √ 2k 2 λ 1 . In fact, e (0) , λ 1 = (e 0 , . . . , e 15 ), (1, 1, 0, . . . , 0)

= (e 0 , e 1 , 0, . . . , 0), (1, 1, 0, . . . , 0)

≤ (e 0 , e 1 , 0, . . . , 0) • (1, 1, 0, . . . , 0)

≤ √ 2k 2 λ 1 .
This implies that we can choose

C 1 = C • λ 1 2 2 - √ 2k 2 λ 1
• e (0) , λ 2 ≤ e (0) , λ 2 ≤ √ 8k 2 λ 2 . This implies that C 2 = C • λ 2 2

4

-2 √ 2k 2 λ 2 .

• e (0) , λ 3 ≤ e (0) , λ 3 ≤ √ 9k 2 λ 3 . This implies that

C 3 = C • λ 3 2 4
-3k 2 λ 3 . Now for some τ i > 0 set

C 1 = C 1 k 1 /2 • τ 1 ; C 2 = 2C 2 k 1 /2 • τ 2 and C 3 = 2C 3 k 1 /2 • τ 3 .
Then, for L = 16 we obtain from (D.9) and (D.7):

P e ≤

  Security engineering, especially in this third wave, requires you to think differently. You need to figure out not how something works, but how something can be made to not work. You have to imagine an intelligent and malicious adversary inside your system constantly trying new ways to subvert it. You have to think like an alien

a

  variety of cryptographic algorithms and provides guarantees in terms of IND-CPA (indistinguishability under chosen-plaintext attack) security [Reg09, KTX07, PVW08] and IND-CCA (indistinguishability under chosen-ciphertext attack) security [PW11,Pei09]. Other applications of the LWE problem include identity-based encryption schemes [GPV08, CHKP12, ABB10], various forms of leakage-resilient encryption [AGV09, DGK + 10, GKPV10], homomorphic encryption [Bra12, BV14a, BGV14, SCC19] and much more. In order to fix ideas and to have a clearer vision of our discussion, we give below two formal definitions which present the LWE problem in its search and decision form.Definition 1.1 (Search-LWE). Let q = poly(n) be an integer and χ a Gaussian-like distribution over Z. Let m = poly(n), referred sometimes as the number of samples. For a secret vector s ∈ Z n q and an m × n dimensional matrix A sampled uniformly from Z m×n q , consider an error term e drawn from the χ m distribution and denote b = As + e. The problem asks to recover the secret s given the pair (A, b). The second version of the problem is the decision-LWE. Definition 1.2 (Decision-LWE). Consider the pair (A, b) with the same distribution as in Definition 1.1. The problem asks to distinguish between the two samples (A, b) and (A , b ), where A and b are uniform samples from Z m×n q and Z n q respectively.

  Two schemes based on Module-LWE have been proposed for the NIST standardization process: the signature scheme Dilithium [DKL + 18] and the KyberKEM key encapsulation mechanism [A + 20]. The latter scheme provides an IND-CCA secure KEM, which has first been described in [BDK + 18]. Like most key encapsulation protocols in the literature, Ky-berKEM is derived from an IND-CPA secure public-key encryption scheme via a slightly tweaked Fujisaki-Okamoto transform.

3. 2

 2 with a recent reduction to the DGS-BDD problem derived from [N + 20]. A brief introduction to the FrodoKEM protocol is given in Section 3.3 including some modifications proposed in the literature. Subsections 3.3.2 and 3.3.3 review the reliability and the security achievements of the scheme. In Section 3.4 we propose a new error correction mechanism in order to improve the performance of FrodoKEM. In Subsection 3.4.3, we derive an upper bound for the decryption failure probability of our modified protocol, while the concrete security is examined in Subsection 3.4.5. The performance comparison with the original FrodoKEM protocol is presented in Subsection 3.4.4. The details of the numerical simulations performed are presented in Appendix B. • Chapter 4 -KyberKEM with reconciliation. Section 4.2 introduces the Module-LWE problem which is the basis of the KyberKEM protocol presented in Section 4.3. In Subsections 4.3.2 and 4.3.3, we review the decryption failure probability and security bounds for the protocol. In Section 4.4, we describe our proposed modification for the encoding and decoding function. In Subsections 4.4.3 and 4.4.4, we provide an error probability bound of our modified protocol, and we study the concrete security against known attacks. Finally, in Subsection 4.4.5 we compare the performance of the modified protocol with KyberKEM for different choices of parameters. Further details about our numerical simulations, as well as some partial results about higher-dimensional reconciliation using Barnes-Wall lattices are presented in Appendices C and D.

  Vectors and matrices are written in boldface and M m,n (A) denotes the set of m × n matrices with coefficients in the ring A. The symbol i indicates the complex number √ -1. A constant vector (α, α, . . . , α) is simplified to α. The Euclidean norm of x ∈ R n is x . The open n-dimensional ball of center x 0 and radius r is B n (x 0 , r) = {x ∈ R n : xx 0 < r}. The same way we define the closed ball Bn (x 0 , r) = {x ∈ R n : xx 0 ≤ r}. Rounding a real number x ∈ R to the nearest integer is denoted by x , for which ±a ± 1/2 = ±a, ∀ a ∈ N. The rounding function can be extended to vector notation as x = ( x 1 , . . . , x n ). The symbol || is used for concatenation. Given x ∈ R, we assign sign(x) to be 1 if x ≥ 0, and -1 otherwise. The integer interval {a, a + 1, . . . , b} is also denoted as [[a, b]] for any b > a in Z, and ]]a, b]] when the integer a is excluded. For an even (resp. odd) positive integer m, the operation r = r mod ± m is defined to be the unique element r in the rangem 2 , m 2 (resp. -m-1 2 , m-1 2

Figure 2 . 2 :

 22 Figure 2.2: The union of translates of the shaded region covers R n in a disjoint way.

Figure 2 .

 2 Figure 2.2 illustrates an example of a fundamental region of a lattice. Note that for any fundamental region F, a point x ∈ R n can be uniquely expressed as x = λ + e Q , where λ ∈ Λ and e Q ∈ F. We write λ = Q F (Λ) (x) to be the quantization function applied to x, and

Definition 2. 8 (Figure 2 . 3 :

 823 Figure 2.3: Voronoi region (in gray) surrounded by Voronoi relevant vectors.

Figure 2 . 4 :

 24 Figure 2.4: Simplified illustration of PKE.

FigureFigure 2 . 5 :

 25 Figure 2.5: Simplified illustration of KEM.

  of ciphertext and obtain the corresponding decrypted plaintext. The security requirement for this context is the indistinguishability under chosen-ciphertext attack (IND-CCA). The concept is the same as for IND-CPA security, with the restriction that the attacker cannot query the decryption of the received ciphertext. The formal definition of IND-CPA and IND-CCA security is discussed in the next Section with respect to the PKE and KEM cryptosystems. Note that IND-CCA security implies IND-CPA security.

Figure 2 .

 2 Figure 2.6 illustrates the game above.

Figure 2

 2 Figure 2.7: Simplified illustration of IND-CPA game for KEM.

•

  The challenger selects b $ ← -{0, 1} and sends the challenge c * = Enc(pp, pk, m b ) back to the adversary. • The adversary is allowed to call the decryption oracle A Dec , but cannot request to decrypt c * , because otherwise A Dec outputs a failure symbol ⊥. He then answers with a guess b for the value of b. • The game succeeds if b = b, and it fails otherwise.

Figure 2 .

 2 Figure 2.8 illustrates the game above.

Figure 2 .

 2 Figure 2.9 illustrates the game above.

Figure 2

 2 Figure 2.10: The centered binomial distribution ψ k for k = 16.

  Figure 2.11: Rényi divergence of the centered binomial distribution ψ k and the rounded Gaussian distribution Ψ √ kπ according to k (α = 9).

  Post-Quantum Cryptography project and is now one of the alternative candidates among key establishment algorithms. The security of FrodoKEM is based on the hardness of what is called the Learning With Errors problem (LWE) introduced by Regev [Reg09] and discussed in the next Section.

•

  The primal attack [AAB + ] solves the search version of the LWE problem by constructing a unique-SVP, instance from the LWE problem and solving it using BKZ. The width of the block dimension b for BKZ is examined in order to find the unique solution. Given the matrix LWE instance (A, b = As + e), one builds the lattice Λ = x ∈ Z m+n+1 : (A|I m | -b) x = 0 mod q . This lattice is of rank n+1 and dimension d = m+n+1. In fact, if we set A = (A|I m | -b), then by the rank theorem we have: rank A + dim(Ker A ) = m + n + 1.

  BDDwDGS algorithms [AR05, LLM06, DRSD14] use discrete Gaussian samples that all have equal width parameter s. However, for certain constraints on r, the oracle in Definition 3.4 can be replaced by an oracle with fixed-width r that samples from D w+Λ * ,r for any queried coset w + Λ * . Theorem 5.12 in [N + 20] relates the hardness of BDDwDGS to the hardness of the decision-LWE problem: Theorem 3.2 (BDDwDGS hard =⇒ decision-LWE hard). Let = (n) be a negligible function and let m = poly(n) and C = C(n) > 1 be arbitrary.

FrodoKEM [N + 20 ]

 20 is a family of key encapsulations mechanisms that has been selected by the NIST project for Post Quantum Cryptography Standardization and chosen as an alternative candidate for the third round. The security of the protocol is based on the hardness of the LWE problem, offering a relatively easy to implement algorithm. Moreover, the scheme is designed to ensure IND-CCA security at three different levels, corresponding to the brute-force security of AES-128, AES-192 and AES-256. The IND-CCA secure KEM is induced from an IND-CPA secure PKE scheme called FrodoPKE using the Fujisaki-Okamoto (FO) transform.

  In this algorithm, Alice generates A $ ← -Z n×n q , samples S, E ← χ n×n Frodo , then computes the LWE samples B = AS + E and outputs a public key (A, B). Bob chooses S , E , E ← χ n×n Frodo , then computes the LWE samples U = S A + E and V = S B + E . A message m in {0, 1} 64B is generated unilaterally on Bob's side and encoded into Z n×n q using the function Frodo.Encode(•) presented in Algorithm 2. Bob sends the ciphertext (U, C) to Alice, where C = V + Frodo.Encode(m). Alice recovers m using the decoding function in Algorithm 3. Algorithm 2 Frodo.Encode Input: Bit string k ∈ {0, 1} , = B • 64 Output: Matrix K ∈ Z 8×8 q 1: for i=0 to 7 do 2:

Frodo.Pack (•) [N + 20 ,

 20 Algorithm 3] and then decompressed using Frodo.Unpack (•) [N + 20, Algorithm 4]. The compression function transforms the matrices U and C in Table

  FrodoKEM. Having established the IND-CPA security regarding FrodoPKE, we can now explore the FrodoKEM scheme that guarantees IND-CCA security by applying the Fujisaki-Okamoto transform. The security is studied with respect to both the classical and quantum random oracle models discussed in Subsection 2.3.3. Theorem 5.1 in [N + 20] demonstrates the IND-CCA security of a KEM that is derived from an IND-CPA-secure public-key encryption scheme, even if the KEM and PKE use different error distributions, as long as those distributions are close in terms of Rényi divergence (see Subsection 2.4.4). This is only true in the classical ROM. Theorem 3.4 (Theorem 5.1 in [N + 20]

Corollary 3. 2 .

 2 Using the finite support distribution χ Frodo , FrodoKEM is IND-CCA secure, provided that the FrodoPKE protocol using a rounded Gaussian distribution Ψ σ √ 2π is IND-CPA secure. Regarding the IND-CCA security for a KEM against quantum attackers in the quantum random oracle model, a non-tight reduction is proven in Theorem 5.8 in [N + 20]. Unfortunately, the FrodoKEM instantiations do not verify the hypotheses of this theorem, so there is no currently security guarantee against quantum attackers. This theorem can be seen as a support for the security of general constructions of LWE-based KEMs in the style of FrodoKEM against quantum adversaries. Concrete security for FrodoKEM. The concrete security bounds in FrodoKEM are calculated similarly to [LP11, ADPS16b, AGVW17]. BKW types of attacks [KF15] and linearization attacks [AG11] are not relevant to this case due to the small number m of LWE samples available to the attacker (m ≈ n in FrodoKEM). The best known attacks in this context are BKZ primal and dual attacks (see discussion in Paragraph 3.2). Regarding the LWE parameters, the reduction shown in Paragraph 3.2 clarifies the choice of the standard deviation values in Table 3.2. The choice of the standard deviation σ = αq/ √ 2π for the distribution in FrodoKEM takes condition (3.1) into account. FrodoKEM gives concrete examples on the number of instances N which an adversary can reasonably obtain. Taking the very large number of samples N = 2 256 in condition (3.1), one obtains the lower bound αq > 5.314 for the Gaussian parameter, and hence a standard deviation greater than 5.314/ √ 2π = 2.12. Moreover, it is unreasonable to assume that an adversary can obtain more than N = 2 111 samples from D Λ * ,s , and hence this value of N remains sufficient to not break the BDDwDGS problem. The corresponding σ is 1.4.

Figure 3 . 2 :

 32 Figure 3.2: Bandwidth cost of NIST Level 1 lattice-based KEMs [Pre21, Slide 13].

  g(b 8 , . . . , b 15 ) = 2 • (b 8 , . . . , b 15 ) ∈ 2Z 8 /4Z 8 if = 128 g(b 8 , . . . , b 23 ) = 2 • (b 8 , . . . , b 15 ) + 4 • (b 16 , . . . , b 23 ) ∈ 2Z 8 /8Z 8 if = 192 g(b 8 , . . . , b 31 ) = 2 • (b 8 , . . . , b 15 ) + 4 • (b 16 , . . . , b 23 ) + 8 • (b 24 , . . . , b 31 ) ∈ 2Z 8 /16Z 8 if = 256

. 6 )

 6 Similarly to equation (3.3), we can express the decoded message m as m = m + E8.Decode E .(3.7)

Figure 3 . 3 :

 33 Figure 3.3: Each block of 8 independent components is represented by a distinct color.

  -CCA security. Applying the Fujisaki-Okamoto transformation to our IND-CPA secure protocol yields an IND-CCA secure key encapsulation mechanism in the classical random oracle model (see Theorem 3.4). Our KEM protocol uses the finite support distribution χ that is close to Ψ σ √ 2π in terms of Rényi divergence. This allows to bound the IND-CCA advantage Adv IND-CCA in the same way as for FrodoKEM by using equation (3.4). Our security loss will be minimized by optimizing the Rényi divergence over the order α.

  In this chapter, we study another NIST candidate, KyberKEM, and propose a reconciliation mechanism to improve its security. KyberKEM is an IND-CCA secure key encapsulation mechanism that derives from an IND-CPA secure public key encryption scheme. Its core security is based on the difficulty of solving the structured variant of the LWE problem called Module Learning With Errors (M -LWE). KyberKEM has passed the third round for the NIST Post-Quantum Cryptography Project and is now one of the finalists with regard to key-establishment algorithms. Module-LWE offers a compact structure compared to the standard LWE problem, and therefore enables an efficient KEM scheme with high performance.

  to all samples and e i ← χ freshly generated for each sample.Note that the distribution χ may be parameterized by some parameter α and thus denoted as χ α . If the number of samples is m, then the instances of the M -LWE problem can be given in matrix form #» b = A #» s + #» e where A is an m × n matrix. More precisely, Module-LWE advantage). For an attacker A, we define the advantage Adv M -LWE m,d,χ α as

  and outputs a public key pk = #» b and a secret key sk = #» s

IND-

  CPA security. IND-CPA security (see Subsection 2.3.3) is established for KyberPKE if a passive adversary is not able to distinguish between the algorithm in Table 4.1 and the algorithm KyberPKE' in which the vector #» b together with #» u and v are uniformly random. By observing that the terms #» b, #» u and v of the original algorithm are in fact M -LWE samples, they are indistinguishable from uniform random variables thanks to the hardness of the decision Module-LWE problem.

  M -LWE d+1,d,Ψ k indicates the advantage in Definition 4.2 with respect to the centered binomial distribution Ψ k . IND-CCA security. Applying the Fujisaki-Okamoto transform from Subsection 2.3.4 to Ky-berPKE allows to obtain an IND-CCA secure key encapsulation mechanism called KyberKEM. By using three hash functions as random oracles, one can derive bounds regarding classical and quantum advantage. Let G 1 : {0, 1} * → {0, 1} 256 , G 2 : {0, 1} * → {0, 1} 2×256 and F : {0, 1} * → {0, 1} * initiated with SHAKE-256, be those three hash functions. Theorem 4.2 below bounds the classical advantage.

4. 2 )

 2 , and power-of-two moduli have been used in the literature in [DKRV18, LLZ + 18, N + 20]. These works use other methods for efficient polynomial multiplication, e.g. Karatsuba/Toom-Cook algorithms [BCLV17, DWZ18] and index-based multiplication [BBGM + 17]. An advantage

  The pair (( #» u, r), k) defines the output of the encapsulation function Encaps(A, #» b). Alice performs the decapsulation procedure Decaps( #» s , ( #» u, r)) by computing v = #» u, #» s and returning k = Rec(v , r).

Definition 4. 4

 4 (Conjugation). Let a(Y ) = a 0 + • • • + a n 0 -1 Y n 0 -1 ∈ S = Z[Y ]/(Y n 0 + 1). We define the polynomial conj (a) (Y ) as conj (a) (Y ) = a(conj(Y )),where conj(Y ) = conj X L := conj ζ L is the complex conjugation of the L-th power of the N -th primitive root of unity.

)

  conj e (κ-i) j• λ + e(κ) , λ Equality ( * ) is true due to mod L operation discussed in Subsection 4.4.1, and ( * * ) is true according to Proposition C.1. Using this and the fact that the distributions of e (κ-i) j and e j (κ-i) are invariant by conj(•) (see Lemma C.1) and the distributions of s j (i) and s j (i) are invariant by shifting or by multiplication by Y , we obtain a more compact form of ω(κ) , λ :ω (κ) , λ ∼ (s j , sj ) j=1,...,d , W λ,κ + e (κ) , λwhere s j = (s are n-dimensional vectors of independent centered binomial coefficients, andW λ,κ = e (κ-i) j• λ, . . . , e j (κ-i) • λ i=0,...,L-1, j=1,...,d (4.6)

E 8 we have ||λ|| 2 2 -,

 2 e(κ) , λ ≥ C 2 -2k 2 C. In fact, using the Cauchy-Schwarz inequality and the fact that the centered binomial distribution of parameter k 2 has support in [-k 2 , k 2 ], we obtain: e(κ) , λ ≤ e(κ) , λ ≤ C • e (1, 1) ≤ 2k 2 C.

Game 3 .

 3 To prove that Game 2 and Game 3 are computationally indistinguishable, we use the following Theorem which is essentially a consequence of the Crypto Lemma [Zam14, Lemma 4.1.1]. It guarantees uniformity of the private key without a dither. Theorem 4.3. If v ∈ R q is uniformly random, then k = Rec(v, r) is uniformly random, given r = HelpRec(v).

Following [ Pei14 ]

 Pei14 scheme for message space M = K by having the sender use the ephemeral private key k ∈ K as a one-time pad to conceal the message (this assumes that K has a group structure). Therefore, we can similarly convert our IND-CPA KEM to a passively secure PKE for message space M = Λ 2 /Λ 3 with the same level of reliability and security.Similarly to KyberKEM, since the decryption failure probability is small, we can obtain an IND-CCA secure KEM using a lightly tweaked Fujisaki-Okamoto transform applied to the IND-CPA secure PKE (see Subsection 2.3.4). A theoretical bound can be given on the CCA advantage in the same way as for KyberKEM as discussed in Subsection 4.3.3 (see also [A + 20, Theorem 2 and Theorem 3]). Note that the decryption failure probability bound appears in (4.1).

Proposition A. 1 .

 1 Let λ ∈ BW n and w ∈ C N a target, where N = 2 n , then ParBW(p, λ + w s ) = λ + ParBW(p, w), ∀ p = 4 k .

.aaa

  7 ≥ 2β ≤ cst + 2 20 • P E 0,0 + • • • + E 7,7 = 2 13 + 1025 can be calculated efficiently using Lemma B.1 i λ j conj(b) i-j mod n 0 (-1) δ i,j . Recall that conj(b) 0 = b 0 and conj(b) k = -b n 0 -k if k = 0. So, a, conj(b • λ) = j λ i conj(b) j-i mod n 0 (-1) δ j,i j λ i • i,j • b i-j mod n 0 (-1) δ j,i ,

(C. 1 )

 1 Using the fact that P (s0, s1, . . . , s7), e (0) • λ = C = (e 0 ,...,e 7 ) P (s0, s1, . . . , s7), e (0) • λ = C (e0, e1, . . . , e7) •P {(e0, e1, . . . , e7)} we can obtain the distribution of Z 1 by computing P (s 0 , s 1 , . . . , s 7 ), e (0) • λ = C (e 0 , e 1 , . . . , e 7 ) • P {(e 0 , e 1 , . . . , e 7 )} . (C.2)

=

  p(-k)X -k|e 0 -e 7 | + p(-(k -1))X -(k-1)|e 0 -e 7 | + • • • + p(k)X k|e 0 -e 7 | = X -k|e 0 -e 7 | p(-k) + p(-k + 1)X |e 0 -e 7 | + • • • + p(k)X 2k|e 0 -e 7 | G 0 (X)

7 i=0F

 7 i (X) = X -k (|e 0 -e 7 | + • • • + |e 6 + e 7 |) function G i (X) can be seen as a probability generating function of some distribution. For example, G 0 (X) represents the probability generating function of the random variable that takes values in [[0, |e 0 -e 7 |, . . . , 2k|e 0 -e 7 |]] with probabilities {p(-k), p(-k + 1), . . . , p(k)} respectively. From this fact, we create the array arr0 that contains the probability of having i * |e 0 -e 7 |) for i = 0, . . . , 2k. These probabilities are placed in arr0 as follows: arr0(1 + i * |e 0 -e 7 |) = P{i * |e 0 -e 7 |}, ∀i = 0, . . . , 2k.

  expression (C.1) can have values in [[-(2k) • k • 8 ; (2k) • k • 8]]; the shift is defined to be main shift=(VR1 card*k)*k*8+1, where VR1 card is the number of non-zero components of Voronoi-relevant vectors of VR (1) E 8 , which is 2. Finally, scal pdf[main shift+i] represents the probability that (C.1) takes the value i. We can now apply the formula (C.2) in order to obtain scal pdf. Remark C.1. These simulations have been done |VR (1) E 8 | = 112 times since for each λ ∈ VR (1) E 8we have a different distribution of the dot product.

E 8

 8 follow the same strategy as in Subsection C.2.1. We repeat the simulations |VR (2) | = 128 times.

  k , which is equivalent toe 1 s 1 + • • • + e d s d (κ) -e 1 s 1 + • • • + e d s d (κ) + e

PPP

  ∃λ ∈ C • VR BW 16 : ( s , s), W λ,κ > λ 2 2 -e(κ) , λ (see Equation (4.7)). In this section, we take L = 16. Using Boole's inequality, the above bound can be reduced to:∃λ ∈ C • VR (i) BW 16 : ( s , s), W λ,κ > ∃λ ∈ C • VR (i)BW 16 : ( s , s), W λ,0 >

  BW 16 P ( s , s), W λ i ,0 > C •

-• λ i 2 4 -

 4 BW 16 . Then for any τ i > 0 and any v i ∈ VR (i) BW 16 we have:P{ ( s , s), W v i ,0 > W v i ,0 k 1 /2 • τ i } ≤ e -τ 2 i /2 . (D.7)Using the law of total probability, we can restate the error probability in (D.6) as follows: for λ i ∈ VR (i) BW 16 and constants C i we havePe ≤ L• 3 i=1 VR (i) BW 16 • P { W λi,0 ≥ C i } + P ( s , s), W λi,0 > C • , λ i W λi,0 < C i (D.8)By Replacing λ with λ in (D.8) we obtain:Pe ≤ L • VR (1)BW 16 P W λ 1 ,0 ≥ C1 + L • VR (1) BW 16 • P ( s , s), W λ1 ,0 > C • W λ 2 ,0 ≥ 2C2 + L • VR (2) BW 16 • P ( s , s), W λ 2 ,0 > C • W λ 3 ,0 ≥ 2C3 + L • VR (3) BW 16 • P ( s , s), W λ 3 ,0 > C • , λ 3 W λ 3 ,0 < 2C3Let C 1 be a lower bound for C • e (0) , λ 1 , and C i (i = 2, 3) be a lower bound for C e (0) , λ i . Then we can writeP e ≤ L • VR (1)BW 16 P W λ 1 ,0 ≥ C 1 + L • VR (1) BW 16 • P ( s , s), W λ 1 ,0 > C 1 W λ 1 ,0 < C 1 + L • VR (2) BW 16 P W λ 2 ,0 ≥ 2C 2 + L • VR (2) BW 16 • P ( s , s), W λ 2 ,0 > C 2 W λ 2 ,0 < 2C 2 + L • VR (3) BW 16 P W λ 3 ,0 ≥ 2C 3 + L • VR (3) BW 16 • P ( s , s), W λ 3 ,0 > C 3 W λ 3 ,0 < 2C 3 (D.9)Next, we aim to find suitable values for the constants C 1 , C 2 , C 3 in (D.9).

Table 1

 1

	-based	Dilithium		Kyber	FrodoKEM	5	2
		Falcon		NTRU	NTRU Prime
				SABER
	Code-based			McEliece	BIKE	1	2
					HQC
	Multivariate	Rainbow	GeMSS			1	1
	Stateless Hash or Symmetric based		Picnic
			Sphincs+				2
	Isogeny				SIKE		1
	Total	3	3	4	5	7	8

.1: NIST's third round finalist and alternates.

Table 1 .

 1

2: Common setting for LWE-based KEMs.

Table 1

 1

	Relation to source coding with side information and physical layer security. The
	reconciliation problem is closely related to the problem of source coding with side information,
	i.e. the well-known Wyner-Ziv problem in information theory [WZ76,Kra08] illustrated in Figure
	1.1.
	encoder	X n	p XY	Y n	decoder	Xn	Alice
	R				R

.4: Reconciliation-based KEM.

As shown in Table

1

.4, Bob produces a reconciliation message R using the function HelpRec and uses it to generate the private key µ by applying the function Rec that computes a private key µ given a noisy observation and the reconciliation information. He then sends the message R to Alice. This information aims to correct the bias that exists between V and V . Alice can now use the function Rec to compute the private key µ .

Bob

Figure 1.1: The Wyner-Ziv problem.

Table 2

 2

.1: Asymptotic Notation.

  The corresponding quantization function denoted simply Q Λ (x) finds the closest vector point to x.

	Named after mathematician Georgy Voronoi, the Voronoi region has various applications
	in many fields of science and engineering. Several works in the literature have considered the
	problem of computing the Voronoi region for a given lattice such as [CS82c, CS84, BK18], and a
	recent result shows that it is computationally difficult to calculate the exact number of facets of
	the Voronoi cell for general lattices [DSSV09]. The diamond-cutting algorithm [VB96] computes
	a complete geometrical description of the Voronoi region of any lattice in exponential time and
	space. The memory requirements for this algorithm increase very rapidly with dimension, which
	limits its use to small dimensions. A deterministic algorithm presented in [MV13] allows to
	compute the Voronoi cell of a lattice in time Õ 2 2n .
	The Voronoi region is surrounded by finitely many lattice points. These points are called
	Voronoi relevant vectors. Figure 2.3 illustrates the Voronoi region in gray together with the
	Voronoi relevant vectors. To formalize this definition we need to recall what a bisecting normal
	hyperplane is.

  vector gives rise to a variant of the SVP problem called the γ-approximation version (SVP γ ).

	Definition 2.16 (Closest Vector Problem CVP γ ). Given a lattice Λ in R n , a point t in R n and
	an approximation factor γ(n) ≥ 1, find a lattice vector at distance at most γ • argmin	λ -t .
	λ ∈ Λ
	Definition 2.14 (γ-approximation Shortest Vector Problem SVP γ ). Given a lattice Λ in R n
	and an approximation factor γ ≥ 1, find a non-zero lattice vector of length at most γλ 1 (Λ).
	The approximation factor γ is usually a function of the lattice dimension n and may be
	exponentially large value in n. The famous work by [LLL82] gave a polynomial time algorithm
	that solves SVP γ for γ = 2 n/2 . Later works have improved this result; it is currently known that
	there exists a polynomial time algorithm achieving an approximation factor of 2 n log log n/ log n
	in [AKS01], and several heuristic variants of it are found in [MV10, BLS16, HK17].
	Solving SVP γ for constant values of γ may be a hard problem. In fact, it was shown that
	for approximation factors up to γ = 2 (log n) 1-ε (not polynomial in n, but very close to it), the
	problem is NP-hard [Mic01,Kho05,HR07]. Further, the SVP γ problem is unlikely to be NP-hard for γ = Ω( √ n), as this leads to the equality NP=coNP [Has88, LLS90, Ban93, AR05]. Moreover,
	showing the NP-hardness up to factor n/O(log n) would imply the collapse of the polynomial-
	time hierarchy [GG00]. When γ is taken to be poly(n), the fastest known algorithms to solve
	SVP γ rely on (a variant of) the BKZ lattice basis reduction algorithm [Sch87, SE94a, AKS01,
	GN08, HPS11, ALNSD20].
	The shortest vector problem can be extended to a more generalized form that we call the
	Shortest Independent Vector Problem.
	Definition 2.15 (Shortest Independent Vector Problem SIVP γ ). Given a lattice Λ in R n , find
	n linearly independent lattice vectors v 1 , . . . , v n where v i ≤ γλ n (Λ) for all i = 1, . . . , n.
	This problem is involved in many cryptographic primitives [Ajt96, Reg09, GPV08, Pei10,
	Pei15]. Blömer and Seifert [BS99] showed that SIVP γ is NP-hard for any constant approximation
	factor γ with respect to the Euclidean norm. Micciancio and Voulgaris [MV13] showed that exact
	SIVP can be solved deterministically with Õ 2 2n+o(n) operations. This problem is believed to
	be hard to approximate up to polynomial factors in n, and the best known algorithms within a
	polynomial approximation factors run in time exponential in n [ADRSD15]. Till now, there are
	no known quantum algorithms for solving SIVP γ that outperform classical ones.
	Another important problem associated with lattices is the Closest Vector Problem.

Table 3 .

 3 1: Simplified description of FrodoPKE.

Table 3

 3

	.2 illustrates the failure probability for each level according to the selected parameter
	sets, together with the corresponding ciphertext size.

Table 3

 3

				Known	Known	Best
		m	b	Classical (C)	Quantum (Q)	Plausible (P)
				= log b • 2 0.292b	= log b • 2 0.265b	= log b • 2 0.2075b
	Frodo-640 Primal 712 482	150	137	109
	Dual	716 478	149	136	108
	Frodo-976 Primal 1023 705	216	196	156
	Dual	1040 700	214	195	154
	Frodo-1344 Primal 1244 929	281	256	202
	Dual	1253 923	279	254	201

.3 presents the cost of primal and dual attacks on a single instance of the LWE problem via the FrodoKEM script pqsec.py 2 with parameters n, σ, q. The authors prefer to make a conservative assumption and evaluate the core SVP hardness of the protocol (see Paragraph 3.2). As also mentioned in Paragraph 3.2, the sieving algorithms are used to predict the core hardness, where the cost of vector operations is 2 cb for a well known c (about b • 2 cb CPU cycles).

Table 3 .

 3 3: Security bounds for FrodoKEM in log 2 scale. This illustrates the optimized cost over all possible choices of b -the block dimension of BKZ -and m -the number of used samples.

	After a series of reductions, Table 3.4 represents the resulting security bounds that are
	slightly weaker than the exact values in Table 3.3. The additional column "IND-CCA security
	bound C" represents the bound (3.4), where Adv IND-CPA PKE	is replaced with the best known LWE
	attack.

  64 Z 8 8 . First we define a function f : {0, 1} 8 -→ E 8 /2Z 8 that maps b = [b 1 , b 2 , . . . , b 8 ] ∈ {0, 1} 8 as follows:

  64 Z 8 ∼ = βE 8 /qZ 8 8-dimensional row vector

	7:	for j=0 to 7 do
	8:	O i,j = S (8-i+j) mod 8,j	S i,j is the j-th component of S i
	9:	return O = (O i,j )
	Algorithm 6 Modified decoding algorithm

Finally, E8.Encode is a bijection from {0, 1} to (βE 8 ) 8 /qZ

64

. This allows to define the inverse function E8.Encode -1 (Y) for any Y ∈ (βE 8 ) 8 /qZ 64 as described in Algorithm 5.

Algorithm 5 Inverse of Encoding

Input: Matrix Y ∈ βE 8 /qZ 8 8 Output: m = (m 0 , . . . , m -1 ) ∈ {0, 1} 1: function E8.Encode -1 (Y) 2:

for i=0 to 7 do 3:

m i( /8) , m i( /8)+1 , . . . , m i( /8)+7 = f -1 (Block i (Y)

mod 2) 4: m i( /8)+8 , m i( /8)+1 , . . . , m i( /8)+ /8-1 = g -1 (Block i (Y) -Block i (Y) mod 2) 5: return m = (m 0 , . . . , m -1 ) Decoding Algorithm. The decoding algorithm E8.Decode uses the CVP E 8 algorithm presented in chapter 2 -Algorithm 1. We describe the decoding protocol in Algorithm 6. It concatenates the outputs of CVP E 8 to form an element of (βE 8 ) 8 /qZ 64 . Since our lattice E 8 is scaled by β, we use the fact that CVP βE 8 (x) = β • CVP E 8 1 β x (see Lemma 2.1).

  row vector in βE 8 /qZ 8

	4:	for j=0 to 7 do
	5:

Table 3

 3 Probability of (in multiples of 2 -16 ) Table3.6: Error distributions corresponding to parameter set 2.

	Rényi divergence

.6 for explicit distribution values). Overall, n σ the modulus to noise ratio of the protocol is decreased. As an example, we compute the new bandwidth requirements for the modified Frodo-640 which is log(2 14 )×640+log(2 14 )×8 = 9072, compared to the original FrodoKEM that was log(2 15 ) × 640 + log(2 15 ) × 8 = 9720. This allows to reduce the bandwidth by approximately 7% (see Table 3.7).

Table 3 .

 3 7: Modified parameters for improving the security level and/or bandwidth of FrodoKEM scheme, as well as increasing the private key size.

is equal to 1.4 in Frodo-1344, while still guaranteeing a large number N of discrete Gaussian samples, namely N ≈ 2 111 . For Frodo-1344 we take σ = 1.15, which still leads to a large number of discrete Gaussian samples, namely N ≈ 2 75 .

Table 4

 4

.1: The KyberPKE protocol.

  Table 4.2: Error probability for different parameter sets for KyberKEM.

	512	256 2 3329 3	2	(10, 4) 2 -139
	KyberKEM-768	256 3 3329 2	2	(10, 4) 2 -164
	KyberKEM-1024	256 4 3329 2	2	(11, 5) 2 -174

Table 4 .

 4 3: Security bounds against know primal and dual attacks in log 2 scale [A + 20].

	2

Table 4 .

 4 4: Proposed key encapsulation mechanism with reconciliation, based on Module-LWE.

Table 4 .

 4 Table 4.7. = 3329, n = 256, d= 3, k 1 = k 2 = 2, P e ≤ 2 -164 = 2 11 = 2048, n = 256, d = 3, k 1 = k 2 = 2, p = 5, P e ≤ 2 -174 7: Core hardness of our protocol and comparison with the state of the art. b denotes the block dimension of BKZ, and m the number of used samples. The given costs are the smallest ones for all possible choices of m and b.

	Attack	m	b	Known Classical Known Quantum	Best Plausible
	KyberKEM-512 Round 3: q = 3329, n = 256, d = 2, k 1 = 3, k 2 = 2, P e ≤ 2 -139
	Primal 486 405	118	107	84
	Dual	482 404	118	107	83
	Our Protocol: q = 2 11 = 2048, n = 256, d = 2, k 1 = 3, k 2 = 2, p = 6 , P e ≤ 2 -141
	Primal 473 437	127	115	90
	Dual	493 435	127	115	90
	KyberKEM-768 Round 3: q Primal 658 623 182	165	129
	Dual	670 620	181	164	128
	Our Protocol: q Primal 658 665	194	176	138
	Dual	651 662	194	176	137
	Primal 841 873	255	231	181
	Dual	862 868	253	230	180
	Our Protocol: q = 2 Primal 840 928	271	246	192
	Dual	833 923	269	244	191

KyberKEM-1024 Round

3: q = 3329, n = 256, d = 4, k 1 = k 2 = 2, P e ≤ 2 -174 11 = 2048, n = 256, d = 2, k 1 = 3, k 2 = 2, p = ∞, P e ≤ 2 -168

  t that the coefficients of G 4 (X) decrease when the powers of X increase. That's why, using Remark 3.2, this property holds also for G 8 . Therefore, we can estimate the coefficients of G 8 beyond 213 and hence calculate the required probability P E 0,0 + • • • + E 7,7 ≥ 2β . In fact,P E 0,0 + • • • + E 7,7 ≥ 2β ≤ P E 0,0 + • • • + E 7,7 ∈ 2 13 ; 2 13 + 1024 can be calculated efficiently using Lemma B.1 +P E 0,0 + • • • + E 7,7 ≥ 2 13 + 1025

	Set =	t n	and σ =	s √ 2π	to complete the required result.

verify

Table D

 D k BW n0 Number of reconcilitation bits Number of key bits .1: Values of n 0 and the corresponding minimum values of p and p for which BW n0 is greater than or equal to d min q 2 1 -1 2 p -1 E 8 . The required reconciliation and key bits are illustrated in the last two columns.

			p	p
	16	2	≥ 2	≥ p + 1	256(p -2)	320
	32	2	= 2	≥ 3	512	256
			≥ 3	≥ 4
	64	3	≥ 2	≥ p + 2	256(p -3)	448
	128	3	= 2	≥ 4	512	384
			≥ 3	≥ 5
	256	4	≥ 2	≥ p + 3	256(p -4)	576
	d min	q 2 k 1 -1 2 p-k

  16 • 480 • P W λ 1 ,0 ≥ C 1 + 16 • 3839 • P W λ 2 ,0 ≥ 2C 2 + 16 • 61441 • P W λ 3 ,0 ≥ 2C 3 + 16 • 480 • e -τ 2 1 /2 + 16 • 3839 • e -τ 2 2 /2 + 16 • 61441 • e -τ 2 3 /2 ≤ 2 13 • P W λ 1 ,0 ≥ C 1 + 2 16 • P W λ 2 ,0 ≥ 2C 2 + 2 20 • P W λ 3 ,0 ≥ 2C 3 + 2 13 • e -τ 2 1 /2 + 2 16 • e -τ 2 2 /2 + 2 20 • e -τ 2 3 /2 .In order to obtain the best probability trade-off, we need to choose C i and τ i such that

	Index
	D n lattice, 25	Gosset lattice, 22
	E 8 lattice, 22	IND-CCA security, 29
	Barnes-Wall lattices, 24	IND-CPA security, 29-31
	BDD, 22 BDDwDGS, 44 bisecting normal hyperplane, 17 bounded distance decoding, 22	KEM, 27 key encapsulation mechanism, 27 KyberKEM, 64 KyberPKE, 64
	centered binomial distribution, 36 chosen ciphertext attack, 29 chosen plaintext attack, 29 closest vector problem, 21 coset leaders, 19 CVP, 21	lattice, 14 lattice basis, 14 lattice quantization, 16, 17 Learning With Errors, 40 LWE, 40
	cyclotomic number field, 62	M-LWE, 62
	Decision-LWE, 41 dimension of a lattice, 14 discrete Gaussian distribution, 35 dual attack, 42	Module Learning With Errors, 62 Modules, 62 modulo lattice operation, 16 modulus-to-noise ratio, 41
	dual lattice, 19	negligible function, 13
	enumeration, 20	PKE, 26
	FrodoKEM, 44 FrodoPKE, 45	primal attack, 42 public-key encryption, 26
	Fujisaki-Okamoto transform, 33	quantization error, 16
	full-rank lattice, 14	quotient group, 19
	fundamental region of a lattice, 16	quotient ring, 62
	generator matrix of a lattice, 15	random oracle model, 28

P W λ i ,0 ≥ C 1 ≈ e -τ 2 i /2 ; i = 1, 2, 3.

The distribution of the norm W λ i ,0 is calculated via computer simulations for d ∈ {2, 3, 4} by

Throughout this work, we use the convention that lattice points are always represented as row vectors.

This software is available online at http://magma.maths.usyd.edu.au/calc/ with limited computing power.

This definition differs from that of[START_REF] Langlois | Gghlite: More efficient multilinear maps from ideal lattices[END_REF] in which the logarithm of the sum is used.

This is due to the fact that the the approximation factor Õ(n/α) of the underlying lattice problems depends on the modulus-to-noise ratio, which ensures higher security once it becomes larger.

B+1and k ∈ Z 2 B . Then, dc(ec(k) + e) = k.

https://github.com/lwe-frodo/parameter-selection/blob/master/pqsec.py

The condition σ ≥ 2.12 is imposed in [N+ 20] to allow the reduction from the bounded distance decoding with discrete Gaussian sampling (BDDwDGS) to the decision LWE problem. Note that for efficiency reasons, σ

https://github.com/pq-crystals/security-estimates/blob/master/MLWE_security.py

When expanding the product (e ,0 , e ,1 , . . . , e ,n-1 ) • (s ,0 , s ,1 , . . . , s ,n-1 ) mod X n + 1, one can see that it produces an independent sum of n =

terms in each component, each term of the sum is subgaussian of parameter k 2 1 √ 2π, and that's why we can use Proposition 2.4.

We note that although the lattice E8 is similar to the lattice BW 8 in the sense of Definition 2.5, we have taken a different generator matrix for E8.

rank of a lattice, 14 reconciliation, 8 rounded Gaussian distribution, 35 Rényi divergence, 38 Search-LWE, 40 shortest independent vector problem, 21 shortest vector problem, 20 sieving, 20 similar lattices, 16 SIVP, 21 subgaussian distribution, 37 sublattice, 19 successive minima, 14 SVP, 20 unimodular matrix, 15 volume of a lattice, 15 Voronoi region, 17 Voronoi relevant vectors, 18

Acknowledgment

My work was initiated thanks to the INEX Paris-Seine AAP 2017 project.

KyberKEM

Presentation of the algorithm

In this section we present a simplified description of KyberKEM. The protocol admits three parameter sets called KyberKEM-512, KyberKEM-768, and KyberKEM-1024. Our discussion will mainly focus on the underlying KyberPKE encryption scheme that is the basis of the construction of the KyberKEM protocol using the Fujisaki-Okamoto (FO) transform previously discussed in Subsection 2.3.4.

The public-key encryption scheme KyberPKE is similar to the one in [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] with the main difference being the use of Module-LWE instead of Ring-LWE. Fixing R = Z[X]/(X n + 1), the encrypted message is of a fixed length of n = 256 bits and the corresponding R-module is R d q with d ∈ {2, 3, 4}. The multiplication in R q is performed using the Number Theoretic Transform (NTT) (see [START_REF] James | An algorithm for the machine calculation of complex fourier series[END_REF][START_REF] Longa | Speeding up the number theoretic transform for faster ideal lattice-based cryptography[END_REF][START_REF] Seiler | Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography[END_REF] for further details). In order to implement the NTT efficiently, the modulus q should be a prime number that satisfies q = 1 mod n. For the choice n = 256, the smallest primes satisfying the previous condition are q = 257, q = 769 and q = 3329. The first two values are too small to guarantee the negligible failure probability required for CCA security for KyberKEM, and therefore the authors of [A + 20] chose q = 3329.

A brief illustration of the protocol is given in Table 4.1. The noise vectors in KyberPKE are sampled from the centered binomial distribution ψ k defined in Subsection 2.4.2 for k ∈ {2, 3} that depends on the exponent of the R-module R d q . The extension of ψ k from Z to R is denoted by Ψ k . This choice of error distribution does not significantly decrease security of the scheme compared to a rounded Gaussian distribution, for the reason that those two distributions are close with respect to Rényi divergence (see Subsection 2.4.4). The use of the centered binomial distribution allows a much faster implementation compared to sampling from a discrete Gaussian distribution, which requires a significant algorithmic effort (see [BCNS15,DCRVV15,RVM + 14]).

The definition below is necessary in the following.

Definition 4.3 (Compression and Decompression functions)

. Let b, q be positive integers such that b < log q . The compression function Compress q : Z q → Z 2 b and the decompression function Decompress q : Z 2 b → Z q are defined as:

Note that these functions can be extended to vectors by applying them component-wise.

protocol [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF]. For instance, in [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] the functions HelpRec and Rec can be written as the above form by considering the product lattices Λ 1 = (q D4 /2 p ) 256 , Λ 2 = (q D4 ) 256

and Λ 3 = qZ 1024 . We point out that a dither is not required in our algorithm unlike in [START_REF] Peikert | Lattice cryptography for the internet[END_REF][START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF] since the modulus q is an even number. Unlike NewHope, the proposed protocol is based on Module-LWE and uses the same parameters n, d, k as in KyberKEM. In order to obtain 256 bits of key with n = 256, a higher-dimensional lattice than D4 is needed, which is why we choose the E 8 lattice.

Bandwidth requirements. Focusing only on the data sent by Bob to Alice in KyberKEM-512, our protocol for n = 256, d = 2, q = 2 11 and p = 5 requires to send a pair ( #» u, r) where #» u is an element of R d q (requiring 11×256×2 = 5632 bits) and r ∈ Λ 1 /Λ 2 requires (p-1)×256 = 1024 bits. In total, 6656 bits are needed.

Besides, the two terms Compress q ( #» u, b #» u ) and Compress q (v, b v ) are sent in the original KyberKEM-512, where b #» u = 10 for which Compress q ( #» u, b #» u ) requires 512 × 10 bits, and b v = 4 for which Compress q (v, b v ) requires 256 × 4 bits. In total, 6144 bits are needed. Consequently, our protocol requires slightly more bandwidth (a 8.3% increase) than KyberKEM-512. The same calculations for d = 3 and d = 4 lead to the following table: 4.5: Bandwidth requirements (in bits) for our modification of the three levels of KyberKEM. The choice of p is affected by the decryption failure probability that will be discussed in the next section.

Cost of multiplication in the ring R. Our protocols relies heavily on polynomial arithmetic in the ring R q with modulus q = 2 13 , and polynomial multiplication is a costly operation. As mentioned, since q is not prime, we are replacing the NTT algorithm with Karatsuba/Toom-Cook methods. Asymptotically, NTT polynomial multiplication has complexity of O (n log n), while Karatsuba polynomial multiplication has a higher asymptotic complexity of O n 1.58 .

Though we lose in asymptotic time complexity, we gain in modular arithmetic since modular reduction comes for free. The complexity comparison of NTT versus Toom-Cook is heavily dependent on hardware implementation, see for example Table 2 in [START_REF] Anvers | Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM[END_REF]. For instance, when using C language, the costs of Toom-Cook and NTT are comparable, while with an optimized AVX2 implementation, NTT is much more efficient.

Error Probability Bounds

KyberKEM levels and parameters

Values of p p = 2 p = 3 p = 4 p = 5 p = 6 p = ∞ KyberKEM-512:

Table 4.6: Upper bound for error probability for different values of moduli q, noise parameter k and reconciliation rate parameter p. Note that taking p too small leads to a large error probability, whereas if p is large, the size of the ciphertext c will also be large.

IND-CPA security

Recall from Subsection 2.3.3 that a KEM is IND-CPA secure if an attacker cannot distinguish it computationally from an ideal one, in which the shared private key is truly random. We will prove that, with the choice of q in Subsection 4.4.3, our KEM algorithm is IND-CPA secure assuming the hardness of M -LWE given two samples. This proof is generic and holds in the setting of the key generation protocol in Section 4.4 independently of the choice of the lattices Λ 1 and Λ 2 as long as the operations Q Λ i for i = 1, 2 can be done efficiently. We follow the same argument as in [Pei14, Section 4.2]. We consider the adjacent games below:

Notice that Game 1 is the "real" game corresponding to our modified protocol, and Game 4 is the "ideal" game where the key is uniform and independent from all the random variables observed by the eavesdropper. Game 2 is a modified version of Game 1 in which #» b is taken to be uniform in R d q . The inputs of Game 3 are all uniformly sampled except for the reconciliation message r.

Our aim is to prove that Game 1 and Game 4 are computationally indistinguishable. We'll do so sequentially.

Equivalence of Game 1 and Game 2. Game 1 and Game 2 are computationally indistinguishable under the assumption of hardness of M -LWE. the error probability. However, we failed to obtain a good bound for the error probability, which may be due to the fact that BDD decoding is sub-optimal, and that our bound was based on the subgaussian parameter.

Finally, we mention that designing lattice-based protocols which are at the same time efficient and provably secure is still an open problem. In fact, the parameters chosen for the current NIST candidates based on lattices do not satisfy the hypotheses of the worst-case to averagecase reduction theorems, although they are heuristically assumed to be secure. Therefore, more work is needed to design protocols which ensure a better decryption failure probability and better modulus for larger error variance. This problem was studied in [START_REF] Gates | Reduction-Respecting Parameters for Lattice-Based Cryptosystems[END_REF] but the proposed parameters lead to an inefficient cryptosystem. Such a consideration is therefore of significant interest for future work, and error-correction and reconciliation techniques might be a useful tool to achieve this goal. Error correction could also be a valuable tool for fully homomorphic encryption based on LWE or Ring-LWE [START_REF] Brakerski | Fully homomorphic encryption from ring-lwe and security for key dependent messages[END_REF][START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF], where noise amplification is the main limiting factor for the number of homomorphic operations.

Appendix A

Mathematical implementations, definitions and proofs

A.1 Probability generating function

This section is devoted to review the probability generating function.

Definition A.1 (Probability generating function). Let Z be a discrete random variable taking values in a set

This function allows to calculate the distribution of a sum of independent random variables:

is a sequence of independent (and not necessarily identically distributed) discrete random variables that take values in a lower bounded sets

A.2 Computation of the Rényi divergence

We present here the code written in Mathematica to calculate the Rényi divergence for α = 9 between the rounded distribution Ψ √ 16π and the centered binomial ψ 16 , as it was done in [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF].

A.3 Voronoi relevant vectors for E 8

G := [2 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , -1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 , 0 , -1 ,1 ,0 ,0 ,0 ,0 ,0 , 0 ,0 , -1 ,1 ,0 ,0 ,0 ,0 , 0 ,0 ,0 , -1 ,1 ,0 ,0 ,0 , 0 ,0 ,0 ,0 , -1 ,1 ,0 ,0 , 0 ,0 ,0 ,0 ,0 , -1 ,1 ,0 ,

e le va nt Vec to rs ( E ) ;

A.4 Voronoi relevant vectors for BW 16

G := [2 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 , 1/2 ,1/2 ,1/2 ,1/2 ,0 ,1/2 ,0 ,1/2 ,1/2 ,0 ,0 ,1/2 ,0 ,0 ,0 ,0 , Following the same steps, we can prove that

The algorithm will return the value z (s) in {z + 0 (s), z - 0 (s), z + 1 (s), z - 1 (s)} such that sz (s) is minimal. This is equivalent to saying that z (s)

In any case, the output is of the form λ + ParBW(p, w).

Our next step now is to prove that Proposition A.1 holds for p = 1 or s ∈ C 1 . In this case Algorithm 1 returns SeqBW(0, λ + w). This function is presented in Algorithm 2.

A.5.3 Linearity of SeqBW(r, * )

In this subsection we refer to the functions t(s) = (b(s), ρ(s)) and RMdec(r, t) = RMdec(r, b, ρ) in Algorithms 2 and 3 and to the function ψ :

. Recall that each vector λ in BW n can be written as

where c n ∈ G N and c r ∈ RM n r for r = 0, . . . , n -1. For any 0 ≤ r ≤ n, let

where RMdec = RMdec mod 2.

Proof. Before we start the proof, observe that for c r ∈ RM n r , ψ(c r ) mod 2 = c r . Let's start with n = 1, r = 0. In this case it is easy to see from Algorithm 3 that ψ is the identity function and

So this remains true for

RMdec.

For n = 1 and r = 1 we have 2 r = N . Thus

This remains also true for RMdec. Now we continue by induction: suppose Proposition A.2 holds for (r -1, n -1) and (r, n -1). We want to show that it holds for (r, n). Following the notation in Algorithm 3, we find:

Note that

Now we compute the vector u.

Otherwise,

Then we have

Hence we obtain: Proof. Let's first define the Schur product: for binary vectors x, y ∈ F N 2 , we set

x * y = (x 1 y 1 , . . . , x N y N ).

For n = 1, and r = 0, we have for a, b ∈ RM 1 0 = {(0, 0), (1, 1)}:

Suppose that the hypothesis holds for n, for all r < n. Let (a, b) ∈ RM n+1 r .

-If r < n, then write a = (u, u ⊕ v) and b = (u , u ⊕ v ), where u, u ∈ RM n r and v, v ∈ RM n r-1 . Then

, so the statement is trivially true.

Proposition A.3. For λ r ∈ BW n r and w ∈ C N , we have SeqBW(r, λ r + w) = λ r + SeqBW(r, w).

Proof. We will proceed by decreasing induction on r.

If r ≥ n, then SeqBW is nothing more than the rounding function, and the property holds. Now suppose that the hypothesis remains true for r + 1; let's prove it for r:

A.6 Proof of Proposition 2.2

Lemma A.5.

for n ≥ 4. Then 2 (Φ n ) -2 is an integer matrix.

Lemma A.6. Let n = 2 2α with α ≥ 1 and integer. The two matrices 2 α (G BW n ) -1 Φ -1 n and 2 α (G BW 2n ) -1 are integer matrices.

Proof. The proof follows the induction principle on α. It is easy to verify that property holds for α = 1 by direct calculation, i.e., 2

4 and 2 • (G BW 8 ) -1 are integer matrices. Suppose this property remains true until some integer α, i.e.,

are integer matrices, and let's prove it for α + 1. Note that in this case the lemma must be proven for 4n and for 8n. Using the fact that the inverse of a 2 × 2 block matrix A X 0 B is simply

one can write:

Clearly, by hypothesis and using lemma A.5, each block in (A.1) represents an integer matrix. Now let's study the 8n case:

FrodoKEM simulations

B.2 Calculating the error probability B.2.1 The distribution of one entry of E

We consider here our modified FrodoKEM for which the error standard deviation is σ. Recall from Equation (3.8) that the entries of E are a sum of products of elements distributed according to χ:

The distribution of the product of S i,k E k,j and E i,k S k,j can be efficiently computed for any i, j

and k, by brute-forcing over all the support of χ. We use this result to calculate the probability generating function of the sum of 2n products, plus the initial one that corresponds to E i,j . This is done using Lemma A.1.

B.2.2 The distribution of the sum of two, four and eight entries of E

After calculating the exact distribution of each entry of E , we now need to calculate the distribution of a sum of 2 and 8 entries of E , and this is due to Equation (3.10) illustrated below:

The distribution of E 0,0 + E 1,1 can be obtained from the probability generating function which

. This product can be calculated efficiently. Now regarding the distribution of the sum E 0,0 + • • • + E 7,7 , the product G 8 = 7 i=0 G E i,i would take a long time to compile (around 4 days). To solve this problem, we first calculate G 4 = 3 i=0 G E i,i that represents the probability generating function of a sum of 4 entries of E , and then we use the following lemma:

Lemma B.1 will help us calculate the coefficients of G 8 given only G 4 . It is not hard to

Appendix C

KyberKEM simulations and proofs C.1 Conjugation function's properties

In this section we give some properties of the conjugation function derived from Definition 4.4.

Moreover, if the coefficients of a(Y ) are sampled independently from a well defined distribution, then they will be identically distributed as the coefficients of conj (a) (Y ).

, where δ i,j = 1 if i -j < 0 and 0 otherwise. So k = i -j mod n 0 . Using the identity Y n 0 = -1, we obtain: In this section, we consider again the modified scheme in Table 4.4, where the lattices Λ 1 and Λ 2 are replaced by products of Barnes-Wall lattices BW n 0 with n 0 being a power-of-two.

To obtain a nested sequence Λ 3 ⊆ Λ 2 ⊆ Λ 1 , we need to verify the inclusions of the chosen lattices Λ 1 , Λ 2 and Λ 3 . Accordingly, using Proposition 2.2 which states that for n ≥ 2 and

where q is a power-of-two integer, n = n 0 × L = 256 and β = q 2 k for k ≥ log n 0

2

. In order to obtain the best possible minimum distance for the lattice Λ 2 , we choose the equality k = log n 0 2 . This imposes to have p ≥ k so that Λ 2 ⊆ Λ 1 . Referring to Subsection 2.2.4 and recalling that Vol(BW n0 ) = (n 0 /2) n 0 /2 , the number of reconciliation bits transmitted is

Moreover, the size of the key (in bits) is

For most dimensions, the number of key bits is not very suitable for the proposed application, since key sizes in cryptography are usually powers-of-two (See Table D.1).

As we did in Chapter 4, Equation (4.4), we can establish a polynomial splitting for n 0 (see Subsection 4.4.1) and get the sufficient condition to obtain k = k in Table 4.4, that is

Note that the calculation of the Voronoi-relevant vectors for BW n 0 for large n 0 requires a huge amount of computation. That's why we adopt the sphere bound approach illustrated in Proposition D.1 below in order to cover more general cases. However, the upper bound for the error probability provided by the sphere bound is not as tight as the bound based on Voronoi-relevant vectors.

Proposition D.1. For any n-dimensional lattice Λ, the ball of radius d min /2 is included in the Voronoi region. In other words, for any x ∈ R n , we have

A visual representation of the sphere bound is in Recalling that the minimum distance of BW n 0 is n 0 /2 (see Subsection 2.2.4) and that for a

√ 2 (see Equation (4.4)) for certain values of n 0 , p and p, as shown in Table D.1 and Table D.3. We note that although the minimum distance of BW n 0 is increasing in n 0 , the inclusion Λ 3 ⊆ Λ 2 in equation (D.1) imposes a scaling factor β which decreases with n 0 , so that there is almost no gain in terms of minimum distance when using higher-dimensional lattices.

These are the most promising choices for Λ 2 for which we want to estimate the error probability:

In addition, applying Theorem 2.3 to ω (κ) , we get ∀ > 0 that

That's why, we impose the condition

for which the error probability will be bounded by

Equation (D.5) leads to the following table: k 1 = 2 and k 2 = 2 q = 2 20 =⇒ p ∈ {3, . . . , 8} q = 2 21 =⇒ p = 3 q = 2 22 =⇒ p = 4 q = 2 22 =⇒ p = 4 q = 2 23 =⇒ p ∈ {5, 6}

Goal: P e ≤ 2 -164 q = 2 19 =⇒ p ≥ 9 q = 2 20 =⇒ p ≥ 4 q = 2 21 =⇒ p ≥ 5 q = 2 21 =⇒ p ≥ 5 q = 2 22 =⇒ p ≥ 7 k 1 = 2 and k 2 = 2 q = 2 21 =⇒ p = 3 q = 2 21 =⇒ p = 3 q = 2 22 =⇒ p = 4 q = 2 22 =⇒ p ∈ {4, 5} q = 2 23 =⇒ p ∈ {5, 6, 7}

Goal: P e ≤ 2 -174 q = 2 20 =⇒ p ≥ 4 q = 2 20 =⇒ p ≥ 4 q = 2 21 =⇒ p ≥ 5 q = 2 21 =⇒ p ≥ 6 q = 2 22 =⇒ p ≥ 8

Table D.2: The values of n 0 and the corresponding values of q and p for which the error probability bounds matches the ones in KyberKEM.

This implies that in order to improve upon KyberKEM, we need q to be at least 2 19 , with the number of reconciliation bits transmitted being at least 1762 bits. Note that the value n 0 cannot be smaller than 16 because otherwise the size of the key will be less than 256 bits 2 .

Although the previous discussion fails to find any advantage in choosing Λ 2 to be a product of higher-dimensional Barnes-Wall lattices, this might be due to the fact that the sphere bound is not tight enough. In the next section, we focus on the case n 0 = 16 and try to obtain a better error probability bound.

Parameters: q = 2 11 and p = 5 observing that

We calculated the probability bound for KyberKEM-768 and KyberKEM-1024. In the case of KyberKEM-512, since the centered binomial distribution k 1 is equal to 3, the calculations are out of reach. In fact it requires (2k 1 + 1) 16 ≈ 2 45 operations. Our results are presented in Table D.4.

In conclusion, we were not able to obtain a good error probability bound for q = 2 11 . This may be due to our sub-optimal error bound technique or to the fact that the choice of the lattice BW 16 is ill-suited for this application. In fact, the key rate is larger than needed. We remark that in the first version of the NewHope paper [START_REF] Alkim | Post-quantum key exchange-a new hope[END_REF], where similar bounds based on Lemma D.1 were used, the error bound was of the same order (2 -60 ), which prevented the authors from proving CCA-security.