Rémi Leluc
email: remi.leluc@telecom-paris.fr

Elie Chedemail
email: elie.chedemail2@ensai.fr

Thi Thu

Quyen Nguyen
email: thi-thu-quyen.nguyen@inria.fr

Fully Homomorphic Encryption and Bootstrapping

Keywords: homomorphic encryption, bootstrap, (ring) learning with errors, blind rotation ©2022 SEME Report -Ravel Technologies

This report is the result of a work done during the SEME (Semaine d'Étude Mathématiques Entreprise) in Rennes (May 2nd -May 6th 2022). The project presented here concerns the company Ravel Technologies and deals with the field of homomorphic encryption for secure data processing. Homomorphic encryption is an encryption that allows users to do computations on encrypted data without first decrypting them. An encryption algorithm must switch with elementary operations, which are at least addition and multiplication. A straightforward application of a homomorphic encryption for the delegation of calculations concerns cloud computing service where there is a need to perform calculations while preserving the confidentiality of the data, e.g. for the medical and banking sectors. Among possible algorithms, those that have become popular over the last ten years are based on the socalled Learning With Errors (LWE) problem, for performance and security reasons. Since this technique introduces noise into the encryption, which can grow during homomorphic computations to the point that later decryption fails, it is necessary to consider a noise reduction method such as bootstrapping.

Introduction

Context. Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting them. These resulting computations are left in an encrypted form which, when decrypted, results in an identical output to that produced had the operations been performed on the unencrypted data. This allows data to be encrypted and out-sourced to commercial privacy-preserving cloud environments for processing, all while encrypted. An encryption scheme that supports arbitrary computations on ciphertexts is known as fully homomorphic encryption (FHE). Such a scheme enables the construction of programs for any desirable functionality, which can be run on encrypted inputs to produce an encryption of the result. Since such a program do not need to decrypt its data, it can be run by an untrusted party without revealing its inputs and internal states. Fully homomorphic encryptions have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing and many applications for the banking and medical sectors.

Historical background. With the breakthrough discoveries of key exchange in 1976 [START_REF] Diffie | New directions in cryptography[END_REF], public-key encryption (also known as asymmetric encryption), and digital signatures in 1978 [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF], the scope of cryptology broadened considerably. In public-key cryptography, each party has a pair of keys: a public one and a private (or secret) one. The public one can be published, e.g., on the Internet, and allows anyone to encrypt a message, that can only be decrypted with the corresponding private key. In order to explain this concept, a famous analogy is often used: the public key corresponds to an open lock, whereas the private key corresponds to the lock's key. Publishing the public key is equivalent to making the open lock available; then anyone can write a message, put it in a box, and close the box with the provided lock. The sealed box is then sent to the recipient, who can open it with the appropriate key. Interestingly, since it uses lattice cryptography, homomorphic encryption is resistant to quantum computing algorithm hacks and appears as a viable solution for secure data processing on the cloud. However, the main obstacle that researchers faced for more than 30 years was the growth of the noise: after many computations, the noise level will become too large and it will be impossible to proceed without losing correctness.

Bootstrap revolution. The turning point came in 2009 with the breakthrough by Craig Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] who put forward the first plausible construction for an FHE (Fully Homomorphic Encryption) scheme based on the hardness of some lattice problems. This breakthrough had the effect of reigniting FHE as a topic of research, and since then many important results followed. Although the techniques improved greatly, and the schemes became simpler and more efficient, the original blueprint presented in Gentry's thesis continues to underlie all known FHE constructions.

The key idea that was proposed in Gentry's work is that of bootstrapping. By this term, we denote the process of refreshing a ciphertext in order to produce a new ciphertext that encrypts the same message, but with a lower level of noise so that more homomorphic operations can be evaluated on it. This operation is at the very core of any FHE schemes known to date, and consists of homomorphically evaluating the decryption circuit of the scheme. Roughly speaking, it is like decrypting the ciphertext with the secret key, and then re-encrypting the message, with the difference that the secret key is not known and it is replaced by an encryption of the secret key, called the bootstrapping key. This requires an additional hardness assumption, called circular security assumption, meaning that we must assume it is safe to publish an encryption of the secret key under itself. Although this assumption is still not well studied and understood, and it is sometimes regarded with suspicion, no attacks that exploit this extra piece of information have been proposed.

Outline. Section 2 introduces the mathematical background then homomorphic encryption is presented in Section 3. The well-known schemes LWE and RLWE are explained in Section 4 and the whole boostrap procedure is detailed in Section 5. Finally, Section 6 concludes the report with discussions for further research.

Preliminaries

Notations. Let n be a power of two. We denote the 2n-th cyclotomic ring by R := Z[X]/ (X n + 1) and its quotient ring by R Q := R/QR. Ring elements in R are indicated in bold, e.g. a = a(X). For two vectors ⃗ a and ⃗ b, we denote their inner product by ⟨⃗ a, ⃗ b⟩. We write the floor, ceiling and round functions as ⌊•⌋, ⌈•⌉ and ⌊•⌉, respectively. For q ∈ Z and q > 1, we identify the ring Z q with [-q/2, q/2) as the representative interval, and for x ∈ Z we denote the centered remainder of x modulo q by [x] q ∈ Z q . We extend these notations to elements of R by applying them coefficient-wise. We use a ← S to denote uniform sampling from the set S. We denote sampling according to a distribution χ by a ← χ.

Probabilities. Given a probability distribution D, we use x ← D to denote that x is sampled from D. For a set S, x ← S denotes that x is sampled uniformly from S. A distribution χ over the integers is called B-bounded if it is supported on [-B, B].

Definition 1 (Discrete Gaussian) The discrete Gaussian distribution D Z,σ over the integers is the probability distribution that assigns a probability proportional to exp -π|x| 2 /σ 2 to each x ∈ Z.

The discrete Gaussian distribution D Z,σ is then used to define a distribution χ on R. The distribution χ is in general not as simple as just sampling the coefficients according to D Z,σ . However, for the polynomial f (x) = x d + 1 with d a power of 2 , we can indeed define χ as D d Z,σ . For more general cyclotomic polynomials, sampling from χ is only slightly more involved. Recall that for the normal distribution N 0, σ 2 , we have that

Prob x←N (0,σ 2 ) [|x| > k •σ] = erf(k/ √ 2). As such define the function β(ϵ) := min{β | erf(β/ √
2) < ϵ}, then with probability 1 -ϵ the samples are bounded by β • σ.

Homomorphic Encryption (HE)

Homomorphic encryption is a form of encryption with an additional evaluation capability for computing over encrypted data without access to the secret key. The result of such a computation remains encrypted. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought of as homomorphisms between the plaintext space P = ({plaintext}, +, ×) and the ciphertext space C = ({ciphertext}, ⊕, ⊗). For any encryption φ : P → C , the homomorphic property is described as follows.

Definition 2 (Homomorphic encryption) Let φ : P → C be any encryption scheme. φ is called homomorphic encryption (HE) if it preserves addition or multiplication of two messages, i.e., φ(m

1 + m 2 ) = φ(m 1 ) ⊕ φ(m 2 ) or φ(m 1 × m 2 ) = φ(m 1 ) ⊗ φ(m 2 ).
Moreove, φ is called fully homomorphic encryption (FHE) if it preserves both addition and multiplication.

Injecting errors. Among all the possible algorithms for homomorphic encryption, those that have become popular over the last ten years are all based on the so-called Learning With Errors (LWE) problem, for performance and security reasons. In these schemes, an error term is injected during the encryption procedure for security purposes. The reason is that these encryption schemes rely on the hardness of solving "noisy" problems, i.e., problems where the relations are not exact, but are perturbed by a moderate quantity of error. Combining multiple ciphertexts through homomorphic operations has the side effect of combining the noises as well, thus increasing the magnitude of the error in the resulting encryption. When the error grows beyond a certain threshold, correctness is lost, meaning that the decryption procedure will not return the expected result. We say that an encryption scheme is somewhat homomorphic if it can evaluate a certain number of homomorphic operations, before the error grows too much to maintain the correctness of the evaluation.

