Abudushalamu Aili

Matthieu Vandamme

Jean Michel Torrenti

Benoit Masson

Addendum to "Is long-term autogenous shrinkage a creep phenomenon induced by capillary effects due to self-desiccation?"

by Abudushalamu Aili a , Matthieu Vandamme a , Jean-Michel Torrenti b , Benoit Masson c a Université Paris-Est, Laboratoire Navier (UMR 8205), CNRS, École des Ponts ParisTech, IFSTTAR, Marne-la-Vallée F-77455, France b Université Paris-Est, IFSTTAR, 14 Boulevard Newton, Champs-sur-Marne F-77420, France c EDF-DIN-SEPTEN, Division GS -Groupe Génie Civil, 12-14 Avenue Dutriévoz, Villeurbanne F-69628, France Prof. F.-J. Ulm brought to our attention that we forgot to include an important reference in our manuscript. Indeed, [START_REF] Ulm | Creep and shrinkage coupling: new review of some evidence[END_REF] showed that, for 5 concretes that differed in their water-tocement ratio and for which basic creep and autogenous shrinkage were measured by Le [START_REF] Roy | Déformations instantanées et différées des bétons à hautes performances[END_REF], the long-term kinetics of autogenous shrinkage could be explained by creep of the solid skeleton under the action of an internal pore pressure. Their conclusion was based on the observed linearity of the relationship between basic creep compliance and increase in autogenous shrinkage in the long term.

From the slope of this linear relationship, they back-calculated an "effective pore pressure" displayed in Figure 1. Interestingly, this uniaxial "effective pore pressure" -merely calculated from macroscopic observables-is in very good agreement (both in terms of magnitude and in terms of trend with water-to-cement ratio) with the capillary stresses that we estimated at the pore scale with the help of micromechanics (see Fig. 6 in our manuscript). The reason for this agreement lies in Eq. 16 of our manuscript, which reads Σ ∞ = σ ∞ and shows that, in the linear viscoelastic case with a viscoelastic Poisson's ratio of the matrix equal to 0.2, the long-term "effective" macroscopic stress Σ ∞ that acts at the scale of the concrete sample is equal to the long-term microscopic stress σ ∞ that acts on the C-S-H gel.

Figure 1: Uniaxial "Effective pore pressure" versus water-to-cement ratio, as reported by [START_REF] Ulm | Creep and shrinkage coupling: new review of some evidence[END_REF]. Figure adapted from [START_REF] Ulm | Creep and shrinkage coupling: new review of some evidence[END_REF].


Jean-Claude Bajard
email: jean-claude.bajard@sorbonne-universite.fr

Julien Eynard
email: julien.eynard@cea.fr

Paulo Martins

Leonel Sousa

Vincent Zucca
email: vincent.zucca@kuleuven.be

An asymptotically faster version of FV supported on HPR

Keywords: Fan-Vercauteren scheme, Residue Number System, Homomorphic Encryption

State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryption and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n 2 log n) to O(n log n) and from O(n 3 log n) to O(n 3 ), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.

I. INTRODUCTION

Since Gentry's uncovering of Fully Homomorphic Encryption (FHE) [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF], a large amount of research has been dedicated to improving its efficiency. While the Fan and Vercauteren (FV) [START_REF] Fan | Somewhat Practical Fully Homomorphic Encryption[END_REF] proposal is one of the most efficient homomorphic schemes, it requires computationally expensive operations on polynomials with large coefficients. The Residue Number System (RNS) [START_REF] Sousa | Combining residue arithmetic to design efficient cryptographic circuits and systems[END_REF] allows to break down large integer arithmetic into many independent smaller channels. With it, additions and multiplications are computed independently for each channel, resulting in a reduction of complexity when compared to traditional positional representations. As a result, state-of-theart implementations of FV are based on the RNS [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF].

However, the non-positional nature of RNS makes it more difficult to implement operations such as division and rounding, which are required by both FV homomorphic multiplication and decryption procedures. Furthermore, while for positional representations the size of the representation of a number is proportional to its magnitude, the RNS representation of a number is as large as the largest number representable in it. During the relinearisation procedure, which dominates the asymptotic complexity of the homomorphic multiplication, polynomial coefficients need to be decomposed to values of smaller magnitude. Hence, after applying this decomposition, the RNS becomes a sub-optimal representation. This work proposes to exploit instead the Hybrid Position-Residues Number System (HPR) [START_REF] Bigou | Hybrid Position-Residues Number System[END_REF] representation of numbers to accelerate the cryptographic operations of FV. This hybrid representation is of a positional nature, but each digit is represented in RNS. It not only inherits the parallel nature of RNS but it also makes the relinearisation, and division and rounding operations more efficient. As a result, in dimension n, the complexity of FV decryption is asymptotically reduced from O(n 2 log n) to O(n log n). Similarly, the complexity of homomorphic multiplications is reduced from O(n 3 log n) to O(n 3 ). Complexity gains are translated in practice into speedups of up to 8.0 and 8.6 for the decryption operation and of up to 2.0 and 1.6 for the homomorphic multiplication, for the parameters considered in this article and two state-ofthe-art schemes, with an upward trend for larger parameters.

