Ilaria Chillotti

Marc Joye

Damien Ligier

Jean-Baptiste Orfila

Samuel Tap

CONCRETE: Concrete Operates oN Ciphertexts Rapidly by Extending TfhE

Fully homomorphic encryption (FHE) extends traditional encryption schemes. It allows one to directly compute on encrypted data without requiring access to the decryption key. This paper introduces CONCRETE, an open-source library developed in Rust that builds on the state-of-art TFHE cryptosystem. It provides a userfriendly interface making FHE easy to integrate. The library deals with inputs of arbitrary format and comes with an extensive set of operations to play with ciphertexts, including a programmable bootstrapping.

INTRODUCTION

The idea of fully homomorphic encryption (FHE) emerged in 1978 when Rivest, Adleman and Dertouzos started talking about privacy homomorphisms [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF]. However, no solution was found until 2009 when Gentry presented the first instantiation of a FHE scheme [START_REF] Gentry | Computing arbitrary functions of encrypted data[END_REF].

A common feature in Gentry's original cryptosystem and in all subsequent FHE schemes is that ciphertexts contain noise. The vast majority of homomorphic operations make this noise grow. If not controlled, the noise in a ciphertext can compromise the encrypted plaintext and induce incorrect results at decryption time. This fact inherently limits the number of operations that can be performed on ciphertexts. A homomorphic encryption scheme supporting a predetermined noise threshold is termed leveled. The groundbreaking idea of [START_REF] Gentry | Computing arbitrary functions of encrypted data[END_REF] which made FHE possible, is a technique called bootstrapping enabling to reduce the noise-using only public material-when needed. This way, there is no more limitation on the maximal number of operations that can be performed and the scheme becomes fully homomorphic. Since Gentry's FHE scheme, many other schemes have been presented in the literature, but the bootstrapping technique has remained the main bottleneck, both in terms of running time (several minutes) and of key sizes (gigabytes). This state of affairs dramatically changed in 2015 when Ducas and Micciancio introduced the FHEW cryptosystem [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] mastering a bootstrapped NAND gate in less than a second yet with keys of about 1 GB in size. This was further improved in 2016 by Chillotti et al. and gave rise to the TFHE cryptosystem [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption over the torus[END_REF] running any bootstrapped binary gate in a few tens of milliseconds and with keys in the order of megabytes.

Furthermore, in addition of being relatively fast, the bootstrapping procedure in TFHE can be 'programmed': it enables the homomorphic evaluation of any function on a ciphertext while reducing the noise. This powerful technique opens new application scenarios for the practical use of FHE technologies.

The above reasons explain our choice to implement and extend the TFHE scheme in our CONCRETE library (CONCRETE stands for "Concrete Operates oN Ciphertexts Rapidly by Extending TfhE"). As for the programming language, we picked Rust, a new language that has become popular thanks to its performance (as good as C or C++ with the advantages of a high-level programming language), its memory safety, and its efficient memory usage and access.

CONCRETE follows TFHE's implementation: it makes use of arithmetic modulo 𝑞 with a small modulus natural for a machine such as 𝑞 = 2 32 or 𝑞 = 2 64 . This is very convenient because these moduli are natively supported while using unsigned integers with 32 or 64 bits and their respective efficient addition and multiplication operations. Further, CONCRETE unleashes the full potential of TFHE by encrypting and bootstrapping values of arbitrary format, including real numbers. In particular, it is not limited to boolean computation. This is achieved through the use of encoding functions.

The library is designed in layers. The lower-level layer, called Core API, is meant to be accessible by FHE experts and aims to be as efficient as possible. The layer above, named Crypto API, wraps the operator layer in a user-friendly way. It is accessible and easy to use by any programmer (even with a limited understanding of the cryptography behind it). It offers in addition extra capabilities, including automated metadata keeping track of the amount of noise.

CRYPTOGRAPHIC CONTENT OF THE LIBRARY

TFHE [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption over the torus[END_REF] is based on the learning with errors (LWE) problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], a hard problem on lattices, and its variant Ring-LWE [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF][START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF]. It deals with two types of ciphertexts: LWE ciphertexts and RLWE ciphertexts.

Encryption & Decryption

LWE ciphertexts. Let B denote the set {0, 1} and let 𝑞 be a power of two. Let also

Z 𝑞 = Z/𝑞Z. The plaintext space is Z 𝑞 . An LWE ciphertext 𝑐 𝑐 𝑐 ← LWE 𝑠 𝑠 𝑠 (𝜇) encrypting a plaintext 𝜇 ∈ Z 𝑞 under the secret key 𝑠 𝑠 𝑠 = (𝑠 1 , . . . , 𝑠 𝑛 ) ∈ B 𝑛 is a tuple 𝑐 𝑐 𝑐 = (𝑎 1 , . . . , 𝑎 𝑛 , 𝑏) ∈ (Z 𝑞 ) 𝑛+1
where 𝑎 1 , . . . , 𝑎 𝑛 are sampled uniformly at random in Z 𝑞 and 𝑏 = 𝑛 𝑗=1 𝑠 𝑗 𝑎 𝑗 + 𝜇 + 𝑒 (mod 𝑞), with 𝑒 a (small) discretized Gaussian noise.

Given a ciphertext (𝑎 1 , . . . , 𝑎 𝑛 , 𝑏), the decryption algorithm uses the secret key (𝑠 1 , . . . , 𝑠 𝑛 ) to obtain 𝜇 * 𝑏 -𝑛 𝑗=1 𝑠 𝑗 𝑎 𝑗 = 𝜇 + 𝑒 (mod 𝑞); see Fig. 1.3. If the message is encoded in the most significant bits (and thus if 𝜇 has its least significant bits set to zero) then, provided that the noise 𝑒 is not too large, rounding 𝜇 * enables to recover the original 𝜇. RLWE ciphertexts. Let 𝑁 be a power of two so that 𝑋 𝑁 + 1 is the 2𝑁 th cyclotomic polynomial. Let also

B 𝑁 [𝑋 ] = B[𝑋 ]/(𝑋 𝑁 + 1) 𝜇, 𝜇 ′ = 𝑚 (1) 𝜇 + 𝜇 ′ = 𝑚 + 𝑚 ′ (2) 𝜇 * = 𝑚 𝑒 (3)
𝜇 = 𝑚 (4)
Figure 1: Representation of plaintexts as a sequence of bits. Given a ciphertext (𝒶 1 (𝑋 ), . . . , 𝒶 𝑘 (𝑋 ), 𝒷(𝑋 )), the decryption proceeds by computing (in Z 𝑞,𝑁 [𝑋 ]) the polynomial µ * (𝑋 ) 𝒷(𝑋 )-𝑘 𝑗=1 𝓈 𝑗 (𝑋 ) 𝒶 𝑗 (𝑋 ) = µ(𝑋 )+ℯ(𝑋 ). As for LWE ciphertexts, if the message is encoded in the most significant bits of the coefficients of µ(𝑋 ), rounding each coefficient of µ * (𝑋 ) yields back the original µ(𝑋 ), provided that the noise ℯ(𝑋 ) is not too large.

Real Encoding on [𝒂, 𝒃]

The plaintext space is defined over Z 𝑞 . This section describes how to represent messages of a real domain 𝒟 = [𝑎, 𝑏] ⊂ R with a subset of Z 𝑞 . To do so, a number of bits 𝑛 msg are reserved to store the message 𝑚 ∈ 𝒟 as well as a number of padding bits 𝑛 pad in the MSBs. There are two different settings for the encoding: (i) the number of precision bits contained in the plaintext is maximized (Fig. 1.4) and (ii) the precision is limited to 𝑛 msg bits (Fig. 1.1);

The encoding functions are defined as (i) Encode(𝑚 ∈ 𝒟) = 𝑞 (𝑚 -𝑎)/(𝛿 • 2 𝑛 pad ) and as (ii) Encode(𝑚 ∈ 𝒟) = 𝑞 2 𝑛msg+𝑛 pad (𝑚 -𝑎) • 2 𝑛 msg /𝛿 with 𝛿 = 𝑏 -𝑎 + 𝜎 and 𝜎 = (𝑏 -𝑎)/(2 𝑛 msg -1). The quantity 𝜎 is a security margin to prevent wrong decryption nearby 0 ∈ Z 𝑞 (i.e., 𝑎 and 𝑏 in 𝒟), which boils down to actually consider the interval [𝑎, 𝑏 + 𝜎).

The decoding functions of a noisy plaintext 𝜇 * ∈ Z 𝑞 are defined as (i) rounding 𝜇 * to remove the noise and get 𝜇 and then computing Decode(𝜇) = 𝑎 + (𝜇 • 𝛿 • 2 𝑛 pad /𝑞) ∈ 𝒟, and (ii) simply computing Decode(𝜇 * ) = 𝑎 + (𝜇 * • 𝛿 • 2 𝑛 pad /𝑞) ∈ 𝒟.

Addition & Scalar Multiplication

LWE ciphertexts can readily be added together (component-wise addition). The result of an addition is an LWE ciphertext in (Z 𝑞 ) 𝑛+1 encrypting the sum (modulo 𝑞) of the input plaintexts.

This works analogously with RLWE ciphertexts. Note that in both cases the noises also add up as a result of the addition.

Remark 1. A way to avoid the modular reduction in the sum of the plaintexts is to make sure that they are small enough. For example, suppose that 𝑞 = 2 32 and that plaintexts viewed as 32-bit integers are of the form {𝑥 • 2 25 , 0 ≤ 𝑥 < 2 5 }. This means that plaintexts are made of 2 bits set to zero (i.e., the 2 left-most significant bits-these bits are called padding bits), 5 bits containing the message, and 25 bits set to zero; see Fig. 1.1. Hence, as illustrated in Fig. 1.2, the addition of two such plaintexts yields a plaintext as an element of {𝑥 • 2 25 , 0 ≤ 𝑥 < 2 6 }, that is, with only one bit of padding left.

By extension, LWE (resp. RLWE) ciphertexts can be multiplied by an integer constant. The noise after the scalar multiplication grows proportionally with respect to the integer constant.

External Product

LWE and RLWE ciphertexts can be added; unfortunately, they cannot be multiplied as easily. One may resort to a matrix-based approach [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased[END_REF] to this end. This involves two parameters: a basis 𝐵 ∈ N and a number of levels ℓ ∈ N. To avoid rounding, it is assumed that

𝐵 ℓ | 𝑞. RGSW ciphertexts. An RGSW ciphertext of µ(𝑋 ) ∈ Z 𝑁 [𝑋 ] un- der secret key (𝓈 1 (𝑋 ), . . . , 𝓈 𝑘 (𝑋 )) ∈ B 𝑁 [𝑋 ] 𝑘 is a matrix 𝒞 𝒞 𝒞 ∈ (Z 𝑞,𝑁 [𝑋 ]) (𝑘+1)ℓ×(𝑘+1) whose row #𝑡 where 𝑡 = 𝑖 + ( 𝑗 -1)ℓ, for 1 ≤ 𝑖 ≤ ℓ and 1 ≤ 𝑗 ≤ 𝑘 + 1, is an RLWE encryption under key (𝓈 1 (𝑋 ), . . . , 𝓈 𝑘 (𝑋 )) of plaintext µ 𝑡 (𝑋 ) -𝓈 𝑗 (𝑋 ) µ(𝑋 ) 𝑞 𝐵 𝑖 , with 𝓈 𝑘+1 (𝑋 )
-1. This is written 𝒞 𝒞 𝒞 ← RGSW 𝓈 𝓈 𝓈 (µ(𝑋 )).

External product. The external product [2, § 3.3] of an RGSW ci- phertext 𝒞 1 𝒞 1 𝒞 1 ← RGSW 𝓈 𝓈 𝓈 (µ 1 (𝑋 )) and of an RLWE ciphertext 𝒸 2 𝒸 2 𝒸 2 ← RLWE 𝓈 𝓈 𝓈 (µ 2 (𝑋 )) is noted 𝒸 3 𝒸 3 𝒸 3 = 𝒞 1 𝒞 1 𝒞 1 ⊡ 𝒸 2 𝒸 2 𝒸 2 . The resulting ciphertext 𝒸 3 𝒸 3 𝒸 3 is an RLWE encryption of µ 1 (𝑋 ) • µ 2 (𝑋 ). The external product is defined by 𝒞 1 𝒞 1 𝒞 1 ⊡ 𝒸 2 𝒸 2 𝒸 2 = G G G -1 (𝒸 2 𝒸 2 𝒸 2 ) • 𝒞 1 𝒞 1 𝒞 1 where G G G -1 (𝒸 2 𝒸 2 𝒸 2 ) is the gadget decomposition of 𝒸 2 𝒸 2 𝒸 2 .
The transformation G G G -1 (•) flattens a vector of (𝑘 + 1) polynomials of Z 𝑞,𝑁 [𝑋 ] into a row vector of (𝑘 + 1)ℓ polynomials of Z 𝑁 [𝑋 ] with small coefficients in the range [-𝐵/2, 𝐵/2). The use of the gadget decomposition enables to control the noise growth in the external product. 𝒸 0 . The output is an RLWE encryption of µ b (𝑋 ).

Programmable Bootstrapping

As aforementioned, homomorphic operations may increase the noise in ciphertexts, and when the noise grows too much ciphertexts cannot be decrypted anymore. This is why, from time to time, it is important to refresh noisy ciphertexts by reducing the amount of noise. Programmable bootstrapping (PBS) is a generalization of the bootstrapping technique allowing resetting the noise at a fixed level while at the same time homomorphically evaluating a function on the input ciphertext.

Programmable bootstrapping involves a series of three algorithms: (i) Switch Modulus, (ii) Blind Rotate, and (iii) Sample Extract. It is often followed by an LWE Key Switching algorithm. These algorithms are described below.

Modulus switching. The modulus switching is a classical technique in FHE for switching the modulus of ciphertexts. In TFHE, a modulus switching is performed prior to the blind rotation procedure. The Switch Modulus algorithm scales by 2𝑁 /𝑞 and rounds (i.e., performs the operation ⌈2𝑁 ( • mod 𝑞)/𝑞⌋) each component of the input LWE ciphertext (i.e., elements in Z 𝑞 ).

Blind rotation. The Blind Rotate algorithm homomorphically applies a rotation over the coefficients of the plaintext polynomial stored in an RLWE ciphertext. It is used to blindly put a desired coefficient in the constant term. This algorithm takes on input a (possibly trivial) 1

RLWE ciphertext 𝒸 𝒸 𝒸 𝑇 ∈ (Z 𝑞,𝑁 [𝑋 ]) 𝑘+1 encrypt- ing the test polynomial 𝑇 (𝑋 ) = 𝑡 0 + 𝑡 1 𝑋 + • • • + 𝑡 𝑁 -1 𝑋 𝑁 -1 , an LWE ciphertext 𝑐 𝑐 𝑐 = (𝑎 1 , . . . , 𝑎 𝑛 , 𝑏) ∈ (Z 2𝑁 ) 𝑛+1
encrypting 𝜇, and 𝑛 RGSW ciphertexts {𝒞 𝒞 𝒞 𝑖 } 1≤𝑖 ≤𝑛 encrypting each bit of the secret key (𝑠 1 , . . . , 𝑠 𝑛 ) ∈ B 𝑛 used to encrypt 𝑐 𝑐 𝑐. Note that the RGSW ciphertexts and the RLWE ciphertext are encrypted with the same secret key. The noisy plaintext contained in 𝑐 𝑐 𝑐 is noted 𝜇 * .

In Figure 2, the test polynomial is seen as a table where, for 0 ≤ 𝑖 ≤ 𝑁 -1, 𝑡 [𝑖] represents the 𝑖-th coefficient 𝑡 𝑖 of 𝑇 (𝑋 ), and 𝑡 [𝑖 + 𝑁 ] = -𝑡 𝑖 . The algorithm starts by initializing an accumulator ACC ← 𝑋 -𝑏 • 𝒸 𝒸 𝒸 𝑇 . Next, by using each ciphertext of {𝒞 𝒞 𝒞 𝑗 } 1≤ 𝑗 ≤𝑛 as control bit into a CMUX, the algorithm successively updates the accumulator as ACC ← CMUX(𝒞 𝒞 𝒞 𝑗 , ACC, 𝑋 𝑎 𝑗 • ACC) for 𝑗 = 1, . . . , 𝑛. The output is an RLWE ciphertext encrypting the plaintext

𝑋 -𝑏+ 𝑛 𝑗 =1 𝑠 𝑗 𝑎 𝑗 • 𝒸 𝒸 𝒸 𝑇 = 𝑋 -𝜇 * • 𝒸 𝒸 𝒸 𝑇 which contains 𝑡 [𝜇 * ] in its constant coefficient.
Sample extraction. It is easy to extract any of the 𝑁 coefficients inside an RLWE plaintext µ(𝑋 [𝑋 ] as an LWE ciphertext. The corresponding algorithm is called Sample Extract and simply consists in picking some of the coefficients of the input RLWE ciphertext and using them to build the output as an LWE encryption of the desired coefficient 𝜇 𝑖 . It is a public operation and adds no noise in the output. Key switching. After the blind rotation and sample extraction, the resulting LWE ciphertext is encrypted with a secret key that is different from the one used on input. In order to revert to the original key, one needs to perform a key-switching operation (this operation is optional). As for the external product, the corresponding Key Switch algorithm involves two parameters: a basis 𝐵 KS ∈ N and a number of levels ℓ KS ∈ N. The input dimension is denoted 𝑛 in and the output dimension 𝑛 out . This procedure is classical in FHE and is possible thanks to the use of a key-switching key; i.e., a list of 𝑛 in LWE ciphertexts encrypting each bit of the input secret key 1 A trivial RLWE ciphertext for plaintext µ(𝑋 ) is a ciphertext of the form (0, . . . , 0, µ(𝑋 )). multiplied by successive powers of basis 𝐵 KS (up to ℓ KS ). The output is an LWE ciphertext encrypting the same message as the input, with respect to the original secret key.

) = 𝜇 0 + 𝜇 1 𝑋 + • • • + 𝜇 𝑁 -1 𝑋 𝑁 -1 ∈ Z 𝑞,𝑁
𝑡 [0] multiplication by 𝑋 -𝑏 𝑡 [𝑏 ] CMUX(𝒞 𝒞 𝒞 1 , ACC, 𝑋 𝑎 1 • ACC) 𝑡 [𝑏 -𝑠 1 𝑎 1 ] 𝑒 1 CMUX(𝒞 𝒞 𝒞 2 , ACC, 𝑋 𝑎 2 • ACC) 𝑡 [𝑏 -𝑠 1 𝑎 1 -𝑠 2 𝑎 2 ] 𝑒 2 CMUX(𝒞 𝒞 𝒞 3 , ACC, 𝑋 𝑎 3 • ACC) CMUX(𝒞 𝒞 𝒞𝑛, ACC, 𝑋 𝑎𝑛 • ACC) . . . 𝑡 [𝑏 -𝑛 𝑗 =1 𝑠 𝑗 𝑎 𝑗 ] = 𝑡 [𝜇 * ] 𝑒 𝑛
Programmable Bootstrapping. It is essential to have at least one bit of padding left in the input LWE plaintext. This is a consequence of the negacyclic property:

𝑋 𝑁 +𝑢 = -𝑋 𝑢 . Without padding the output is only guaranteed up to the sign.

Look-up table.

There are multiple ways to represent a function 𝑔 : Z 𝑁 → Z 𝑞 . A simple way is to use a look-up table, which is a sort of dictionary containing pairs (𝑖, 𝑡 [𝑖]), where 𝑖 is the input index and 𝑡 [𝑖] = 𝑔(𝑖). In our implementation, the value 𝑡 [𝑖] is obtained by performing Encode ′ •𝑓 • Decode(𝑖). Observe that the encoding function might not be the one corresponding to Decode (i.e., Encode ′ ≠ Encode): in fact, the bootstrapping enables to change encoding. These values are used to program the test polynomial as

𝑇 (𝑋 ) = 𝑡 0 + • • • + 𝑡 𝑁 -1 𝑋 𝑁 -1 with 𝑡 𝑖 = 𝑡 [𝑖],
and store it in an RLWE ciphertext. It is easy to see that the constant coefficient of

𝑇 (𝑋 ) • 𝑋 -𝑖 is 𝑡 [𝑖],
that is, the right output in the look-up table.

Note that if the goal of the bootstrapping is simply to reduce the noise, function 𝑓 is the identity function.

Computing a Multiplication. Interestingly, a multiplication can be computed using two PBS operations. This follows from the observation that, in R, 𝑥 •𝑦 = (𝑥 +𝑦) 2 /4-(𝑥 -𝑦) 2 /4. Over encrypted data, this amounts to one homomorphic addition and one homomorphic subtraction to get the evaluation of 𝑥 + 𝑦 and 𝑥 -𝑦, two PBS's with function 𝑧 ↦ → 𝑧 2 /4 to get (𝑥 + 𝑦) 2 /4 and (𝑥 -𝑦) 2 /4, and finally one homomorphic subtraction to get 𝑥 • 𝑦.

CONCRETE IMPLEMENTATION

The CONCRETE 2 library is built as a stack of layers (Fig. 4) from the closest to the hardware to the most abstracted and easy-touse (Crypto API). In between, the API called Core API proposes an hardware generic API. At the moment, Core API only provides access to the CPU-based code version, but a GPU version (following the same API) is in preparation. On top of that, the Core API is wrapped in a more user-friendly API called Crypto API where every cryptographic object is represented as a structure. These structures also contain some metadata as the noise distribution, the number of padding bits or the decoding parameters. They are mainly used to ensure the correctness of the computation. The noise is monitored by a dedicated module abbreviated as NPE, for Noise Propagation Estimator.

The value of 𝑞 is not fixed so that all functions are currently defined for either 2 32 or 2 64 . Note that having functions for 𝑞 = 2 128 would be easy.

1 use concrete_lib:: * ; Code Example 1: A piece of code using CONCRETE's Crypto API to compute a multiplication with a constant, an addition with a constant, a PBS with the ReLU function and to decrypt.

NPE.

In a nutshell, the Noise Propagation Estimator (NPE) contains the noise formula associated to each homomorphic operator. It uses parts of the metadata associated to the ciphertext as inputs; i.e., the variances of the noise distribution. In the end, the noise variance of the output ciphertext is updated. In the case of computation with a cleartext (e.g., between a scalar and a ciphertext), the actual scalar is required as input.

FFT. The Fast Fourier Transform (FFT) is used to speed up the polynomial products, as provided by the FFTW [START_REF] Frigo | The design and implementation of FFTW3[END_REF] implementation. The latter has been slightly modified to be compliant with the Z 𝑞,𝑁 [𝑋 ] arithmetic. The idea is to multiply each polynomial coefficient by power of 𝑒 𝑖𝜋 /𝑁 for the forward FFT and by power of 𝑒 -𝑖𝜋 /𝑁 for the backward FFT. The Fourier representation of the polynomials uses 64-bit floating numbers.

Core API

The Core API is designed as an abstraction of the hardware dedicated code. Then depending on the underlying hardware actually present on the running machine, the API offers multiple choices which do not require any code modification by the end-user. For instance, the Core API offers some SIMD optimizations if supported by the CPU, or even running on a GPU if possible. Note that the latter is currently a mock-up and not open-sourced yet. Despite this convenient abstraction, the API aims to be as low-level as possible in order to yield better performance.

The API is divided into two main modules: (i) math containing non-cryptographic operations such as adding, subtracting or multiplying (unsigned) integers or polynomials, and (ii) crypto containing cryptographic-related operations such as encryption and decryption functions or bootstrapping and key switching functions.

Slices are used to represent messages, plaintexts, ciphertexts and keys. In Rust, a slice is a contiguous sequence of elements but at the difference of an array, its size is not known at compile time. A slice contains a pointer to the data and the length of the slice. Messages are stored in slices of f64, and plaintexts, ciphertexts and keys are stored in slices of unsigned integers u32 or u64.

Ciphertexts. Ciphertexts are stored in slices of unsigned 32-bit/ 64-bit integers. In Core API, functions are able to work on a collection of ciphertexts. This is modeled as a single slice containing several concatenated LWE ciphertexts. For instance, the key switch function can compute a key switch for each of the ciphertexts in the slice.

Secret keys. The LWE or RLWE secret keys are all sampled from a uniform binary distribution. The keys are stored in the same way as ciphertexts: in slices of unsigned 32-bit/64-bit integers such that in the first element of the slice are the 32/64 first bits of the key.

Random source. Uniform random integers are generated with OpenSSL. Discretized Gaussian integers are obtained with a Box-Muller algorithm using OpenSSL uniform random integers.

Benchmarks. Tables 1 and2 show the time needed to compute a PBS and a key switch for both 𝑞 = 32 and 𝑞 = 64. Benchmarks are obtained using Criterion, a Rust micro-benchmarking library. Each measurement is the mean duration of 500 iterations of the operation performed on a single thread.

Benchmarks were made on a personal computer with a 2.6 GHz 6-Core Intel ® Core ™ i7 processor.

Crypto API

The Crypto API wraps Core API in simple-to-use structures. Typically, metadata are directly included and automatically updated as the Core API homomorphic computation progresses. Code example 1 shows how to pick cryptographic parameters and generate secret keys (Lines 16 and 17), how to define an input encoder (Line 13), how to encode and encrypt a message (Line 23), how to generate Code example 2 shows how to pick cryptographic parameters and how to generate an RLWE secret key (Lines 2 and 3), how to define an input encoder (Line 6), how to encode and encrypt packed messages in RLWE ciphertexts (Lines 7 to 10), how to add two ciphertexts with padding (Line 13), to multiply by constants with padding (Line 14), how to extract an LWE from an RLWE (Line 16), and finally how to decrypt (Line 18).

Structures. The Crypto API introduces the following structures: Encoder, Plaintext, LWESecretKey, RLWESecretKey, LWEBSK, LWEKSK, LWE, VectorLWE, VectorRLWE, LWEParams, RLWEParams.

Cryptographic parameters. In order to ease the use of the library, some secure cryptographic parameters are offered to the end-user. For instance, in Code example 1, an RLWE secret key is created using &RLWE128_1024_1. Following the notations defined in Section 2, this means that the RLWE key provides 128 bits of security with 𝑁 = 1024 and 𝑘 = 1. Similar predefined sets are available for LWE parameters, such as &LWE128_630 providing 128 bits of security with 𝑛 = 630. The adequate standard noise distribution for each parameter set have been computed via the LWE Estimator [START_REF] Albrecht | On the Concrete Hardness of Learning with Errors[END_REF] in September 2020. Obviously for more advanced users, the cryptographic parameters can easily be set by hand. Code Example 2: A piece of code using CONCRETE's Crypto API to encrypt packed messages with RLWE and to compute constant multiplication and homomorphic addition before extracting one slot as an LWE ciphertext.

Encoders and ciphertexts. An encoder is a structure containing the bounds of the real interval, the number of bits of precision, the number of padding bits and the type of encoding. The ciphertext structures VectorLWE and VectorRLWE defined in the Crypto API are able to store one or more ciphertexts of the same type (namely LWE or RLWE). It also contains the required metadata to track the noise, the encoding, and the number of bits of message guaranteed to be correct all along computations. The noise evaluation is realized with the help of the NPE module. In the case where the noise bits are devouring the bits of the message, a message informs the user about the intact number of bits and the number of bits of message is updated.

To encrypt, a call to the function LWE::encode_encrypt for instance, allows one to obtain an LWE ciphertext from a message, a secret key and an encoder. Note that the same function is present in modules VectorLWE and VectorRLWE.

Padding bits. Some homomorphic functions require some bits of padding in order to avoid the reduction modulo 𝑞 and loose some most significant bits of the plaintext. Padding bits can be seen as a safety guard to ensure the computation correctness. For instance, an addition of two messages may result in a carry, which is translated into one padding bit. In the same vein, by default the PBS uses one padding bit and is able to add many of them in it's output. In the Crypto API, homomorphic operations requiring padding bits are suffixed with _with_padding.

Automatic generation of the look-up table. The Crypto API provides an automatic generation for the look-up table associated to an arbitrary function 𝑓 taking as input an f64 and outputting an f64, mainly called in the PBS. It takes as inputs the encoding of the inputs, the encoding of the outputs, and the function 𝑓 .

Benchmarks. Table 3 presents the time needed to compute a multiplication using two PBS's. The same setting as above is used. Table 4 gives the cost of a PBS and a key switch using the Core API and the Crypto API for the parameter set given in [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption over the torus[END_REF].

FUTURE WORK

The CONCRETE library offers an efficient and user-friendly interface to homomorphically compute over ciphertexts. There is a variety of ways to use encoding such as representing approximation of real numbers. Thanks to the programmable bootstrapping, it is possible to compute non-linear functions in addition to homomorphic additions and multiplications by scalars. We plan to add other homomorphic operations and features in the next versions of the library. In parallel, we are implementing the GPU version of the Core API level and building an automatic API dealing with padding and noise automatically on its own. Future works also include some studies about enhancing the FFT performance and further support of SIMD operations. Finally, we want to work on the parallelization of the existing code.

Figure 2 :

 2 Figure 2: Binary representation of the constant coefficient from the polynomial plaintext encrypted in the accumulator during the Blind Rotate algorithm.

2 Figure 3 :

 23 Figure 3: Representation of the PBS steps as a sequence of bits. Each rectangle shows the noisy plaintext encrypted by an LWE ciphertext but the third which is the plaintext in the constant coefficient of an RLWE ciphertext.

2 3 4 // parameters 5 let 8 2

 2458 fn main() -> Result<(), CryptoAPIError> { (min, max) = (-1., 1.); 6 let weight = 2.; 7 let bias = 3.; The CONCRETE library is released under the AGPLv3 license.

Figure 4 :

 4 Figure 4: Overview of the CONCRETE library architecture. Dashed boxes refer to upcoming features.

1 /

 1 / generation of a RLWE secret key 2 let rlwe_params = RLWEParams::new(1024, 1, -25)?; 3 let rlwe_sk = RLWESecretKey::new(&rlwe_params);

4 5 // encryption 6

 46 let encoder = Encoder::new(-5., 5., 5, 7)?; 7 let rlwe_ct_1 = VectorRLWE::encode_encrypt_packed( 8 &rlwe_sk, &[1.4, -3.5, 2.7], &encoder)?; 9 let rlwe_ct_2 = VectorRLWE::encode_encrypt_packed( 10 &rlwe_sk, &[-3.1, -2.2, 0.3], &encoder)?; 11 12 // homomorphic operations 13 let mut rlwe_ct_3 = rlwe_ct_1.add_with_padding(&rlwe_ct_2)?; 14 rlwe_ct_3.mul_constant_with_padding_inplace(&[2.3, 2., -1.5], 2.3, 5)?;

  White boxes indicate bits set to zero; MSBs are on the left and LSBs on the right. and Z 𝑞,𝑁 [𝑋 ] = Z 𝑞 [𝑋 ]/(𝑋 𝑁 + 1). The plaintext space for RLWE encryption is Z 𝑞,𝑁 [𝑋 ]. An RLWE ciphertext 𝒸 𝒸 𝒸 ← RLWE 𝓈 𝓈 𝓈 (µ(𝑋 )), encrypting a plaintext µ(𝑋 ) ∈ Z 𝑞,𝑁 [𝑋 ] under the secret key 𝓈 𝓈 𝓈 = (𝓈 1 (𝑋 ), . . . , 𝓈 𝑘 (𝑋 )) ∈ (B 𝑁 [𝑋 ]) 𝑘 is a tuple 𝒸 𝒸 𝒸 = (𝒶 1 (𝑋 ), . . . , 𝒶 𝑘 (𝑋 ), 𝒷(𝑋 )) ∈ (Z 𝑞,𝑁 [𝑋 ]) 𝑘+1 of 𝑘 + 1 polynomials, where 𝒶 1 (𝑋 ), . . . , 𝒶 𝑘 (𝑋 ) are sampled uniformly at random in Z 𝑞,𝑁 [𝑋 ] and 𝒷(𝑋 ) = 𝑘 𝑗=1 𝓈 𝑗 (𝑋 ) 𝒶 𝑗 (𝑋 ) +

	µ(𝑋 )+ℯ(𝑋 ) (mod (𝑞, 𝑋 𝑁 +1)), with ℯ(𝑋 ) a polynomial with (small)
	discretized Gaussian coefficients.

  The programmable bootstrapping algorithm implemented in CONCRETE takes on input an LWE ciphertext 𝑐 𝑐 𝑐 in encrypting a plaintext 𝜇 in under the key 𝑠 𝑠 𝑠 in ∈ B 𝑛 , and a bootstrapping key; i.e., a list of 𝑛 RGSW ciphertexts, each one encrypting a bit of the secret key 𝑠 𝑠 𝑠 in used to encrypt 𝑐 𝑐 𝑐 in . It outputs an LWE ciphertext 𝑐 𝑐 𝑐 out encrypting the plaintext 𝜇 out under the key 𝑠 𝑠 𝑠 out ∈ B 𝑘𝑁 .

	As depicted in Figure 3, this procedure is composed of three
	steps:
	(1) a modulus switching (to be compatible with 𝑁 ) wherein the
	input ciphertext in (Z 𝑞 ) 𝑛+1 is converted into a ciphertext in
	(Z 2𝑁 ) 𝑛+1 ;
	(2) a blind rotation of an RLWE ciphertext encrypting a redun-
	dant look-up table 𝑡 of size 𝑁 (which is rotated according to
	the output LWE ciphertext of Step 1);
	(3) a sample extraction of the constant coefficient of the RLWE.

Table 1 :

 1 PBS in milliseconds from CPU Core API with 𝑘 = 1, 𝐵 = 27 and ℓ = 3.

		𝑁 = 1024	𝑁 = 2048	𝑁 = 4096
	# bits	32	64	32	64	32	64
	𝑛 = 630	15.49 18.08 33.28 39.54 73.22 84.01
	𝑛 = 800	19.23 22.98 42.33 50.53 93.12 107.3
	𝑛 = 1024 24.54 29.16 54.14 64.18 117.9 135.2

Table 2 :

 2 LWE key switching (in milliseconds) from CPU Core API with 𝐵 KS = 4 and ℓ KS = 8.

		𝑛 out = 630	𝑛 out = 800	𝑛 out = 1024
	# bits	32	64	32	64	32	64
	𝑛 in = 1024 0.9912 2.292 1.171 2.872 1.518 3.652
	𝑛 in = 2048 2.130 4.661 2.495 5.877 3.200 7.699
	𝑛 in = 4096 4.413 9.476 5.134 11.89 6.592 15.39
	a bootstrapping key (Line 20), how to define an output encoder (Line
	30), how to homomorphically compute 𝑐 → max(0., 𝑤𝑒𝑖𝑔ℎ𝑡 •𝑐+𝑏𝑖𝑎𝑠)
	with a PBS (Lines 36 and 37), and finally how to decrypt (Line 40).

Table 3 :

 3 Multiplication (in milliseconds) with two PBS's from Crypto API with 𝑘 = 1, 𝐵 = 2 7 , ℓ = 3 and 64-bit integers. 𝑁 = 1024 𝑁 = 2048 𝑁 = 4096

	𝑛 = 630	35.78	78.90	167.2
	𝑛 = 800	45.82	100.1	213.3
	𝑛 = 1024	58.77	127.8	273.6

Table 4 :

 4 Comparison (in milliseconds) between Core API and Crypto API API. PBS: 𝑛 = 630, 𝑁 = 1024, 𝑘 = 1, 𝐵 = 2 7 and ℓ = 3. LWE key switch: 𝑞 = 2 32 , 𝑛 in = 1024, 𝑛 out = 630, 𝐵 KS = 4 and ℓ KS = 8. Planned Demo During the demo, we plan to quickly give an overview of CONCRETE, and then to run live tests for basic operations (both exact and approximate) and for neural network inference.

		CPU Core API Crypto API
	# bits	32	64	64
	PBS	15.49 18.08	18.18
	Key Switch 0.9912 2.292	2.262
	3.3

// github.com/zama


Marie Delavergne

Geo Johns

Adrien Lebre

Cheops, a service to blow away Cloud applications to the Edge

Keywords: Edge computing, Service composition, Service mesh

One question to answer the shift from the Cloud to the Edge computing paradigm is: how distributed applications developed for Cloud platforms can benefit from the opportunities of the Edge while dealing with inherent constraints of wide-area network links? Leveraging the modularity of microservice-based applications, we propose to deploy multiple instances of the same service (one per edge site) and deliver collaborations between them according to each request. Collaborations are expressed thanks to a DSL and orchestrated in a transparent manner by the Cheops runtime. We demonstrate the relevance of our proposal by geo-distributing Kubernetes resources.

Introduction

Nowadays, there is an indubitable shift from Cloud Computing to the Edge [START_REF] Tran | Collaborative mobile edge computing in 5g networks: New paradigms, scenarios, and challenges[END_REF]. The assumptions that are generally taken to develop Cloud applications are not valid anymore in the Edge context. For instance, the intermittent network connections should be considered as the norm rather than the exception. If you consider the Google Doc service, users in the same vicinity cannot work on the same document if they cannot reach the datacenter, even though they are close to each other. To reckon with the Edge constraints, and thus be able to satisfy requests locally, the most straightforward approach is to deploy an entire, independent instance of the application on every Edge sites. This way, if one site is separated from the rest of the network, it can still serve local requests 1 . The next step is to offer collaboration means between these instances when needed.

Git is an application that fulfills such requirements (even though it has not been designed specifically for this paradigm): Git operations can be performed locally and pushed to other instances when required.

We proposed the premises of a generalization of these Git concepts by presenting how an application can be geo-distributed without intrusive changes in its business logic thanks to a service mesh approach [START_REF] Cherrueau | Geo-distribute cloud applications at the edge[END_REF]. A service mesh is a layer over microservices that intercepts requests in order to decouple functionalities such as monitoring or auto-scaling [4]. Concretely, we proposed to leverage the modularity and REST APIs of cloud applications to allow collaborations in an agnostic manner between multiple instances of the same system.

In this paper, we extend our proposal to deliver a complete framework that allows multiple instances of a Cloud microservice based application to behave like a single one. Thanks to our framework, called Cheops, DevOps can share, replicate, and extend resources between the different instances in agnostic manner. A service managed by Cheops can be seen as a Single Service Image. We found this analogy with past activities on Single System Images [START_REF] Lottiaux | Openmosix, openssi and kerrighed: a comparative study[END_REF] relevant as the interest of SSI clusters was based on the idea that they may be simpler to use and administer. With Cheops, the challenge related to the collaboration between multiple instances of a system (the geo-distribution aspects) is reified at the level of the DevOps and externally from the business logic of the system itself.

The contributions of this article are as follows:

-A nonintrusive approach relying on service mesh concepts to achieve three kind of collaborations between services: sharing, replication, and cross. -A model of the different kind of relationships between resources that may exist in a microservice based applications. -A detailed description of the current Cheops prototype.

-A demonstration of the feasibility of the proposed framework and collaboration strategies in the Kubernetes ecosystem. The rest of this paper is organized as follows: Section 2 presents the generalization idea of our proposal, while Section 3 deals with the current architecture we followed to implement our proof-of-concept. Section 4 presents related works. Finally, Section 5 concludes and discusses future work.

Towards generic and noninvasive collaborations

::= s : Loc, σ scope | s : Loc R[[s : Appi]] = si R[[s : Loc&Loc ′ ]] = R[[s : Loc]] and R[[s : Loc ′ ]] R[[s : Loc%Loc ′ ]] = R[[s : Loc]] spread to R[[s : Loc ′ ]]
Fig. 1: Scope-lang expressions σ and the function that resolves service instance from elements of the scope R.

Scope-lang is a language introduced in [START_REF] Cherrueau | Geo-distribute cloud applications at the edge[END_REF], that extends the usual requests made from users to their application in order to reify the locality aspects. A scope-lang expression, which we call scope, contains information on the location where a specific request, or part of the request, will be executed. As an example, a scope defined as "s : App 1 , t : App 2 " specifies to use service s from App 1 (the application App on Site 1), and the service t from App 2 (on Site 2). Users defines the scope of the request to specify the exact collaboration between instances required for the execution of their request. The scope is interpreted during the execution of the request workflow to decide the execution location accordingly.

A more formal definition of the language is available in Figure 1, which has been extended to allow cross collaborations. Sharing Sharing is the collaboration which allows a service instance to use a resource from a service which is not the one assigned to its application instance.

Collaboration implementations for elementary resources

The typical example is getting a resource from a service B on another site for a service A as presented by the red arrows in Figure 2a. : application create a --sub-resource foo2 --scope {A: Site1, B: Site2} 1. A user requests to create a resource on service A from Site1 (Service A1), using a sub-resource f oo2 from service B on Site2 (Service B2). 2. The request is intercepted and transferred to Cheops. 3. Cheops extracts the scope from the request and interprets it. 4. Cheops transfers the request to service A, until A needs the sub-resource. 5. The outgoing request is intercepted, and at this point, is transferred to Site2. 6. Cheops on Site2 uses its catalog to find Service B endpoint and transfer the request to this service to get f oo2.

The service response (containing the resource itself) is finally transferred back to

Service A through Cheops.

Replication Replication is the ability for users to create and have available resources on different Edge sites to deal with latency and split networks. Replication main action is duplication: transfer the request to every involved sites and let the application execute the request locally. The operation does not simply consists in forwarding the request to the different instances, though. Cheops keeps track of the different replicas in order to ensure that future CRUD operations achieved on any replica will be applied on all copies, maintaining eventually the consistency over time. To do that, Cheops relies on a data scheme, called the replicant, that links a meta-ID to the different replica IDs and their locations. Figure 2b sums up the workflow to create a replicated resource on two sites: To provide eventual consistency, Cheops follows the Raft protocol, with one replicant acting as the leader.

Cross Cross is the last collaboration we identified. The idea is to create a resource over multiple sites. The main difference with respect to the aforementioned replication concept is related to the aggregation/divisibility property. In the replication, each copy is independent, even if they all converge eventually based on the CRUD operation. A cross resource can be seen as an aggregation of all resources that constitutes the cross-resource overall. Some resources which cannot be divided by an application API will require an additional layer in the business logic to satisfy the divisibility property.

Similarly to the replicant data scheme, Cheops keeps tracks of the different resources in order to perform CRUD operations in the expected manner. A CREATE operation for instance can distribute the resource over different sites (if this resource is divisible), while a READ will be performed on each "sub-resource" composing the cross-resource in order to return the aggregated result.

How Cheops deals with split-brain issue for cross resource is left as future work. However, it is worth noting that the unreachability of one site that hosts a part of the cross resource faces multiple challenges. An illustration of Cross is depicted in Figure 2c: application create a --name bar --scope {A: Site1% Site2}.

1. A user sends a request to create a resource specifying the involved sites. 2. The request is intercepted and transferred to Cheops. 3. Cheops extracts the scope and interprets it. 4. Cheops creates the resource on the first site (Site1) and passes the request to other involved sites. 5. Cheops on Site2 identifies the extended resource and creates an identifier within Cheops to forward to the deployed resource site

Relationship model

Many resources have dependencies with each other (a virtual machine in the OpenStack ecosystem depends on an image, a network, an IP, etc.; a deployment file in Kubernetes is linked to several pods; etc.).

Fig. 3: The different dependencies Hence, it is mandatory to rely on a relationship model for replication and cross operations. This model will be used to keep track on each critical resource and ensure that CRUD operations are performed thoroughly. We have identified and formulated three dependencies, depicted in Figure 3.

Requirement defines a relationship between two resources that is not critical for the survival of either of the resource but rather is a necessary link during a particular operation. The operation can be any operation performed upon either of the resource and while it is performed, the link is vital. If it is severed, the operation will terminate and not succeed. If the link is maintained and no external factors affect the operation, the operation will be a success and after this the link between these resources is insignificant. Hence, a broken link after the operation does not affect either of the resource. An example for OpenStack is a VM requires an image, for the creation operation.

Reliance defines a relationship between two resources that is critical for the survival of either one of the resource or both. If the link between these resources is cut at some point during the lifetime of these resources it will impact the existence of the resources and can lead to a failure condition. Involved resources are independent and one resource cannot alter the other resource. For example, in Kubernetes, a pod, when created with a secret, relies on this secret.

Composition consists of intrinsic dependencies between resources: the life cycle of the two resources are linked. The creation of resource A implies the creation (and respectively the destruction) of resource B. Composition is obviously wider, as one resource can be linked to a collection of other resources, which in their turn can also depend on sub-resources. For example, in OpenStack a stack can be composed of VMs, and in Kubernetes, a deployment is composed of pods.

Creation patterns for replication/cross operations

As mentioned, the goal of the relationship model is to ensure that Cheops operations are done thoroughly when the manipulated resource is not elementary, but depends on other resources. We discuss in this paragraph the various cases.

Requirement For a replication or a cross scenario, the user have the choice to first replicate B everywhere A will be; in this case, the creation of A can be executed without specifying the location of B, it will be executed locally on each site. The other choice is to specify the dependency in the creation request, which is represented in Figure 4. Reliance This relationship follows a similar approach from requirement for replication and cross. The primary objective being to preserve the strong relationship between the resources A and B, Cheops needs to ensure the reachability of Resource B.

As before, a user can still replicate Resource B to ensure that Resource A will not suffer from a network partition. Otherwise, the process is the same as the requirement, except for: first, the dependency information needs to be stored in Cheops database for resource B to warn users against resources failures in replicas in case of a deletion of B. Second, Cheops needs to warn the users of affected resources (replicas of resource A) in case of network partition that affects B, because they will be in a failure state. Composition For replication scenario, a copy of resource A is created on the involved sites which in turn creates resources B, C and D on each of these sites with a cascading effect from the normal, local execution of the creation of A. An update on resource A for a secondary layer resource B, C or D is propagated across the involved sites and also follows normal execution on each site. Network split brain is managed through the Raft protocol that ensures eventual consistency between all replicas. For cross scenario, the process is similar and will also follow a cascading approach. Each compound resource will be created in a cross manner.

Cheops

The global architecture of our proof-of-concept is depicted in Figure 5. Cheops follows a modular approach, composed of various microservices, which are linked together through REST API protocol. There is one Cheops agent per site and agents monitor known Cheops agents through heartbeats. Cheops Core consists of the communication, interface and database modules. The communication module creates a service mesh around the involved sites. This module also talks with the core API module in the core.

Cheops internals

Core API is a management module created for the framework that acts as a service which interconnects all the services inside Cheops. Cheops Glue is designed to help Cheops Core translate Cheops API requests into the respective application API and vice-versa. Since each application has its own pattern for intercepting API, Glue helps in understanding these patterns and convert them to an agnostic API for Core. It is developed independently to an application. The analyser service in Glue evaluates the request from scopelang and converts it into a generic request understandable by the Core API service, while the translator do the reverse operation. Cheops Glue also manages the creation of extra business logic for divisibility property of cross collaboration for specific types of resource. It also handles the network requirements and implements the relationship model.

Validation

We demonstrated the correctness of our proposal on Kubernetes. The feasibility for the collaborations were studied for replication and cross operations:

-For replication, we manipulated replicated pods across two sites.

-For cross, we created a namespace and performed a few operations to validate the existence of the namespace the two sites.

Experiments have been performed over two sites of the Grid'5000 experimental testbed [1] (Rennes and Nantes). These instances were completely independent of each other and local to the infrastructure. On each site, we deployed a Kubernetes cluster, composed of one master and one worker node, as well as a Cheops agent. The goal of the experiments was to validate the expected behaviour. Table 1

Related work

Popular solutions such as Rancher 2 , Volterra 3 or Google Anthos 4 geo-distribute a service to the Edge with a centralised approach. In these approaches, sites are not autonomous, centralised single source of truth and additional details are added to the business logic. Our solution focuses on forming a decentralized P2P set of autonomous application instances without changing the application code. Istio 5 uses a sidecar mechanism to intercept all the requests at the resource level. It creates an individual sidecar or a broker for each service as opposed to Cheops which manages all microservices at each site with a single broker.

MiCADO-Edge [START_REF] Ullah | Micado-edge: Towards an application-level orchestrator for the cloud-to-edge computing continuum[END_REF] extends cloud operator to edge. It uses the KubeEdge [START_REF] Xiong | Extend cloud to edge with kubeedge[END_REF] to orchestrate. Mck8s [START_REF] Tamiru | mck8s: An orchestration platform for geo-distributed multi-cluster environments[END_REF] is another similar solution with geo-distribution application deployments. The solution is as a wrap around KubeFed 6 . These Framework provides primarily a centralised approach to manage the resources without the Edge sites autonomy like our solution.

Hybrid control planes such as OneEdge [START_REF] Saurez | Oneedge: An efficient control plane for geo-distributed infrastructures[END_REF] brings autonomony to the Edge. This solution is quite similar to our proposal but the centralised aspect still makes this solution an unsuitable candidate for us.

TOSCA [2] is a framework which standardises a deployment pattern across platforms. Our solution aims not at avoid creating any additional code, but to allow collaborations between sites without changes in code.

Future work and conclusion

In this paper we presented our service-mesh like framework, Cheops, that allows Devops to geo-distribute a micro-services based application following a REST API without requiring intrusive changes in the business logic. This service mesh relies on these applications modularity and the deployment of instances of the application on each site composing the Edge infrastructure.

Cheops relies on scope-lang, a DSL we previously introduced to allow users to explicit the execution location of their requests as well as the type of collaborations between the different service instances. To ensure the correctness of 2 https://rancher.com Accessed 2022-07-06 3 https://medium.com/volterra-io/tagged/kubernetes Accessed 2022-03-20 4 https://cloud.google.com/anthos Accessed 2022-07-06 5 https://istio.io Accessed 2022-07-06 6 https://github.com/kubernetes-sigs/kubefed Accessed 2022-07-06 each collaboration, Cheops relies also on a relationship model we introduced. Finally, we demonstrated the relevance our approach on simple collaborations across different sites.

We are currently working on a model to introduce patterns for application code for cross collaboration which requires a step further. As discussed above, we also need to focus on tolerance for intermittent networks across collaborations. Finally, one future area of focus will be to add control loops in Cheops in order to optimize the placement of resources. In our current version of the approach, DevOps need to manually specify the location, and finding the optimal site may be an additional overhead.

We claim our approach to bring existing Cloud applications to the Edge without entangling any geo-distribution code in the business logic is crucial to stimulate the shift to include Edge sites in the global capabilities of the Cloud.

2. 1

 1 Scope-lang Appi, Appj ::= application instance s, t ::= service si, tj ::= service instance Loc ::= Appi single location | Loc&Loc multiple locations | Loc%Loc cross locations σ

Figure 2

 2 Figure 2 depicts the three collaborations implemented in Cheops.

Fig. 2 :

 2 Fig. 2: The different Cheops collaborations

Fig. 4 :

 4 Fig.4: Behaviors to observe following the dependencies 5. Since Resource B is only required for some operations, this dependency is stored in Cheops database for further usage (in these operations).

Fig. 5 :

 5 Fig. 5: Cheops architecture Cheops agents are divided into two main components which are Cheops Core API and Cheops Glue.Cheops Core consists of the communication, interface and database modules. The communication module creates a service mesh around the involved sites. This module also talks with the core API module in the core. Core API is a management module created for the framework that acts as a service which interconnects all the services inside Cheops. Cheops Glue is designed to help Cheops Core translate Cheops API requests into the respective application API and vice-versa. Since each application has its own pattern for intercepting API, Glue helps in understanding these patterns and convert them to an agnostic API for Core. It is developed independently to an application. The analyser service in Glue evaluates the request from scopelang and converts it into a generic request understandable by the Core API service, while the translator do the reverse operation. Cheops Glue also manages the creation of extra business logic for divisibility property of cross collaboration for specific types of resource. It also handles the network requirements and implements the relationship model.

  Site1 to create two replicas of the bar resource. 2. The request is intercepted and transferred to Cheops. 3. Cheops extracts the scope and interprets it. 4. Cheops creates the replicant, and passes the request to create it to Cheops on the other involved site (Site2), as well as the request of creation of bar on both sites, which is simply the request without the scope. 5. Both Cheops execute the request of creation; the response is intercepted to fill the local IDs on the replicants and the response is transferred to the user, replacing the local ID by the meta-ID of the replicant.

application create a --name bar --scope {A: Site1 & Site2}.

1. A user sends a request on

Table 1 :

 1 and Table 2 presents the results. Replication Kubernetes CLI requests

	Operation	Location	Result
	kubectl create pod purple -scope{Site1&Site2}	Site1 Pod purple created on Site1 and Site2
	kubectl create pod violet -scope{Site1&Site2}	Site2 Pod violet created on Site1 and Site2
	kubectl get pod violet	Site1 Pod violet from Site1 is displayed
	kubectl get pod violet	Site2 Pod violet from Site2 is displayed

Table 2 :

 2 Cross Kubernetes CLI requests