Parameters trade-off. When practically instantiating an encryption scheme, one of the most delicate steps is that of choosing parameters. This usually requires finding a sensible trade-off between security and efficiency, and remains one of the potentially weak points for theoretically secure schemes. This is also the case for homomorphic encryption schemes, but in this case the problem of finding parameters is even more important. In fact, parameters like the size of the modulus or the standard deviation of noise terms define the threshold below which the noise must remain in order to guarantee a correct decryption.

Learning With Errors (LWE) and Ring Learning With Errors (RLWE)

The learning with errors (LWE) problem was introduced in Regev ( 2009), and has become one of the most known problems in lattice-based cryptography. It has been used to construct several cryptosystems, and it is believed to be hard even for quantum computers. Learning with errors (LWE) is a conjecturally hard problem in lattice-based cryptography. Its hardness allows the construction of public key encryption/decryption schemes.

LWE Encryption

LWE encryption is the encryption based on LWE problem. This encryption scheme is parameterized by two positive integers, n and q, and an error distribution χ over Z, usually a discrete Gaussian of width αq, 0 < α < 1.

Definition 3 (LWE distribution) Given a secret vector s ∈ Z n q , the LWE distribution LW E s,χ over Z n q × Z q is sampled by picking ⃗ a ← Z n q , an error e ← χ, and returning (⃗ a, b = ⟨⃗ s, ⃗ a⟩ + e).

In other words, for n, q, t ∈ N * with t|q and a message m ∈ Z t ⊂ Z q , the LWE encryption with the key ⃗ s ← χ key (Z n q ) of m is defined as:

LWE q,⃗ s (m) := (⃗ a, b) = (⃗ a, ⟨⃗ a, ⃗ s⟩ + m + e) ∈ Z n+1 q
where ⃗ a ← Z n q , error e ← χ error (Z q ) and m = q t m. The decryption of a ciphertext

(⃗ a, b) of m is LWE -1 ⃗ s (⃗ a, b) := ⌈ t q (b -⟨⃗ a, ⃗ s⟩)⌋ ∈ Z q . Let Err LWE ((⃗ a, b), m) = t q (b -⟨a, s⟩) -m = t q e. If | t q e| ∈ [0, 1/2] then LWE -1 (⃗ a, b) = m,
thus the decryption is successful. Here we observe the interest of keeping the function Err LWEs small in order to decrypt successfully. For this case, we set t << q and χ error as small noise distribution. Note that the addition of LWE ciphertexts is straightforward and is given by

LWE q,⃗ s (m 1 ) + LWE q,⃗ s (m 2 ) = (⃗ a 1 , b 1 ) + (⃗ a 2 , b 2 ) = (⃗ a 1 + ⃗ a 2 , b 1 + b 2 ) = (⃗ a 1 + ⃗ a 2 , ⟨⃗ a 1 + ⃗ a 2 , s⟩ + ( m1 + m2 ) + (e 1 + e 2 )) = LW E q,⃗ s (m 1 + m 2 ).
LWE encryption is then additively homomorphic with an accumulated noise. Such noise needs to be reduced in order to ensure a succesful decryption. This is the aim of the bootstrap procedure that we describe in Section 5.

Ring-LWE Encryption

RLWE encryption was introduced in [START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF]; [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] and is the encryption based on LWE problem on a well chosen polynomial quotient ring. Similarly to LWE, the encryption distribution of RLWE is given by the following definition.

Definition 4 (Ring-LWE distribution) Let R be a polynomial ring such that R = Z[X]/f (X), with f some cyclotomic polynomial of degree n. Also, let q ≥ 2 be an integer modulus, and let R q = R/qR be the quotient ring. Finally, let χ be an error distribution over R. For a fixed secret s ∈ R q , the ring-LW E distribution ring-lwe s,χ is sampled by taking a ← R q , e ← χ, and outputting (a, b = s • a + e). All the computations are, as usual, done modulo q.

In other words, for n, Q, t ∈ N * with t|q and a message m(X) ∈ R Q , the RLWE encryption with the key z(X)

← χ key (R Q ) of m ∈ R t is defined as: RLWE Q,z (m) := (a, b) = (a, a • z + m + e) ∈ R 2 Q where a ← R Q , error e ← χ error (R Q ) and m = Q t m.
Again, note that from the definition, RLWE encryption is linearly homomorphic. The advantage of using ring-LWE instead of plain LWE is compactness and efficiency. In fact, in the case of ring-LWE, each sample gives a n-dimensional pseudorandom ring element b ∈ R, instead of just a pseudorandom scalar b ∈ Z q . We can thus say that a single ring-LWE sample with a ∈ R takes the place of n LWE samples with vectors a i ∈ Z n q . Moreover, thanks to techniques like the Fast Fourier Transform (FFT) [START_REF] Brigham | The fast Fourier transform and its applications[END_REF], the multiplication between ring elements can be performed in quasi-linear time.

External Product for RLWE. Since the RLWE encryption scheme is homomorphic for the addition, we are now interested in the multiplication operation. For that matter, we rely on another encryption scheme with allows to define an external product on RLWE. Consider the following ecryption scheme

RLWE ′ z (m) = RLWE z (m, RLWE z (Bm), • • • , RLWE z (B k-1 m))
using the same keys z ∈ R q , and where ciphertexts consist of k = log B q basic encryptions produced by the original RLWE scheme. The base B can be set differently to achieve various time/space trade-offs. For simplicity, we assume q is a power of B, but the scheme can be easily adapted to other values. Mixed base variants are also possible, where B i is replaced by a product B 1 • • • B i . Incidentally, we note that these ciphertexts allow to recover the message m exactly, even without encoding/scaling, by first decrypting RLWE B k-1 m to recover (m mod B). Then subtracting B k-2 • (m mod B) from RLWE s B k-2 m to recover m mod B 2 , and so on. We then define

RGSW z (m) = (RLWE ′ z (-z • m), RLWE ′ z (m))
Interstingly, note how RGSW z (m) ciphertexts can be equivalently written as

RGSW z (m) = (RLWE z (0), . . . , RLWE z (0)) + mG where G = I 2 ⊗ 1, B, B 2 , . . . , B k-1 ⊤ ∈ R 2k×2 Q
is the powers-of-B "gadget matrix". Such formula may be derived from [START_REF] Ducas | Fhew: Bootstrapping homomorphic encryption in less than a second[END_REF]. For the notations, note that each ciphertext of 0 may be written as RLWE z (0) = (a i , b i ) and we have k such encryptions in the formula above which are stacked to obtain an element of R 2k×2 Q . We finally obtain the multiplication operation in RLWE thanks to the following external product ⋄ : RLWE × RGSW -→ RLWE Such multiplication allows to define the product on ciphertexts as follows.

Lemma 5 For two messages m 0 , m 1 ∈ R Q with m 1 small we have:

RLWE z (m 0 ) ⋄ RGSW z (m 1 ) = RLWE z (m 0 • m 1 )

Bootstrap procedure

Bootstrap is a noise reduction technique for LWE encryption. The general idea is to transform the LWE encryption into an RLWE encryption in which the noise of the former is removed and the noise of latter is reduced thanks to RLWE's rich settings. Once a small-noised RLWE encryption with is obtained, we can extract from it a small-noised LWE encryption. We implemented the bootstrap procedure as well as all necessary tool functions to work in ring polynomials. The code is written in Python and is available upon request. From a practical point of view, the bootstrap procedure may be expressed as follows: it takes as input a ciphertext LW E s (m) = (⃗ a, b) with error e then apply the three steps:

• Step 1: Blind rotation (⃗ a, b) = LW E s (m) - → (a z (X), b z (X)) = RLW E z(X) (X -b+⟨⃗ a,⃗ s⟩ • w(X))
•

Step 2: Key switching

(a z (X), b z (X)) - → (a s (X), b s (X)) = RLW E s(X) (X -b+⟨⃗ a,⃗ s⟩ • w(X)) • Step 3: Extraction (a s (X), b s (X)) - → (⃗ a, b) = LW E s (m)
and the final output is a ciphertext LW E s (m) = (⃗ a, b) with small error e ′ < e. This full procedure is summarized in Figure 1 below where the right part concerns the "bootstrap world" where operations are performed on ring polynomials.

Bootstrap Bootstrap scheme. For a good choice of w(X) ∈ R Q we compute the RLWE z(X) encryption of the blind rotation X -b+⟨⃗ a,⃗ s⟩ • w(X). Here w(X) can be considered as a window filter and X -b+⟨⃗ a,⃗ s⟩ makes it slice to the RLWE plaintext that corresponds to the LWE ciphertext of m, thus killing the LWE error e. It rests now RLWE noise due to multiplication ⋄. We then switch the key z(X) to s(X) in the RLWE encryption which produces again noise due to scalar multiplication in RLWE. These two noises are however controllable, which means they can be made small by choosing z and computation techniques (AP, GINX) . Finally the extraction of the last RLWE ciphertext encrypted by s(X) returns a LWE ciphertext of m with noise e ′ < e.

(LWE ⃗ s (m), e) = ((⃗ a, b), e) RLWE z(X) (X -b+⟨⃗ a,⃗ s⟩ • w(X)) (LWE ⃗ s (m), e ′ ) = (( ⃗ a ′ , b ′ ), e ′ ) RLWE s(X) (X -b+⟨⃗ a,⃗ s⟩ • w(X)) e ′ < e

Blind Rotation

The main trick behind the bootstrap procedure is to work with ring polynomials. Indeed, for a polynomial w(X) = N -1 i=0 w i X i and any u ∈ Z q , we have coeff 0 (X -u w(X)) = coeff u (w(X)) = w u . Recall that for any LWE ciphertext, we have b -⟨⃗ a, ⃗ s⟩ = m + e so that with u = b -⟨⃗ a, ⃗ s⟩, coeff 0 (X -(b-⟨⃗ a,⃗ s⟩) w(X)) = w m+e = w m. Thus, as soon as w(X) is well-chosen with coefficients that are equal by parts on subsets, one may recover a ciphertext of m with smaller noise.

Product and Decomposition. Blind rotation is an operation that multiplies a given ring element f ∈ R Q by a monomial X v , where the exponent v = -b + ⟨⃗ a, ⃗ s⟩ is given by an LWE ciphertext (⃗ a, b) ∈ Z n+1 q of a message m ∈ Z q encrypted under a secret key ⃗ s ∈ Z n q . The output of the blind rotation is an RLWE encryption of f • X v under a secret key z ∈ R Q . The operation is called blind rotation because it rotates the coefficients of f negacyclically (i.e with the sign negative). Consider the decomposition

X -b+⟨a,s⟩ • f = n i=1 X a i •s i • X -b • f. Let ACC 0 be trivial encryption RLWE z (X -b • f ) = (0, Y -b • f ).
Using the property of RLWE ⋄ RGSW, we may recursively apply the external product to obtain

RLWE z X -b+⟨a,s⟩ • f = RGSW z n i=1 X a i •s i • ACC 0 = n i=1 RGSW z (X a i •s i ) • ACC 0 .
Two different blind rotation algorithms were proposed in [START_REF] Ducas | Fhew: Bootstrapping homomorphic encryption in less than a second[END_REF]; [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]. Many authors refer to the two algorithms as AP blind rotation and GINX blind rotation respectively. Both methods rely on the properties of RGSW ciphertext described above. This is where different techniques are employed to encode the elements in the product of the above formula: the AP algorithm relies on the decomposition of the elements a i is basis B whereas the GINX algorithm takes advantage of the structure of binary secret keys.

AP blind rotation. For each i = 1, • • • , n, decompose a i in a basis B ≥ 2 as a i = K j=0 a i,j B i where K := log B q -1 and 0 ≤ a i,j ≤ B -1. The decomposition may be rewritten as

RLWE z X -b+⟨a,s⟩ • f = n i=1 K j=0 RGSW z (X a i,j •B i •s i ) • ACC 0 .
The blind rotation key is the public Bootstrap Key (BK) given by BK AP i,j,v := RGSW z (X v•B j •s i ). In practice, one needs to store these bootstrap keys. The procedure of AP blind rotation is described in Algorithm 1.

Algorithm 1 AP Blind Rotation Require: f, (a, b), BK AP i,j,v = RGSW z (X v•B j •s i ). 1. Set ACC = (0, Y -b • f ) 2. for 1 ≤ i ≤ n: 3.
for 0 ≤ j ≤ K:

4.
for 0 ≤ v < B:

5. ACC ← ACC ⋄ BK AP i,j,v
6. Return ACC GINX Blind Rotation. This blind rotation is known to be more efficient than AP when the secret key s ∈ Z q is set to a binary or ternary vector, however its performance degrades when using larger secret keys. For each secret key element s i ∈ Z q for i ∈ {1, • • • , n}, we decompose the key as s i = |U | j=1 u j • s i,j where s i,j ∈ {0, 1} and U ⊂ Z q is an appropriately chosen subset of Z q . For simplicity, we consider the case that s

i ∈ {0, 1}. Then for all i ∈ {1, • • • , n}, we have that X a i •s i = 1 + (X a i -1)s i which implies that RLWE z X -b+⟨a,s⟩ • f = RGSW z n i=1 (1 + (X a i -1) • s i ) • ACC 0
Using this technique, the blind rotation key is BK GINX i = RGSW z (s i ). The procedure of GINX blind rotation is described in Algorithm 2.

Algorithm 2 GINX Blind Rotation

Require: f, (a, b), BK GINX i = RGSW z (s i ). 1. Set ACC = (0, Y -b • f ) 2. for 1 ≤ i ≤ n: 3. ACC = ACC + (X a i -1) • (ACC ⋄ BK GINX i ) 4. Return ACC
Observe that in line (3), if s i = 0, the second addendum is ignored since it gives an encryption of 0 and the value stored by the accumulator stays the same. If s i = 1, then ACC ⋄ RGSW z (1) is equal to ACC and the accumulator is updated to X a i • ACC.

Key Switching in RLWE

Key switching operation converts a ciphertext RLWE

z 1 (m) of a message m ∈ R Q encrypted by a secret key z 1 ∈ R Q to a ciphertext RLWE z 2 (m) encrypted by a new secret key z 2 ∈ R Q .
There are different variants of the key switching technique (e.g see for details). We describe the following method. Let (a, b) be an RLWE encryption of m by the secret key z 1 . To offer a space/time trade-off, we write a in a basis B ≥ 2 as follows:

a = K j=0 α j B j with α j (X) = N -1 i=0 a i,j X i , 0 ≤ a i,j ≤ B -1 and K := log B Q -1
The KeySwitching (KS) keys are given for all j = 0,

• • • , K by RLWE z 2 (B j •z 1 ) := (KS a j , KS b j ). Now rewrite the ciphertext m = b -a • z 1 -e as m = b - K j=0 α j • KS b j + K j=0 α j • KS a j • z 2 -( K j=0 α j • e j + e)
where e is the error in the RLWE encryption of m under the key z 1 and e j those in the RLWE z 2 (B j • z 1 ). The procedure of key switching is described in Algorithm 3. Note that (KS a j , KS b j ), for j = 0, • • • , K, is a public switching key. We see explicitly that the key switching error is equal to the sum of the error of RLWE z 1 (m) and all RLWE z 2 (B j • z 1 ) which calls for caution when choosing the various parameters for encryption. where ι i (a) is the ith anti-cyclic permutation of coefficients of a. Since e(X) is small, so is e i and (ι i (a), b i ) is a LW E s encryption of m. Therefore, the extraction operation of the bootstrap procedure only requires to compute the anti-cyclic permutation of coefficients of a.