The remainder of this article is organised as follows: the FV cryptosystem and the HPR representation are described in Section II. Based on these techniques, our construction is given in Section III. Afterwards, Section IV reviews related art, and Sections V and VI compare the proposed techniques with state-of-the-art methods from theoretical and experimental perspectives, respectively.

II. BACKGROUND

The ring R = Z[X]/(X n + 1) can be thought of as a set of polynomials with integer coefficients and degree smaller than n. R q = R/qR denotes the polynomials in R whose coefficients are reduced modulo an integer q. When q ≡ 1 (mod 2n), elements of R q can be represented in the Number Theoretic Transform (NTT)-domain, which allows for coefficient-wise additions and multiplications [START_REF] Aguilar-Melchor | Topics in Cryptology -CT-RSA 2016: The Cryptographers' Track at the RSA Conference 2016[END_REF]. Henceforth, boldface letters are used to denote polynomials and the infinity norm • ∞ is the largest absolute value of the polynomial's coefficients. The expansion factor associated to R is defined

as δ R = sup a•b ∞ a ∞ b ∞ , for a, b ∈ R -{0} . a ← D and
a ← χ are used to denote that a is drawn uniformly at random from the set D or according to a distribution χ, respectively. The notation | • | q (resp. [•] q ) is used to denote the residue modulo q in [0, q) (resp. in [-q/2, q/2)). Moreover, for a ∈ Q, b = a is used to denote the closest integer b ∈ Z to a. The computational complexity is herein evaluated in terms of the amount of Elementary Modular Multiplications (EMMs), whose operands fit a single machine word, floating point operations (FPOs) and forward and inverse NTTs required.

A. FV cryptosystem

A private-key of the FV scheme [START_REF] Fan | Somewhat Practical Fully Homomorphic Encryption[END_REF] is generated as a polynomial s ← χ key , and the corresponding public-key is computed as:

b = ([-(a • s + e)] q , a) ∈ R 2 q
with a ← R q drawn uniformly at random and e ← χ err . χ key is such that for s ← χ key , s ∞

B key for a small B key , while the distribution χ err has standard deviation σ err such that elements sampled from this distribution have their infinite norm smaller than B err = 6σ err with very high probability.

A relinearisation key is defined with respect to a pair of functions D and P, such that [ D(a), P(b) ] q = [a • b] q and the infinite norm of D(a) is "small". The relinearisation key, which can be interpreted as a vector of pseudo-encryptions of P(s 2 ), is defined as:

--→ rlk = ( P(s 2 ) -( - → e + - → a • s) q , - → a ) ∈ R 2l q where - → e ← χ l err and - → a ← R l q . A ciphertext ct = (c 0 , c 1 ) ∈ R 2 q , encrypting [m] t ∈ R t , satisfies c 0 + c 1 • s = ∆[m] t + v mod
q, where ∆ = q/t . ct can be correctly decrypted as long as the noise v satisfies v ∞ < ∆/2 -|q| t /2, through:

m = t q [c 0 + c 1 • s] q t . (1)
The homomorphic addition of two ciphertexts corresponds to the pairwise addition of their coefficients modulo q. The homomorphic multiplication of ct and ct encrypting [m] t and [m ] t is performed in two steps. First, we compute the three elements ciphertext:

ct mult = t q c 0 • c 0 q , t q (c 0 • c 1 + c 1 • c 0 ) q , t q c 1 • c 1 q ∈ R 3 q (2) satisfying c 0 + c 1 s + c 2 s 2 = ∆[m • m ] t + v mod q.
In a second step, ct mult is relinearised, by multiplying D( c 2 ) by --→ rlk and adding the result to ( c 0 , c 1 ):

ct mult = c 0 + D( c 2 ), --→ rlk 0 q , c 1 + D( c 2 ), --→ rlk 1 q .
The result ct mult , can be decrypted with [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF] to produce [m • m ] t . As homomorphic operations are applied, the noise associated with ciphertexts grows, limiting the number of operations that can be applied.

B. Hybrid Position-Residue Number System

Using [START_REF] Bigou | Hybrid Position-Residues Number System[END_REF] and considering a modulus q such that q = p d , one can represent polynomials a ∈ R q in a positional system of large radix base p -i.e. such that a = d-1 i=0 a i p i with (a 0 , . . . , a d-1 ) ∈ (R p ) d . We view elements representated in HPR as elements of R p [Y ], leading to:

a(Y ) = d-1 i=0 a i Y i
which produces the value of a when evaluated at Y = p.

Moreover, if the modulus p is chosen as a product of small distinct primes, p = pi∈P p i with P = {p 1 , • • • , p k }, the Chinese Remainder Theorem (CRT) states that there is a ring isomorphism between R p and R p1 × . . . × R p k . In this case, the digits a i s can be represented in RNS as f P (a i ) = ([a i ] p1 , . . . , [a i ] p k ) which allows to break down the arithmetic over the large coefficients into several smaller channels and thus enhance performance. The RNS representation can be reversed, and a i recovered, by computing:

f -1 P ([a i ] p1 , . . . , [a i ] p k ) = k i=1 [a i ] pi p i p pi p p i p = k i=1 a i p i p pi p p i -α i p (3)
with α i ∞ ≤ (k -1)/2. However, since the HPR is of a positional nature, one has to consider the propagation of carries over the digits after additions or multiplications. In order to compute the carries, the digits should be able to grow larger than p. Thus, the digits arithmetic cannot be performed directly modulo p and a second RNS basis B = {b 1 , . . . , b k } is adjoined to P. 1) Carry Propagation: In order to approximate the carry caused by the i th digit, ν i = ai p , we add a modulus b sk to B to form B sk , and use a Shenoy-Kumaresan approach [START_REF] Shenoy | Fast Base Extension Using a Redundant Modulus in RNS[END_REF]. First, we use a fast base extension (FBE),

FBE(a i , P, B sk ) = k i=1 a i p i p pi • p p i mod b b∈Bsk to obtain [a i ] p + α i • p in base B sk .
Then, the approximated carry νi = (a i -FBE(a i , P, B sk ))p -1 = ai p -α i is produced in B sk . To finalise the procedure, the value of νi is extended exactly to P. An inexact extension first computes

FBE( νi , B, P) = νi + α i • b in basis P with b = b 1 • • • b k and α i ∞ (k -1)/2.
Then, the extra residue modulo b sk is used to correct α i • b, by computing α i with:

[α i ] bsk = 1 b i=1 a i b i b bi b b i -[ ci ] bsk bsk .
With this procedure, values νi < λB, for some λ > 0, can be exactly represented and extended from B so long as b sk ≥ 2(k + λ) [4, Lemma 6]. For the parameters considered in this article, b sk can have the same bitwidth as the other moduli in P and B, which is enough to get the residues of

[a i ] p + α i • p and of νi = ν i -α i in P ∪ B sk .
Afterwards, νi can be added to the digit of index i + 1 and one can re-run the procedure to compute the carry νi+1 caused by the digit of index i+1. If one assumes an element to belong to R q , the representation of the Most Significant Digit (MSD) in basis B can be discarded. The MSD is implicitly multiplied by p d-1 , so any value larger than p/2 in absolute value would lead to representations larger than q/2 = p × p d-1 /2, which are redundant.

Computational cost. The computation of a carry for a single HPR digit requires a first fast base extension from P to the k + 1 moduli of B sk (nk(k + 2) EMMs), followed by the product by 1/p in base B sk (n(k + 1) EMMs), and a Shenoy-Kumaresan extension (n(k 2 + 3k + 1) EMMs). Finally, since, when operating modulo q, carries are consecutively computed for all the digits but the last, the carry propagation procedure applied to an element in R d p requires the following amount of EMMs:

C 1_carry = n(2k 2 + 6k + 2) EMMs C all_carries = (d -1) • C 1_carry .

III. PROPOSED HPR-BASED CONSTRUCTION

In this section, we propose an efficient HPR variant of the FV scheme. Key generation, encryption and homomorphic addition take place as in the original scheme [START_REF] Fan | Somewhat Practical Fully Homomorphic Encryption[END_REF], but with polynomial coefficients represented in HPR.

A. Proposed HPR-based Decryption Algorithm

In this section, an HPR-based method for FV decryption is proposed. We assume that the HPR representation of a ciphertext (c 0 , c 1 ) ∈ R 2 q , with:

c i (Y ) = d-1 j=0 c i,j Y j
having digits satisfying c i,j β • p for i = 0, 1 and 0 j d -2: β may take the value of k/2 if carry propagation has been applied; or might be even slightly larger for cases where the ciphertext represents an homomorphic sum. Lemma 1 proves that, for the considered setting, the value of c 0 (p) + c 1 (p) • s can be efficiently approximated having only access to the mod-P representation of the MSD of c 0 and c 1 without causing a large error. This reduces by a factor of d the number of NTTs one needs to compute.

Lemma 1. For i = 0, 1, let c i be such that c i,j ∞ βp for j ∈ [[0, d -2]], then: [c 0,d-1 + c 1,d-1 • s] p = ∆[m] t + v + qu p d-1 + e + • p (4)
for some ∈ R, with the error e verifying e ∞ p p-1 β(1+ δ R B key ).

Proof. In Appendix A.

Decryption consists of efficiently computing (5) modulo t based on the values of c 0,d-1 and c

1,d-1 . t • [c 0,d-1 + c 1,d-1 • s] p p = [m] t + ẽ + t(u + ) (5) with ẽ = t • v -|q| t [m] t + tp d-1
e /q which has a norm bounded up by:

ẽ ∞ t q v ∞ + t|q| t 2q + t p -1 β(1 + δ R B key ) (6)
We use a strategy similar to [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] to compute (5) with a fast basis extension but without any error. By scaling the computation in ( 5) by an integer γ, any extension errors will be detected since they will be nonzero modulo γ. After efficiently getting [γt(c 0,d-1 +c 1,d-1 •s)] p +αp through a fast conversion from P to {γt}, one can compute:

r = (γt[c 0,d-1 + c 1,d-1 • s]p -([γt(c 0,d-1 + c 1,d-1 • s)]p + αp))/p = (γt[c 0,d-1 + c 1,d-1 • s]p -γ[t(c 0,d-1 + c 1,d-1 • s)]p)/p -α + (γ[t(c 0,d-1 + c 1,d-1 • s)]p -[γt(c 0,d-1 + c 1,d-1 • s)]p)/p = γ t [c 0,d-1 + c 1,d-1 • s]p p -α + γ [t(c 0,d-1 + c 1,d-1 • s)]p p = γ ([m]t + ẽ ) + γ [t(c 0,d-1 + c 1,d-1 • s)]p p -α = γ[m]t + γ ẽ + γ [pẽ] p p -α mod γt. (7)
Now, through the application of Lemma 2 to [START_REF] Aguilar-Melchor | Topics in Cryptology -CT-RSA 2016: The Cryptographers' Track at the RSA Conference 2016[END_REF],

[m] t can be computed as (r -[r] γ )/γ mod t. Lemma 2. Let γ > k/2 and α ∞ (k -1)/2. If we have v ∞ < q 2t 1 - k γ - 2tβ p -1 (1 + δ R B key ) - |q| t 2 (8)
then ẽ = 0, and γ

[pẽ] p p -α γ = γ [pẽ] p p -α.
Hence, the correction technique from [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] works.

Proof. In Appendix B.

B. Summarising

Here we summarise the above-described decryption steps.

First, c 0,d-1 + c 1,d-1 • s is computed as an approximation to (c 0 (p) + c 1 (p) • s)/p d-1 with kNTT + nEMM + kNTT -1 . Then (7) is computed modulo γt. Notice that since γt • [c 0,d-1 + c 1,d-1 • s] p = 0(modγt)
, the expression for r can be simplified as:

r = -([γt(c 0,d-1 + c 1,d-1 • s)] p + αp) p mod γt = -FBE([γt(c 0,d-1 + c 1,d-1 • s)], P, γt).p -1 mod γt
which costs knEMM + knEMM γt to compute if γt fits one machine word. Then the message is extracted by using the centred remainder of r modulo γ since [m] t = (r -[r] γ )/γ mod t under the conditions of Lemma 2. Notice that as in [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], if γ is chosen as a power of two, division by γ can be replaced with a shift. Hence, the decryption algorithm has a computational cost of:

k NTT + 2kn EMM + k NTT -1 + kn EMM γt .

C. Proposed HPR-based Homomorphic Multiplication

In this section, an HPR-based method for FV homomorphic multiplication is proposed. We consider two ciphertexts ct = (c 0 (Y ), c 1 (Y )) and ct = (c 0 (Y ), c 1 (Y )), with their elements represented in HPR, encrypting respectively m and m , such that

c 0 + c 1 • s = ∆[m] t + v + rq and c 0 + c 1 • s = ∆[m ] t + v +
r q where r and r satisfy:

r ∞ , r ∞ δ R B key + 1 2 + 1 r ∞ . (9)
The polynomial digits are assumed to be bounded in a similar way to how they were bounded during decryption in Section III-A, i.e. for (i,

j) ∈ {0, 1} × {0, . . . , d - 1}, c i,j ∞ , c i,j ∞ β • p with β k/2.
Until now, we only needed to represent the digit of index d -1 in basis P, since we were dealing with elements of R modulo q. However, during homomorphic multiplication, the first product in (2) is not reduced modulo q. Therefore we have to extend the digits of index d -1 to the basis P × B sk . This extension is done exactly with the approach of [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF], denoted HPS in the rest of the paper. First,

FBE(c i,d-1 , P, B sk ) = [c i,d-1 ] p + α i • p is computed.
Then, α i is produced as:

α i =      k j=1 c i,d-1 pj p pj p j      (10)
by using floating point operations to compute the quotients and by rounding to the nearest integer. Finally, the term α i • p is subtracted from the intermediate result. The lifting procedure of one digit has a practical complexity of n(k 2 +3k+1) EMMs and n(k + 1) Floating-Point Operations (FPOs).

Note that the approximation of [START_REF] Bajard | Note on the noise growth of the RNS variants of the BFV scheme[END_REF] with floating point arithmetic may lead to an erroneous computation of α i . There is a region Z + 1 2 ± , where is related to the used precision and the number of moduli in the basis P (| | < 2 -50 for IEEE 754 double precision and k < 8), to which the value computed in (10) may belong before rounding, causing a possible error of at most 1. While one can detect when this happens, and redo the computation with a higher precision to reduce , we have chosen, as in [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF], to skip this error detection. We will discuss the possible effects of this choice in Remark 1.

At this point we aim at computing (2). To do so we start by computing the NTTs of all the digits of the two input ciphertexts (4d(2k + 1) NTTs in total). Then the product

( c 0 (Y ), c 1 (Y ), c 2 (Y )) is computed with a Karatsuba pattern.
The products of polynomials in Y are performed as usual, i.e. in the power basis, and the products of digits, which are in NTT form, are made component-wise. Since the product is not reduced modulo q, no reduction modulo Y d is done. Thus we obtain polynomials of degree (2d -2) in Y . The division by q = p d and the rounding can be approximated by computing only the d -1 MSDs of the products. Nonetheless, in order to reduce the noise added by this approximation, we also keep the carry coming from the digits of index d -1.