Conclusion

If introduced on a large scale and in real-world scenarios, fully homomorphic encryption (FHE) would have enormous consequences for people's privacy, allowing them to use remote services hosted on untrusted servers, without disclosing personal informations. Over the years, homomorphic encryption has been a very active field for research, and this has led to a long list of works and improvements, e.g. Brakerski and Vaikuntanathan (2014b,a); [START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF]. This comprised both theoretical works that put forth new ideas and constructions, and implementation works [START_REF] Wang | Accelerating fully homomorphic encryption using gpu[END_REF][START_REF] Jung | Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus[END_REF] that optimized existing constructions with the goal of achieving the best possible efficiency.

Figure 1 :

 1 Figure 1: Representation of the bootstrap Procedure

Algorithm 3

 3 Key Switching in RLWE Require: (a, b) = RLWE z 1 (m), z 2 , (KS a j , KS b j ) := RLWE z 2 (B j • z 1 ) 1. Write a = K j=0 α j B j where α j = N -1 i=0 a i,j X i such that |a i,j | ≤ B -1 2. Return (a ′ , b ′ ) = -K j=1 α j • KS a j , b -K j=1 α j • KS b j5.3 ExtractionThe final step of the boostrap procedure deals with the extraction of a ciphertext of the coefficient of order 0 of a ciphertext in RLWE. To define such operation, consider a ciphertext RLW E s(X) (m(X)) = (a(X), b(X)) ∈ R Q . We have: b(X) = a(X) • s(X) + m(X) + e(X) so the coefficients of the polynomials may be identified asb i = N -1k=0a i-k s k + mi + e i = ⟨ι i (a), s⟩ + mi + e i