Lemma 3. Let i ∈ {0, 1, 2} and c i,d-1 /p -α i,d-1 be the carry coming from c i,d-1 with α i,d-1 ∞ (k -1)/2 (see Section II-B1). We have:

c i,d-1 p -α i,d-1 + c i,d +• • •+ c i,2d-2 •p d-2 = c i q +e i (11)
with:

e i ∞ 6δ R tβ 2 p d -1 p -1 - 1 -p -d (p -1) 2 + k 2 B e . (12)
Proof. In Appendix C.

The three polynomials of degree d -1 in Y described in Lemma 3 approximate (2) with an error e i . They may be interpreted as encrypting [m•m ] t . The next proposition states the inherent noise of this new ciphertext, depending on the input noises v and v .

Proposition 1. For i ∈ {0, 1, 2}, let ĉi = c i,d-1 p -α i,d-1 + 2d-2
j=d c i,j • p j-d as in [START_REF] Pöppelmann | Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware[END_REF], then we have:

ĉ0 + ĉ1 • s + ĉ2 • s 2 ≡ ∆ • [m • m ] t + v mod q with: v ∞ δ R t (r ∞ + 1/2) ( v ∞ + v ∞ ) + δ R min( v ∞ , v ∞ )/2 + t 2 δ R (1 + r ∞ ) + B e 1 + δ R B key + δ 2 R B 2 key + 1/2(t + 1) (13)
and where B e is as in (12) and r ∞ is as in [START_REF] Ahmad Al Badawi | Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme[END_REF].

Proof. In Appendix D.

Remark 1. In the case where an error has occurred in the HPS basis extension, before the multiplication, then we would operate on c i +qu with u ∞ = 1 (or c i +qu with u ∞ = 1). In this case r ∞ would increase to 3(δ R B key +1)/2+1. As explained in [5, Section 4.5], this would only impact the size of δ R t (r ∞ + 1/2) ( v ∞ + v ∞ ) by less than 3% in the worst case. Considering that this error occurs with probability smaller than 4n•2 -50 ≤ 2 -32 on each multiplication (for n ≤ 2 16 ), its effect on the noise growth in practice is negligible.

In practice, after having computed ( c 0 (Y ), c 1 (Y ), c 2 (Y )), the carries of c0,d-1 and c1,d-1 are computed and stored apart. These are then added after the relinearisation step to the final output to reduce the overall computational complexity. The computation of the two carries requires 2(2k + 1) NTT -1 to leave the NTT representation, and 2 × C 1_carry . Moreover, the carry generated by c2,d-1 is only computed and propagated during the relinearisation step. Therefore, at this point the three elements ciphertext has the d-1 MSDs of c0 and c1 and the d MSDs of c2 in NTT representation; and the two carries stored apart in coefficient representation.

Computational cost. Overall, assuming that each vectormatrix product is performed with a naive algorithm, the homomorphic multiplication (before relinearisation) requires:

C mult. = n(4k 2 + 12k + 4)EMMs + n(4k + 4)FPOs +4d(2k + 1) NTTs + 2(2k + 1) NTTs -1 +3nd(2k + 1)(d + 3)/2 EMMs + 2 • C 1_carry .

D. Relinearisation

At the beginning of relinearisation, the d MSDs of c2 are converted from the NTT to the canonical domain at a cost of d(2k + 1) NTT -1 . Then, carry propagation is applied and the Least Significant Digit (LSD) is discarded, producing ĉ2 , as per Proposition 1. By construction, the digits a = ([a 0,P , a 0,B ], . . . , [a d-1,P , a d-1,B ]) HPR that result from propagating carries satisfy:

Y i f -1
P∪B ([a i,P , a i,B ]) q = Y i FBE(a i,P , P, {q}) q (14)

where f -1 P∪B corresponds to reverting the RNS representation with respect to the (P, B) basis (see [START_REF] Sousa | Combining residue arithmetic to design efficient cryptographic circuits and systems[END_REF]). Concretely, this means that once the carry propagation has been done, the residues of ĉ2 in base B are no longer required for the relinearisation process. [ĉ 2 • s 2 ] q can be rewritten as:

[ĉ 2 • s 2 ] q = d-1 i=0 FBE(ĉ 2,i , P, {q}) • s 2 Y i q =   d-1 i=0 k j=1 ĉ2,i p j p pj p p j Y i s 2   q . ( 15
)
Thus, we can define D(ĉ 2 ) and P(s 2 ) as the vectors with entries r i,j = ĉ2,i pj p pj and ψ i,j = p pj Y i s 2 q , respectively, for 0 i d -1 and 1 j k. Clearly, the r i,j ∞ < p j /2 are small, and D(ĉ 2 ), P(s

2 ) q = [ĉ 2 • s 2 ] q .
The relinearisation-key ( --→ rlk) is composed of pseudoencryptions of the ψ i,j values. To produce the pseudoencryption with respect to ψ i,j , a Ring Learning with Errors (RLWE) sample ([-(a i,j • s + e i,j )] q )), a i,j ) is drawn, and p pj • s 2 is added to the i-th digit of the first element. Then, the whole relinearisation key is stored in NTT form.

Remark 2. Note that, since s 2 ∞ δ R B 2
key < p j for moduli p j of practical size, p pj • s 2 is representable as a single HPR digit. Thus, the RLWE samples used to mask the ψ i,j = p pj • Y i • s 2 , for a fixed i and 1 ≤ j ≤ k, do not need to have a degree higher than i in Y . The d -1 -i MSDs of the k elements of the relinearisation-key associated with these ψ i,j can be set to zero. In practice, RLWE samples are drawn with respect to a modulus p i p d , but with an error of same standard deviation σ err . This technique allows us to not only reduce the size of --→ rlk, but also to further reduce the practical complexity of the relinearisation. When a small polynomial r i,j has been extracted from a residue modulo p j , it is easily extended to the base (P, B sk ) through a simple copy-paste operation. Then, since its representation is a single digit, the computation of its NTT form only requires (2k+1) NTTs. In the next step, the polynomials r i,j are multiplied by the corresponding --→ rlk elements and the results are accumulated in ĉ0 , ĉ1 .

The relinearisation step causes an increase in the noise associated with the ciphertext. More concretely, for a homomorphic multiplication result ( c 0 , c 1 ), one gets:

[ c 0 + c 1 s] q = ĉ0 + ĉ1 • s + D(ĉ 2 ), P(s 2 )- ( - → e + - → a • s) + D(ĉ 2 ), - → a • s q = ĉ0 + ĉ1 • s + ĉ2 • s 2 -D(ĉ 2 ), - → e q = ĉ0 + ĉ1 • s + ĉ2 • s 2 + e relin q .
The extra noise caused by this step is bounded by:

e relin ∞ δ R • d • B err • (p 1 + • • • + p k ). (16)
Computational cost. After the carry propagation of the d MSDs of c2 , we have to compute the NTTs of 1-digit polynomials r i,j in base (P, B sk ) for a total of dk(2k + 1) NTTs. Then, for each j, the single-digit polynomials r i,j are multiplied by two relinearisation-key elements of degree i, resulting in a total of nkd(d + 1)(2k + 1) elementary products. The results of these products are added to c 0 and c 1 . Once all intermediate products have been accumulated, 2d(2k + 1) NTT -1 s are used to obtain the result in the canonical domain. Finally, carry propagation is applied to c 0 and c 1 . Thus, the total cost of the relinearisation step is:

C relin. = dk(2k + 1) NTTs + 3d(2k + 1) NTTs -1 +nkd((d + 1)(2k + 1) + 1) EMMs +(3d -2)C 1_carry .
Remark 3. The bit size of the noise grows linearly with the multiplicative depth L. Consequently, when the depth L reaches around L max /d, the noise affects more than one digit. At this point one can apply a coarse grain decomposition to decrease the practical complexity of the relinearisation. The sum with index j in (15) can be computed by the decomposition function prior to the product with the relinearisation key. With this technique, the decomposition polynomials become r i = k j=1 ĉ2,i pj p pj p pj , and the new relinearisation key contains ψ i = Y i s 2 q . Since r i is no longer a single residue, its conversion toward base B is not a simple copypaste. However, the carry propagation performed prior to the relinearisation already involves such a base conversion. So, r i is obtained in the full RNS base at no extra cost. Moreover, one may disregard an increasingly larger number of LSDs during relinearisation as noise grows. Assuming that only the d MSDs are taken into account for ĉ2,i (in the case where

L (d -d ) Lmax d )
, the cost boils down to:

C relin.,d = d (2k + 1) NTTs + 3d (2k + 1) NTTs -1 +nd (d + 1)(2k + 1) EMMs +(3d -2)C 1_carry
.

IV. RELATED ART

A first adaptation of FV to the RNS was achieved in [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF]. Due to the reduced complexity, speedups from 2 up to 4 and from 5 up to 20 were achieved for the homomorphic multiplication and decryption operations, respectively, in comparison to an implementation based on a generic multiprecision library. Later, [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] proposed modifications to [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], namely by computing part of the RNS basis extensions with floating point arithmetic.

It has been noticed in [START_REF] Ahmad Al Badawi | Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme[END_REF] that for similar cryptographic parameters, [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] offers a lower multiplicative depth than [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF]. However as pointed out in [START_REF] Bajard | Note on the noise growth of the RNS variants of the BFV scheme[END_REF], this observation results from a misimplementation of the techniques of [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] in the SEAL and PALISADE libraries. Thus, since there is no clear advantage of using one version over the other, herein, we make use of techniques from both [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] and [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF].

V. COMPLEXITY ANALYSIS

The complexities of our HPR-based variant of the FV scheme and of [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] are presented in Table I which, for simplicity, associates both forward and inverse NTTs with the NTTs column. K RN S corresponds to the size of the RNS bases of [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF]. Both [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] make use of secondary bases of size K RN S + 1. In HPR, each polynomial coefficient is associated with d digits, each of them represented in an RNS basis of size k, and a secondary RNS basis with k + 1 moduli. If both systems target the same security level and use moduli of similar bitwidth, the value of k will be about d times smaller than K RN S , since q 1 . . . q K RN S ≈ (p 1 . . . p k ) d .