Acknowledgements This work was done during the SEME (Semaine d'Étude Mathématiques Entreprise) in Rennes (May 2nd -May 6th 2022) organized in collaboration with AMIES (Agence pour les Mathématiques en Interaction avec les Entreprises et la Société). The authors would like to thank the organizers of Université of Rennes 1 as well as the different supervisors from Ravel Technologies: Florian Méhats, Mohammed Lemou and Philippe Chartier.


Benoît Faure
email: benoit.faure@mines-ales.org

Nathan Odic
email: nathan.odic@mines-ales.org

Olfa Haggui
email: olfa.haggui@lirmm.fr

Baptiste Magnier
email: baptiste.magnier@mines-ales.fr

Performance of Recent tiny/small YOLO Versions in the Context of Top-view Fisheye Images

Keywords: Human detection, YOLOv3, v4, v5, Fisheye camera

With the spreading of the computer vision field, human detection and tracking are problems more relevant than ever. However, due to the complexity of fisheye images, current lightweight detection models show difficulty when processing them. The aim of this article is to compare the performance on fisheye images of current real time detection solutions, specifically YOLOv3-tiny, YOLOv4-tiny and YOLOv5-small. Experiments carried out using a top-view fisheye camera, show faster performance but the very poor detection quality from YOLOv4-tiny. YOLOv5-small, while being slightly slower, gives a far better detection than both other solutions. The database created for this paper is available online. In conclusion, the current review shows YOLOv5-small is the best solution out of the 3 reviewed in a fast, real time, fisheye application.

Introduction and Motivations

Human detection is a challenging task owing to their variable appearance and wide range of poses [START_REF] Dollar | Pedestrian detection: An evaluation of the state of the art[END_REF], especially with fisheye camera. Indeed, a fisheye lens enables images to be acquired with a broad field of view [START_REF] Scaramuzza | Omnidirectional camera[END_REF][START_REF] Hansen | Wide-angle visual feature matching for outdoor localization[END_REF][START_REF] Kumler | Current developments in lens design and optical systems engineering[END_REF]. However, pedestrians appear in different shapes, sizes and at various orientations. Unfortunately, most of the existing people-detection algorithms are designed for standard/perspective camera images where people appear upright. On the one hand, people-detection algorithms using classical feature extraction have been adapted to fisheye images [START_REF] Chiang | Human detection in fish-eye images using HOG-based detectors over rotated windows[END_REF][START_REF] Wang | Template-based people detection using a single downward-viewing fisheye camera[END_REF][START_REF] Demirkus | People Detection in Fish-eye Top-views[END_REF]. On the other hand, the detection performances are improved with the great success of deep learning. For instance, the YOLO (You Only Look Once [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF]) is a reliable detector based on Deep Convolutional Neural Network and remains commonly used for real-time object detection. Recently, different algorithms based on YOLO provide much faster and more accurate results than previous algorithms aimed at detecting people in fisheye images without any pre-processing [START_REF] Duan | RAPiD: rotation-aware people detection in overhead fisheye images[END_REF][START_REF] Haggui | Human Detection in Moving Fisheye Camera using an Improved YOLOv3 Framework[END_REF]. Meanwhile, different YOLO versions exist, the last are: YOLOv3 [START_REF] Redmon | Yolov3: An incremental improvement[END_REF], YOLOv4 [START_REF] Shaniya | YOLOv4 RGBT Human Detection on Unmanned Aerial Vehicle Perspective[END_REF], and YOLOv5 [START_REF] Iyer | Comparison of YOLOv3, YOLOv5s and MobileNet-SSD V2 for Real-Time Mask Detection[END_REF]. The small/tiny implementations of these versions are optimum regarding limited hardware resources. The aim of this article is to compare the person's detection performance of these versions on fisheye images. After discussing the differences between each algorithm, each YOLO version is trained on fisheye images, using fisheye datasets.

Detection Method

In this communication, human detection methods in top down fisheye cameras are evaluated. The detection model used in this paper is the state of the art method YOLO, the different versions of it we compared are shown in Fig. 1.

YOLO: an Architecture for human detection

This section details the developments of the YOLO architecture based on Deep Convolutional Neural Network detection model and its extensions: YOLOv3tiny, YOLOv4-tiny and YOLOv5-small architectures. Originally, YOLO is a state of art Object Detector which can perform object detection in real-time with a good accuracy [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF]. It treats the detection task as a regression downside and has been wide utilized in image process fields. There are various deep learning algorithms, but they are unable detecting an object in a single run. Meanwhile, YOLO makes the detection in a single forward propagation through a neural network, which makes it suitable for real-time applications. This property has made YOLO very popular amongst the other deep learning algorithms. Recently, several versions, e.g., YOLOv3 [START_REF] Redmon | Yolov3: An incremental improvement[END_REF], also YOLOv4 [START_REF] Shaniya | YOLOv4 RGBT Human Detection on Unmanned Aerial Vehicle Perspective[END_REF], and lastly YOLOv5 [START_REF] Iyer | Comparison of YOLOv3, YOLOv5s and MobileNet-SSD V2 for Real-Time Mask Detection[END_REF], have additionally been developed to improve the classification performance on complicated datasets, and, to increase the quantity of data within the feature map. Usually, in the architecture of the YOLO algorithm, the head and neural network type are the same for all of the algorithms, whereas backbone, neck, and loss function are different, as detailed below.

YOLOv3-tiny: In order to benefit computers having limited hardware resources, YOLOv3-tiny algorithm (denoted YOLOv3-t) is the preferable version of YOLOv3. Indeed, it is easy for YOLOv3-t [START_REF] He | TF-YOLO: An Improved Incremental Network for Real-Time Object Detection[END_REF][21] network to satisfy real-time requirements on a standard computer with a limited Graphics Processing Unit (GPU). In fact, YOLOv3-t is the simplified and light version of the original YOLOv3 [START_REF] Redmon | Yolov3: An incremental improvement[END_REF]. It operates with the same operating principle as original model, but with a varied number of parameters in which the depth of convolutional layer is reduced. Originally, YOLOv3 [START_REF] Redmon | Yolov3: An incremental improvement[END_REF] utilizes the architecture of darknet53, and then uses many 1×1 and 3×3 convolution kernels to extract features. The Dark-net19 structure of the YOLOv3-t network, within structure contains only seven convolutional layers and small number of 1×1 and 3×3 convolutional layers is used as feature extractor to achieve the desired effect in miniaturized devices. Eventually, to reduce the dimensionality size through the network: pooling layer is applied. However, its convolutional layer structure still uses the same structure of 2D-Convolution, Batch Normalization and an activation function LeakyRelu (Leaky Rectified Linear Unit) as the YOLOv3 algorithm. This network simplification requires this model to occupy less amount of memory and, consequently, will improve the speed of the detection process.

YOLOv4-tiny: As a modified version of YOLOv3, YOLOv4 [START_REF] Shaniya | YOLOv4 RGBT Human Detection on Unmanned Aerial Vehicle Perspective[END_REF] is used in this work with a derived version. Thus, YOLOv4-tiny (denoted YOLOv4-t) uses Cross Stage Partial Network (CSPNet) in Darknet, creating a new feature extractor backbone called CSPDarknet53. However, to help it achieve these fast speeds, YOLOv4-t [START_REF] Jiang | Real-time object detection method based on improved YOLOv4-tiny[END_REF] utilizes a couple of different changes from the original YOLOv4 network. Foremost, the number of convolutional layers in the CSP backbone are compressed with a total of 29 pre-trained convolutional layers.

Additionally, the number of YOLO layers has been reduced to two instead of three and there are fewer anchor boxes for prediction. We can use YOLOv4-t for a faster training and a faster detection. Therefore, the neck is composed of a Spatial Pyramid Pooling (SPP) layer and PANet path aggregation. They are used for feature aggregation to improve the receptive field and short out important features from the backbone. In addition, the head is composed of YOLO layer. Fundamentally, the image is fed to CSPDarknet for feature extraction and then to path aggregation network PANet for fusion. At last, YOLOv4-t is the better option when compared with YOLOv4 as faster inference time is more important when working with a real-time object detection environment.

YOLOv5-small: In this context, YOLOv5 is different from the previous releases. The v5 model has shown a substantial performance increase from its predecessors. In addition, YOLOv5 [START_REF] Iyer | Comparison of YOLOv3, YOLOv5s and MobileNet-SSD V2 for Real-Time Mask Detection[END_REF] comes with its various versions: YOLOv5-s, the small version, YOLOv5-m, the medium version, YOLOv5-l, the large version and YOLOv5-x, the extra-large version, each having its own unique characteristic. Since this study focuses on real-time detection, the speed is a factor of the utmost importance, hence the smallest version has been chosen as the representative of the YOLOv5 family for its performance analysis. The backbone is CSPDarknet53 and solves the repetitive gradient information in large backbones and integrates gradient change into feature map; that reduces the inference speed, increases accuracy, and reduces the model size by decreasing the parameters. Furthermore, it uses a path aggregation network (PANet) as neck to boost the information flow. PANet adopts a new feature pyramid network (FPN) that includes several bottom ups and top down layers. Consequently, this improves the propagation of low-level features in the model. The PANet improves the localization in lower layers, which enhances the localization accuracy of the object.

In addition, the head in YOLOv5 is the same as YOLOv4 and YOLOv3, generating three different outputs of feature maps to achieve multi-scale prediction. Finally, it helps to enhance the prediction of small to large objects efficiently.

Dataset

Images in these datasets were resized to 640×640 pixels because YOLO requires square images whose height and width are multiples of 32. The image size of 640×640 was chosen based on preliminary tests with YOLOv5-s.

Public Datasets: Primarily, as a base for the algorithm, weights trained on the COCO dataset [START_REF] Lin | Microsoft COCO: Common Objects in COntext[END_REF] were used. This dataset provides numerous images containing human examples. Even though the images presented are not fisheye and not necessarily top view, they gave a big data baseline for our model. The objective being, to start fisheye training with weights already able to recognize the general features of a human figure. A few benchmarks and datasets have been created in order to train and evaluate people detection algorithms for fisheye images. Such datasets are used to specialize our model on fisheye cameras. Fisheye images pose challenges not encountered in images taken with a standard lens. These include illumination variations across the image and big variations in the angle at which a person appears. Additionally, fisheye images distort figures in it. The distortion is much more prominent on the edge of the images, with big objects being affected the most. The distortion causes shrinking of the objects, this makes it harder for the YOLO algorithm to discern it. The chosen dataset for specialization is the MIRROR Worlds dataset 3 . However, preliminary tests on these datasets gave poor detection results. That is because annotations of this dataset are imprecise, as shown in Fig. 2. These Our Dataset: The images for the new dataset were collected in the CERIS laboratory of the IMT mines Alès. Videos were acquired with a fisheye camera (Basler ace acA2040-120uc) mounted on a pole and placed around 3m in height. Initially, images were pulled from videos from both inside and outside the laboratory's hangar. During each capture, the camera was static, 2-3 people moved around the camera taking different positions. Examples include sitting, lying down and crouching. Furthermore, the brightness level of the images is very low inside the hangar, outside, however the images are very clear. The split for this dataset is 80% train and 20% test; it is available online with tied annotations 5 .

A second part of the dataset was made, the objective of which being to test the effectiveness of each algorithm (see Sec. 2.1) on images set in environments they were not familiar with. For this part of the dataset, images were pulled from videos taken outdoors and on the street outside. Consequently, these images are different from the one detailed previously. So far, 406 images were annotated, and between 0 and 3 discernible people appear in each image. Finally, the Tab. 1 represents the characteristics of the datasets we used with 406 annotated images of the different scene than others utilized only for the tests. Data Annotation: Data labelling is an essential step in a supervised machine learning task requiring significant manual work. To annotate our new dataset, boxes containing people are manually annotated. In order to do so, the Robof low Tool is used. From a technical aspect, the pixel representing the center of the BBox, as well as its height and width in pixels are defined. Consequently, each BBox is represented by five parameters:

-(x, y): pixel coordinates of the BBox center, w and h: width and height of the BBox respectively, class: ID of the object category.

The parameters x, y, w and h are essential for the evaluation presented in the next section, whereas the ID concerns mainly tracking processes.

Experiments and Evaluations

Evaluation Metrics

To analyze the progress of the network, we utilize the five following metrics: mean average precision 0.5 and 0.5:0.95, precision, recall and CIoU.

Mean Average Precision After running the network on a certain number of images, of which the real BBox sizes and positions are known (i.e., called ground truth), the IoU (Intersection over Union) is computed between each detected BBox and all real BBoxes, the corresponding box with the highest IoU can be considered as the detected BBox: IoU = Intersection area of both boxes U nion area of both boxes . A threshold α is then set to compute the mean average precision mAP α : mAPα = N umber of detections where the coressponding IoU ≥ α N umber of detections f rom the neural network

Moreover, it is possible to take the average of different values of α, to show the progress of the network over a range of metrics simultaneously. With this idea we declare mAP 0.5:0.95 :

Precision: When a detected BBox obtains an IoU above 0, it is counted as a positive. However, the box of the detected object could be very inaccurate, for example by bounding only the top half, or by actually covering twice or thrice the area of the real box. To counter this problem, we set a threshold at 0.5, above which a detection is counted as a true positive, and below which, it is counted as a false positive: precision = total amount of true positives number of true positives + number of f alse positives .

Recall: It represents the percentage of detections, which were not missed, a real BBox which was not detected represents a false negative and define the recall: recall = total amount of true positives total amount of (true positives + f alse negatives) .

CIoU: Complete IoU bounding boss regression [START_REF] Zheng | Distance-IoU Loss: Faster and better learning for bounding box regression[END_REF] allows for fast convergence towards the ground truth BBox. It is used in the training of YOLOv3-t, YOLOv4-t and YOLOv5-s. The metric combines the overlap between predicted and ground truth, as well as the center of the BBoxes and their aspect ratio.

Training of the models

To train the different YOLO networks, we used the respective P yT orch implementations of each architecture. The definition for the architecture of YOLOv4t was obtained from a github repository in [START_REF]Yolov4-tiny[END_REF], which based it on Ultralytics' yolov5 implementation. Finally, the definition for YOLOv3-t [24], YOLOv5-s [23] and the methods for training [25] the networks were obtained from the Ultralytics github repository, the company that developed the YOLOv5 architecture.

As mentioned in the Sec. 2.2, the training started using weights pre-trained on the COCO dataset [START_REF] Lin | Microsoft COCO: Common Objects in COntext[END_REF]. Each YOLO version is then specialized on fisheye cameras, using first the MIRROR dataset (own annotated) before moving training onto our own dataset. We chose to train on the datasets in this order, as the context in which the network will be applied is expected to be closer to the environment we obtained images from. The settings for the training of each YOLO version are detailed in the Tab. 2.

The batch size was maximized while considering the GPU's memory limitations could hold, this was done as to follow indications from Ultralytics on training the model. The image size was set to correspond to the size of COCO images and hyper-parameters were set to their default values. To quantify how close we are to overfitting the model, we observed the rate at which the CIoU increased. In an attempt to limit the risk of overfitting, epochs for both datasets were chosen as to stop training before this rate became negligible. The Fig. 3 represents the evolution of the CIoU during training on the MIRROR dataset (a) and our dataset (b). The graphs start very close to each other in (a) as they were all trained on the COCO dataset, however YOLOv5-s shows better performance in learning especially at the start of training where it begins converging much faster. In Fig. 3(b), the graphs start separate, this is due to the better score YOLOv5-s had at the end of training on the MIRROR dataset. The combination of these two graphs demonstrates a better learning performance of the YOLOv5-s model.

Performance of the models on images in a familiar context

The Tab. 3 gives the final metrics of the training and testing on the MIRROR dataset, while the Tab. 4 gives the final metrics of the testing on our dataset of models trained on both our dataset and the MIRROR dataset. The results are similar across all 3 versions for Precision, Recall and mAP 0.5 , however YOLOv5-s has better results for mAP 0.5:0.95 . In terms of the detection quality, YOLOv5s performed best, with YOLOv3-t and YOLOv4-t as second and third place respectively. However, in detection speed the rankings are reversed, the increase in speed from YOLOv4-t comes from the small size of the neural network (weight file is 6.3Mo) relative to YOLOv3-t (17.4Mo) and YOLOv5-s (14.5Mo). To finish testing, all 3 models were used to detect people in the same dataset they were trained on. A sample of the data obtained is shown in Fig. 4. All 3 algorithms perform well in both a dark (a)-(b) and light (c)-(e) contexts. The algorithms were also able to detect and bound small entities as shown in column (e) of Fig. 4.

Performance of the models on images in an unfamiliar context

Results shown previously (Sec. 3.3) give a very optimistic view of the algorithms performance. However, the high similarity between the BBoxes provided by each model, as well as the very high performance in low light contexts possibly indicates a partial memorization of the dataset. To investigate this, all 3 trained YOLO versions were tested on the second part of our dataset. As the images and contexts differ greatly in comparison to images our models were trained on, it would give a better indication of the models performance.

The Tab. 5 summarizes the results obtained in the test, the rankings are consistent with the results obtained previously; however the distance between each model is much bigger. On all precision metrics, YOLOv5-s performs much better than the other two metrics. The mAP 0.5 of the model is at 0.739, meaning that the algorithm is capable of bounding it's detection relatively well. Furthermore, the model displays a high precision (0.82), indicating the low number of false positives in an unfamiliar context. Finally, the recall is at 0.656, it indicates that the model missed around 35% of detection; this figure is high, but in the context of a tracking algorithm could be negligible if compensated properly.

The Fig. 5 shows a sample of the images obtained from the tests. While these images have been selected, they represent quite well the obtained images. In that respect, YOLOv5-s outperforms the other networks, but still has its limitations, as shown by the metrics discussed previously. Column (e) shows two false negatives, one (center) is due to the black clothes on a dark background, and another (bottom left) appears when the person walks into the very edge of the image. This same person was detected a few frames before in the column (d). This column also shows a false negative (center) and a false positive (top left) also appearing at the edge of the frame where cars can be seen distorted. Nevertheless, looking at columns (a), (b) and (c) where the images are very clear, YOLOv5-s was able to properly detect all people present in the picture.

While it is true that YOLOv3-t and YOLOv4-t both have faster detection speeds than YOLOv5, the difference between each algorithm is about 5ms. The detection speeds of YOLOv5-small are fast enough to be used in real time cases (i.e., >10 fps), making detection speed a secondary factor in the comparison of each network. The difference is further dwarfed by the very high performance of YOLOv5-s on detection metrics in comparison to YOLOv3-t and YOLOv4-t. We expect YOLOv4-t's very poor performance to come from it's small size, because of it, it memorized the dataset rather than learn important features.

Conclusion

This paper presents a comparison in the performance of YOLOv3-tiny, YOLOv4tiny and YOLOv5-small when applied to a problem involving fisheye images.

During training, even though YOLOv5-s shows slightly better convergence, all 3 networks give similar detection scores. However, the same cannot be said about the networks' performance on datasets pulled from contexts they are unfamiliar with. In these cases, YOLOv5-s surpasses both YOLOv3-t and YOLOv4-t by a large margin, while giving itself acceptable detection performances. Moreover, while YOLOv5-s displays the slowest detection time, it is a small disadvantage as the detection speeds are still fast enough (25ms per frame) for real time applications. To further the argument in favor of YOLOv5-s, YOLOv4-t and YOLOv3-t have detection times of the same order of magnitude as YOLOv5-s, making the differences negligible in comparison to the differences in detection quality. Subsequently, YOLOv5-s is the best solution out of the 3 proposed for a real time, fisheye detection application. This solution was retained to act as the detection portion of a real time tracking algorithm [START_REF] Wojke | Simple online and realtime tracking with a deep association metric[END_REF][START_REF] Haggui | A Comparison of OpenCV Algorithms for Human Tracking with a Moving Perspective Camera[END_REF][START_REF] Talaoubrid | Human Tracking in Top-View Fisheye Images: Analysis of Familiar Similarity Measures via HOG and against Various Color Spaces[END_REF], applied to videos acquired from a top-view fisheye camera, and mounted on an aerial drone or for security cameras. As a reminder, the dataset is available online (see Sec.

Fig. 1 .

 1 Fig. 1. Flow diagram of different YOLO architectures studied in this communication.

3Fig. 2 .

 2 Fig. 2. Dataset MIRROR, originally not perfectly annotated.

Fig. 3 .

 3 Fig. 3. Evolution of CIoU during training of each YOLO model

Fig. 4 .

 4 Fig. 4. People detection on top-view fisheye images. The used algorithms for the detection are in the first row: YOLOv3-t, second row: YOLOv4-t and third row: YOLOv5-s. Images in (a)-(b) correspond to our new image dataset whereas in (c)-(e), they are tied to MIRROR dataset with new annotations.

  2.2).

Fig. 5 .

 5 Fig. 5. People detection on top-view fisheye images on a new dataset without training on the same data. The used algorithms for the detection are in the first row: YOLOv3-t, second row: YOLOv4-t and third row: YOLOv5-s.

Table 1 .

 1 Experimental characteristics of the used datasets. objects that ended up being detected as human by the detection algorithm. We thus decided to relabel the MIRROR dataset using robof low4 . Subsequently, 1025 annotated images were obtained; the split for this dataset is 80% training and 20% test. Additionally, we decided to create a new dataset to further increase the variations in environments and situations the algorithm could find itself in.

	Database	MIRROR (new annotations) Our dataset
	Number of videos	19	31
	Number of images for training	821	1492
	Number of images for test	204	377 + 406
	Moving camera	No	Yes
	annotations were at times not bounding anything, or bounding completely dif-
	ferent objects,

Table 3 .

 3 Performance of YOLOv3-t, YOLOv4-t and YOLOv5-s on the MIRROR dataset after being trained on it (computer equipped with GPU Tesla K80).

	Version Precision Recall mAP0.5 mAP0.5:0.95 Detection (ms)
	YOLOv3-t 0.964 0.922 0.976	0.617	19.8
	YOLOv4-t 0.947 0.952 0.975	0.587	14.7
	YOLOv5-s 0.953 0.974 0.989	0.736	25.3

Table 4 .

 4 Performance of YOLOv3-t, YOLOv4-t and YOLOv5-s on our dataset after being trained on both MIRROR and our new dataset (computer with GPU Tesla K80).

	Version Precision Recall mAP0.5 mAP0.5:0.95 Detection (ms)
	YOLOv3-t 0.988 0.961 0.984	0.644	20.1
	YOLOv4-t 0.976 0.936 0.976	0.626	15.2
	YOLOv5-s 0.987 0.991 0.993	0.724	25.8

Table 5 .

 5 YOLOv3-t, YOLOv4-t and YOLOv5-s performances in an unfamiliar context.

	Version Precision Recall mAP0.5 mAP0.5:0.95 Detection (ms)
	YOLOv3-t 0.374 0.221 0.207	0.054	19.8
	YOLOv4-t 0.191 0.109 0.089	0.021	14.4
	YOLOv5-s 0.820 0.656 0.739	0.389	24.2
	GPU	Tesla K80

https://roboflow.com/annotate

https://github.com/BenoitFaureIMT/CERIS_FishEye


Cyril Orengo
email: cyril.orengo@mines-ales.fr

Florian Tena-Chollet

Sophie Sauvagnargues

Numerical simulation of a preventative evacuation using a multi-agent framework

. The simulation is applied to Alès and its agglomeration (ten municipalities), subject to a dam failure that could cause a flood wave. Evacuation times for the ten municipalities were thus calculated and analyzed.

Introduction

Because of the multiplication of hazards and the increasing number of exposed human stakes caused by soil artificialization, Because of their lack of flexibility, structural protection methods (dams, dykes..) tend to show their limit. Indeed, some hazards can manifest themselves with intensity and spatial extension exceeding the calibration of structures (especially during floods). In some cases, it is not even possible to imagine structural protection (hurricane or volcanic eruption for example). This type of event raises the specter of a "disaster" understood as an event causing massive stress on population [START_REF] Kinston | Disaster: Effects on mental and physical state[END_REF] and furthermore a physical agent (hazards) hurting another physical agent [START_REF] Quarantelli | What is a disaster? A dozen perspectives on the question, What is a Disaster?: A Dozen Perspectives on the Question[END_REF]. Territories subject to this configuration of important and continuous risks must then prepare themselves to manage possible crises. Population evacuations take place in this context. More specifically, this article deals with a full pedestrian evacuation of the urban area of a medium-sized French city "Alès-en-Cévennes" (France), in the case of an imminent dam failure. This article aims at building a simulation of a preventive evacuation process on a territory of application, the urban area of the agglomeration of "Alès-en-Cévennes". The preventive evacuation of Alès would occur in the context of hydrological hazard, which can be caused by heavy rainfall, especially during the Cevenol episode. Significant risks related to the probable overflow of the Gardon goes along the triggering of an evacuation process in such a context. This makes the use of individual vehicles dangerous [START_REF] Ruin | Vulnérabilité face aux crues rapides et mobilités des populations en temps de crise[END_REF], and complicates the use of shuttles and rescue operations. Several simulations of pedestrian evacuations have been made through the years, but they are mainly applied to a limited size environment. This paper is organized as follows. Section 1 presents a literature review on evacuation simulation. Section 2 introduces the global approach, from the understanding of the process to the systemic modeling of it. Section 3 presents the simulation of it on a multi-agent framework (GAMA platform) and its application in the study case.

State of the art

The first problem encountered when simulating an evacuation is the evacuees routing [START_REF] Garcia-Ojeda | Planning Evacuation Routes with the P-graph Framework[END_REF]. Dijkstra algorithm has been the most used method for years [START_REF] Takabatake | Simulated effectiveness of a car evacuation from a tsunami[END_REF]. Consisting in a division of the network into arcs connecting nodes, corresponding to junctions, the individual chooses the direction that will minimize his total travel time. This approach is a direct application of the work of Zipf [START_REF] Zipf | Human Behaviour and the Principle of Least effort[END_REF] who theorized travel as optimization of metabolic expenditure. The behavior of the individual within his environment is thus, in the first instance, rationalized to the extreme. It is considered that whatever the situation, it will make the best choice. Other models, mainly in the field of distributed artificial intelligence, using agents with more or less extensive cognitive characteristics, operate based on individual strategies. Multi-Agent System (M.A.S.) technology has brought the opportunity to observe complex systems emergence from simple individual behaviors [START_REF] Drogoul | From Multi-Agent simulation to collective problem solving[END_REF]. The problem of pedestrian evacuation on large scale implies a multiplicity of individuals self-organizing on a network to reach shelters. These individuals are socially and physically interacting through the process, these interactions tend to modify their trip. [START_REF] Chaib-Draa | Systèmes multi-agents: principes généraux et applications[END_REF] identify two characteristics of M.A.S. that makes it appropriate to use. First, they are situated. They have a position, at any time, in the environment. This position evolve through time according to rules. The position change of the evacuees is essential to understand pedestrian evacuation dynamics, especially in an urban context, high densities being highly probable. The second characteristic is flexibility. An agent is meant to be non-deterministic; it can adapt its behavior to its environment. In a pedestrian evacuation context, it is materialized by collision avoidance and velocity adaptation according to the density of evacuees on a route.

Global approach for pedestrian evacuation

Due to the multiplicity of actors involved, and the level of uncertainty emanating from human behavior in a crisis, evacuation processes, from a certain quantity of population, can be considered as complex systems. A complex system is characterized by the level of unpredictability of its global functioning from the functioning of these elementary entities. The interest here is to find the global functioning of the system from the functioning of these entities. These entities maintain interactions throughout the process, which have a consequence on the global form of the whole. An evacuation fit well as a complex system due to the multiplicity of the actors and their interactions.

Understanding the functioning of a preventive pedestrian evacuation starts with the research of precedents. The first informational material available is the REX (Experience Feedback). Experience Feedback is a transversal tool for capitalizing on knowledge [START_REF] Gilbert | Feedback: constraints [Retours d'expérience : des contraintes[END_REF]. It is used in all types of organizations, public and private. The methods may vary but the objective remains substantially similar. Experience Feedback is an empirical practice that complements theoretical knowledge about a disaster and its management (Gauthier, 2008). It can be built around a case (case-based reasoning) or after exercises. (Marchand, 2011), our approach is obviously based on cases. The aim is to find significant cases, the synthesis of which could allow a generalization. Experience feedback provides valuable information on the general course of the process, and particularly the performance of the organization in charge of its management. However, it is rare to find concrete data on the movement of individuals during the evacuation, and on possible deviations from the instructions given by the authorities. This information is, on the other hand, available in various research works. Concerning the displacement of pedestrians, and its mechanical characteristics, the social force model of [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF] furnish a solid mechanical basis to our model. It has been used to answer several problematics such as the evacuation of metro platform [START_REF] Li | Pedestrian Evacuation Modeling and Simulation on Metro Platforms Considering Panic Impacts[END_REF], a shipwreck [START_REF] Kang | an improved social force model for pedestrian dynamics in shipwrecks[END_REF] and even adapted to simulate bicycle flows [START_REF] Rui | An Improved Social Force Model for Bicycle Flow in Groups[END_REF]. Many works conducted in the various field have shown herding effects in highdensity pedestrian flows [START_REF] Moussaïd | Experimental study of the behavioral mechanisms underlying self-organization in human crowds[END_REF], on the other hand, pedestrian interactions have been theorized in human sciences fields [START_REF] Houdremont | Rumor and Psychology of Crowds[END_REF]. The pedestrians are also interacting with their environment, in an urban context it mainly refers to roads and buildings. The UML diagram Figure 1 conceptualizes the objects of the model (actors and infrastructures) and their interactions. The large number of actors and the importance of the contextual framework (territory considered and spatio-temporal form of the event) force us to make choices in the elements integrated into the simulation model. The simulation model starts after the transmission of the evacuation order. The initial calibration of the simulation model does not admit any heterogeneity in the reception of the latter by the populations.

Figure 1: UML model of the simulation

Peoples are the main interest of the simulation. A specific object class "people" who is set to be the only one moving through the environment embodies them. Agent "people" possess a desired speed, a Gaussian with an average value of 1.34 meters per second and 0.25 as a standard deviation [START_REF] Fahy | Toward creating a database on delay times to start evacuation and walking speeds for use in evacuation modelling[END_REF]. They also have a perception distance, in which they collect information about the environment. The attributes of relaxation time correspond to the relaxation parameter identified by [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF]. Living places are set as a list of residential buildings. Each "people" agent has a living place, several "people" agents can be linked to the same living place. They choose a target destination according to their objective. The objective is a value that adapts to the situation. If the alert is launched, every agent "people" will search for the nearest shelter. Once they find it, they will build a path to reach it as quickly as possible. Thus, the agent "people" will execute a movement and reach his desired speed. His path is built thanks to the graph. The graph is with the road network. The path is meant to be constant but can be modified if an agent "people" encounters an obstacle, including another agent "people" themselves.

Simulation core

The simulation model is based on a free plug-in available for download on the GAMA platform. This plug-in is based on the Social Force Model of Dirk Helbing [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF].

Method and Model

The physical engine of our model is based on the "social force model" proposed by [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF]. This model defines human motion as a mix of psychological and physical aspects. It renders crowds' behavior by computing local interactions between pedestrians. Three parameters are used to model pedestrian's behavioral pattern in a crowded environment. The "repulsive effect" towards the physical obstacle and other pedestrians, the "attractive effect", which can be summed up by the influence of interest points on the pedestrian move, and the "desired velocity". Applied to our use-case, desire force represents the evacuation shelter chosen by the evacuee. The evacuees reach the objective at a certain speed (who tends to reach the desired velocity) and heading a certain direction, if it is possible. During his trip, the pedestrian will encounter obstacles, such as borders or another pedestrian. These elements apply a force on the pedestrian, and incentive him to adjust his trajectory. The path is a succession of edges; each pedestrian computes it at the beginning of the simulation.

Geographical environment of the simulation.

The geographical environment of the simulation model is generated within the GAMA platform by importing geographical data in shapefile format. A shapefile is a set of files related to one or more geographic objects (building(s), portion of network) containing information about its geometry, its actual geolocation, the method used for the two-dimensional projection, as well as various characteristics (commonly referred to as variables) that it possesses. The geographic objects we need to run the simulation model are of two types:

• Buildings: containing information about the type of building it is, the number of residents and the socioeconomic profile of these residents. The number of inhabitants is estimated using French statistics institute (INSEE) data, crossed with buildings type and shape information.

•

The road network: shaped as a line that contains information on the shape of the real road they represent. The width value allows the simulation to give the pedestrian the possibility to walk away from roads. This feature allows the construction of walking space.

The environment of the model is set from geographical data mostly available online on free access. The building shape is extruded from a French government database, socioeconomic information such as the number of inhabitants is integrated into the shape using spatial analysis tools. The Road network is crafted from an open street map. These data are compiled into a geodatabase, GAMA platform can read them then and built the environment.

Simulation results.

The simulation has been applied to the ten municipalities of "Agglomération Alès" Figure 4(a) threatened by a dam failure. The study area is crossed by the "Gardon d'Alès", a river well known for regular flooding, especially during the fall. The simulation was first launched on each municipality separately, in order to point out eventually heterogeneous response capacity of the population. Shelters are set in a prevention plan related to the dam, edited by the "prefecture du Gard", the state authority on the area. The whole area has been implemented in GAMA platform (multi-agent framework), but simulations are made on each municipality separately due to the high number of agents causing long calculation times. Table 1 shows evacuation time for every municipality. With a closer look, it appears that municipality with less population for a shelter tends to evacuate faster, except for Alès, which is a markedly bigger city and then offers a denser road network. The relationship between the number of shelters and evacuation times appears to be an evidence. Indeed, a less saturated network is a token for a fast evacuation. However, it also shows that the simulation is able to render interaction effects and velocity drops due to increasing density on the network.

Conclusion

Facing increasingly threatening hazards, civil evacuations are an efficient response to avoid casualties. Possibly involving thousands of people, they require knowledge enhancement. Launching an evacuation exercise at the scale of a city can be challenging, in terms of logistics. However, rising of artificial intelligence technology allow numerical simulation of the process. The outputs of these simulations can help crisis management organizations to improve their strategies. Enhancing knowledge on the evacuation proceeding is still a challenging topic. This work proposes a numerical simulation of the process focused on pedestrian mobility and people interactions.

The main interest of this study is to include human physical interactions to render realistic mobility in a crisis context. To that end, a multi-agent system framework has been used, allowing intelligent agents implementation.

The simulation has been applied on the "Agglomération d'Alès", threatened by a flood wave that would be caused by the failure of the nearby dam of Sainte-Cecile d'Andorge. Results show heterogeneous response among the ten municipalities. This simulation is currently simply applied on smoothed conditions. The whole population receives the alert at the same time and is compliant with the evacuation order. It is well known that the population is not systematically at their home. This will be taken into account for the development of the simulation. Eventual flooding due to meteorological events does not slow their trip through the network. Future works will then include various scenarios depicting situations that are more realistic. There is also space to enhance the psychological aspect of the behavior of agents "people".

Figure 3 :

 3 Figure 3: Study area (a) Imported into GAMA platform (b)

Figure 4 :

 4 Figure 4: Evacuation completion rate after one hour

Table 1 :

 1 Evacuation times for ten municipalities

		Cendras
	Saint-Martin de Valgalgues
	Saint Hilaire de Brethmas
	Municipalities	Alès-en-Cévènnes Branoux-les-Taillades La Grande Combe Laval-Pradel Sallis du Gardon Sainte-Cécile d'Andorge Saint-Christol lez Alès
		0	10	20	30	40	50	60	70	80	90	100
				Completion rate :	15min	30min	1h
		Municipality	Number of shelters		Population concerned	Population / Shelters Evacuation time
		Alès	11		3'673		334			65
		Branoux-les-Taillades	4			84		21			115
		La Grande Combe	4			401		100			60
		Laval-Pradel	2			4		2			40
		Salles du Gardon	4			444		111			99
	Sainte-Cécile d'Andorge	2			96		48			84
		Saint-Christol	2			104		52			58
		Saint-Hilaire de B.	1			198		198			135
		Saint-Martin de Val.	2			568		284			121
		Cendras	2			153		77			42