A. Decryption

In all schemes, the computational cost is dominated by the amount of NTTs. A radix-2 NTT requires n 2 log 2 n EMMs [START_REF] Pöppelmann | Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware[END_REF]. In practice, [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] require K RN S forward NTTs and K RN S inverse NTTs; whereas k forward NTTs and k inverse NTTs are required for the HPR-based decryption. As a consequence, the cost of decryption in HPR is nearly d times smaller than that of [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF]. For security reasons, K RN S and K = d×k are in O(n). Hence, since NTTs have a quasi-linear complexity, the asymptotic complexity of the decryption is reduced from:

C(Dec RNS ) ∈ O(n 2 log n) to C(Dec HPR ) ∈ O(n 1+ε log n)
when k = K ε , with 0 ε 1 (ε = 1 being the RNS variant, and ε = 0 the radix-p 1 positional variant). As a consequence, when the number of digits d increases, k and ε decrease, which results in a more efficient decryption algorithm. In particular for d = K, and thus k = 1, we obtain a quasilinear complexity.

B. Homomorphic Multiplication

Using the same method than previously, since K RN S and K ∈ O(n), the asymptotic complexity of [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] is:

C(Mult RNS ) ∈ O(n 3 log n)
while for our HPR variant it is reduced to:

C(Mult HPR ) ∈ O(n 2+ε log n + n 3 ) = O(n 3 ).
Since asymptotically the choice of ε does not impact the complexity of homomorphic multiplication, it would seem best to take ε = 0 so as to minimise the cost of the decryption procedure. However, homomorphic multiplication is executed more often and is the practical bottleneck of these schemes. Hence, one should rather minimise its computational cost by considering the optimal k n , or equivalently d n , in dimension n, that minimises the costs presented in Table I.

Remark 4. When Remark 3 is considered, the asymptotic complexity of relinearisation can be reduced to

O(dkn log(n) + nd 2 k) = O(n 2 log(n) + n 3-ε ) = O(n 3-ε ).

VI. EXPERIMENTAL EVALUATION

The NTT-based Fast Lattice (NFL) library [START_REF] Aguilar-Melchor | Topics in Cryptology -CT-RSA 2016: The Cryptographers' Track at the RSA Conference 2016[END_REF] was adapted to handle moduli with the bitwidths featured in Table II. Our HPR-based variant and [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] were implemented in C++, using the modified NFL library [START_REF] Aguilar-Melchor | Topics in Cryptology -CT-RSA 2016: The Cryptographers' Track at the RSA Conference 2016[END_REF] 1 . They were compiled with gcc 8.3.0 and executed on a single thread on an Intel Core i7-6700K processor running at 4.0GHz with 32GB of main memory, operated by CentOS 7.3. Experimental results for the proposed HPR-based scheme and [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF], for the cryptographic parameters presented in Table II, are depicted in Table III.

Asymptotically, decryption has a speed-up that is linear with n. This behaviour is more noticeable for n ≥ 2 14 in Table III because therein k = 1 is featured for n = 2 13 and k = 3 for n ≥ 2 14 , since k was chosen to minimise the complexity of homomorphic multiplication. Maximum speed-ups of 8.6 and 8.0 are achieved when the proposed HPR-based scheme is compared with [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] and [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF], respectively, for n = 2 16 .

Table III suggests that the theoretically predicted O(log n) speed-up for homomorphic multiplication is only achieved in practice for large parameters. While the novel HPR-based representation brings performance improvements to the multiplication part of the procedure (i.e. without relinearisation), that are noticeable for most parameters, the complexity improvements pertaining to relinearisation only take effect for n ≥ 2 16 . This suggests that the proposed HPR-based scheme is preferable to [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] for applications relying on sums of products, wherein relinearisation is only applied once, after computing the homomorphic sum of the optimised products, or when large parameters (n ≥ 2 16 ) are considered. Maximum speed-ups regarding the whole procedure of 2.0 and 1.6 are achieved when the proposed scheme is compared with [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF] and [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF], respectively.

Moreover, we have measured the depth reached in practice for each scheme by squaring several ciphertexts until they did not decrypt correctly and keeping the smallest value as the practical multiplicative depth. We have not observed any significant difference between the HPR and the RNS variants, which confirms the conclusions of [START_REF] Bajard | Note on the noise growth of the RNS variants of the BFV scheme[END_REF].

CONCLUSION

Whereas state-of-the-art implementations of FV make use of the RNS, the FV scheme requires operations that are inefficient to implement in this representation. In particular, division and rounding require large basis extensions, and the representation of small values is ample. Herein, an alternative approach to accelerate FV was proposed, supported on HPR. Divisions are approximated by considering only the MSDs of HPR values, reducing the asymptotic complexity of decryption from Table III: Execution time (ms) of decryption and homomorphic multiplication for the HPR-based variant, [START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] and [START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF].

O(n 2 log n) to O(n log n). Since the homomorphic multiplication operation also depends on division and rounding, it also benefits from the use of HPR. Moreover, since in HPR small values can be represented as a single digit, the amount of NTTs one needs to compute during relinearisation is significantly reduced. As NTTs no longer dominate the asymptotic complexity of homomorphic multiplication, its complexity is reduced from O(n 3 log n) to O(n 3 ), when compared to RNSbased approaches. Experimental speedups of up to 8.0 and 8.6 for the decryption operation and of up to 2.0 and 1.6 for the homomorphic multiplication are achieved when compared with two state-of-the-art schemes. The experimental results also confirm the asymptotic gain since the speed-ups increase as n grows.

Table I :

 I + (23d + 4)k + 7d + 2 n((2d 2 + 8d + 4)k 2 + (5d 2 + 28d + 8)k + 2d 2 + 10d) n(4k + 4) Computational costs of decryption and homomorphic multiplication for the proposed HPR-based scheme,[START_REF] Bajard | A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes[END_REF] and[START_REF] Halevi | An Improved RNS Variant of the BFV Homomorphic Encryption Scheme[END_REF].

		Scheme	DECRYPTION NTTs EMMs FPOs	NTTs		MULTIPLICATION & RELINEARISATION EMMs	FPOs
		[4]	2dk 3ndk	-	(dk) 2 + 16dk + 7	n(12(dk) 2 + 35dk + 17)	-
		[5]	2dk	ndk n(1 + dk)	(dk) 2 + 16dk + 7	n(12(dk) 2 + 35dk + 14)	n(10dk + 13)
	HPR 2dk 2 Par. 2k 3nk -n log 2 q K RN S log 2 q i (RNS) A 2 13 275 5 55	K = k × d 5 = 1 × 5	log 2 p i (HPR) 55
	B	2 14	549	9	61	9 = 3 × 3	61
	C	2 15	1098	18	61	18 = 3 × 6	61
	D	2 16	2196	36	61	36 = 3 × 12	61

Table II :

 II Parameters achieving at least 100 bits of security according to the estimator of[START_REF] Albrecht | On the concrete hardness of Learning with Errors[END_REF] with σ err = 8.0. Values of k and d were computed by minimizing the cost of homomorphic multiplication presented in TableI, assuming that 1 NTT = n log 2 (n) EMMs and 1 FPO = 1 EMM.

	Par.	Scheme	Dec.	Mult.	Rel.	Mult. + Relin
	A	HPR	0.75	32.0	24.7	56.7
	A	[4]	2.64	28.3	13.3	41.6
	A	[5]	2.36	36.8	13.2	50.0
	B	HPR	6.46	132	135	267
	B	[4]	12.8	157	97	254
	B	[5]	12.1	199	95	294
	C	HPR	14.7	705	892	1,597
	C	[4]	64.5	840	775	1,615
	C	[5]	58.5	1,164	784	1,948
	D	HPR	33.2	3,925	5,688	9,613
	D	[4]	285	8,227	7,118	15,345
	D	[5]	267	12,298	7,018	19,316

The code is available at https://gitlab.com/fvhpr/hare

ACKNOWLEDGEMENTS

This work was partially supported by Portuguese funds through Fundação para a Ciência e a Tecnologia (FCT) with reference UIDB/50021/2020 and by the Ph.D. grant with reference SFRH/BD/103791/2014; by the ANR grant AR-RAND 15-CE39-0002-01; through the Pessoa/Hubert Curien programme with reference 4335 (FCT)/40832XC (CAMPUS-FRANCE); by EU's Horizon 2020 research and innovation programme under grant agreement No. 779391 (FutureTPM). This work was also partially supported by CyberSecurity Research Flanders with reference number VR20192203, by the Office of the Director of National Intelligence (ODNI) and by Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006. J. Eynard was initially supported by University of Toulon (France) for this project.

Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the ODNI or IARPA.

The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.

APPENDIX A PROOF OF LEMMA 1

A valid encryption of [m] t satisfies c 0 + c 1 • s = ∆[m] t + v + uq. Thus we have that the approximation in (4) satisfies:

. The norm of e can thus be bounded as

APPENDIX B PROOF OF LEMMA 2

First, we show that if

Finally, it will be shown that (8) implies (17). This is achieved by exploiting [START_REF] Bigou | Hybrid Position-Residues Number System[END_REF] to bound ẽ ∞ , and as consequence v ∞ :

Through a manipulation of the previous expression, ( 8) is finally reached:

APPENDIX C PROOF OF LEMMA 3

For i ∈ {0, 1, 2} we have by definition:

Moreover, given that the digits of c l and c l , for l = 0, 1, have their norm smaller than βp then:

(18) Now by using the second bound for every c i,j we can write:

Recalling that p d = q, we have:

and then we deduce [START_REF] Pöppelmann | Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware[END_REF] with:

. In particular, we obtain ( 12):

As shown in [START_REF] Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF], we have:

. However in the conditions herein considered, we need also to take into account the errors e i coming from [START_REF] Pöppelmann | Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware[END_REF], thus: