The Internet of Things (IoT) is one of the most important technologies in our current world. It is composed of connected devices with sensors and processing abilities, all connected to a single platform that orchestrates them. The integration of these IoT devices into many real-life applications (eg., transportation, industries, ...) imply significant performance and efficiency improvements. As a consequence, we have seen a boom in the number of IoT devices deployed and their corresponding platforms. These IoT devices use real-time data from their deployment environment and send them to the platform. The collected data by these devices often consist of sensitive information belonging to the individual who uses this technology. Hence, the privacy of users' data is one of the important concerns in IoT. Moreover, IoT applications rely on automating frequent tasks to achieve better efficiency. Unfortunately, moving control of usually human-controlled operations to the IoT presents some non-negligible risks to the safety of IoT users.

This thesis deals with the privacy and safety concerns raised by IoT. We propose security protocols that preserve the privacy of the users' data. In addition to privacy, we design verifiable solutions that guarantee the correctness of the computations performed by the IoT devices and the platform and hence increase trust toward this technology. We design these solutions while focusing on their performance. More precisely, we propose protocols that are scalable to cope with the increasing number of IoT devices. We also consider protocols that are fault-tolerant to cope with the frequent dropouts of IoT devices. We particularly focus on two security protocols: Secure Aggregation and Remote Attestation.

Secure aggregation is a protocol where an aggregator computes the sum of the private inputs of a set of users. In this thesis, we propose the first verifiable secure aggregation protocol (VSA) that gives formal guarantees of security in the malicious model. Our solution preserves the privacy of users' inputs and the correctness of the aggregation result. Moreover, we propose a novel fault-tolerant secure aggregation protocol (FTSA) based on additively-homomorphic encryption. The scheme allows users in secure aggregation to drop from the protocol and offers a mechanism to recover the aggregate without affecting the privacy of the data. We show that FTSA outperforms the state-of-the-art solutions in terms of scalability with respect to the number of users.

On the other hand, a remote attestation protocol is a protocol that allows an IoT device (acting as a prover) to prove its software integrity to the IoT platform (acting as the verifier). We propose a new collaborative remote attestation protocol (FADIA) in which devices collect attestations from each other and aggregate them. FADIA deals with the heterogeneity and dynamic nature of IoT by considering fairness in its design. The evaluation of FADIA shows an increase in the lifetime of the overall network. i

IoT and its Applications

With the recent advances in embedded systems and communication technologies, the Internet of Things (IoT) paradigm emerge and evolves rapidly. Indeed, researchers expect that the number of IoT devices installed will raise to 41.6 billion devices that will generate 79.4 ZB of data in the year 2025 [START_REF] Dignan | Iot devices to generate 79.4zb of data in 2025, says idc[END_REF]. IoT is composed of connected objects with sensors and processing abilities. The connected objects exchange data with each other and with external systems. IoT spans different life sectors such as medical care, end-consumers, industrial, and even military applications. The main benefit of IoT originates from its ability to automate daily tasks leading to improved efficiency, productivity, and accuracy of existing systems.

Many applications use IoT technologies to improve the quality of their services and to reduce their operational cost. We discuss the main applications where IoT made a significant contribution to their advancement.

Home Automation It may involve temperature and humidity sensors, live monitoring devices, electric appliances control, etc. Smart homes [START_REF] Prospero | Best smart home hubs of[END_REF] provide a platform for end consumers to collect data from their houses and automate actions. The main benefit of smart homes is offering more life convenience for end-consumers and cost-saving by optimizing energy consumption.

Healthcare The medical sector also benefits from IoT technologies to improve healthcare systems [PSJH + 20]. It allows the collection of more rich medical data from patients which are used to improve the research work and studies on existing diseases [START_REF] Istepanian | The potential of internet of m-health things "m-iot" for non-invasive glucose level sensing[END_REF]. Additionally, IoT can improve the live monitoring of patients leading to improved treatment of emergency cases.

Transportation Automated cars are the future of the world. This promising technology strongly depends on IoT sensors and devices that are installed inside vehicles and on the 1 Chapter 1. Introduction roads [START_REF] Mahmud | Integration of electric vehicles and management in the internet of energy[END_REF]. These devices communicate with each other to provide autonomous driving features for passengers. Industry 4.0 One of the main reasons behind the boom of IoT technologies is their use in industries [START_REF] Yang | The internet of things in manufacturing: Key issues and potential applications[END_REF]. Industry 4.0 involves the deployment of smart sensors and IoT platforms in the production lines. The exchange of data between the product and the production line enables a much more efficient connection of the supply chain. Thus, it leads to a reduction in production costs and an improvement in product quality.

Infrastructures Large-scale applications that cover metropolitan projects have also a huge interest in IoT technologies. They involve smart cities [START_REF] Poon | Sleepy in songdo, korea's smartest city[END_REF] where smart sensors enable services like parking search, environmental monitoring, water distribution, and traffic management. They also involve smart grids [START_REF] Sayed | Chapter 18 -scada and smart energy grid control automation[END_REF] that enable smart monitoring of electricity consumption in a large inhabited area.

IoT Components

The IoT involves two main components: the IoT end-devices (the sensors, actuators, etc.) and the IoT platform to which these end-devices are connected. We describe the role and the properties of each of these components.

IoT End-Devices

These are the devices installed at the peripheries of the IoT network. They collect live data from the environment and perform simple actions. An example of these devices is smart sensors, programmable logic units (PLC), cameras, electricity relays, etc. Although there exist many types of IoT end-devices, they all share some common characteristics:

• Deployed in large-scale: It is common in many IoT applications that the IoT end-devices are deployed in large numbers and spread across multiple geo-dispersed locations. For example, smart city applications install end-devices in different locations to track live information about the environment in multiple locations. This allows authorities to take better decisions that help improve the life quality in some regions.

• Low in Resource: Due to the need for large number of devices in some applications, the manufacturers have to decrease their costs to make them affordable. This comes at the cost of minimizing the resources that these devices possess such as their processing power, their data transfer speed, and their energy resources.

• Heterogeneity: The complexity of IoT applications requires deploying different types of IoT end-devices. These devices can have different properties in terms of their amount of resources and their software stack.

• Mobility: In many applications, the end-devices are supposed to move frequently within some areas. For example, in industrial applications, smart sensors may be connected to objects to track the production or business process.

IoT Platform

In addition to the IoT end-devices, IoT applications deploy an IoT platform to provide their servers. The IoT platform is the brain of the IoT which manages all the connected IoT end-devices. It involves the network architecture and the processing servers that collect data from the end-devices and analyze/process them. The IoT platform administrators control these servers. They define how the data is processed and what decisions and actions to take based on the data analysis. These IoT platforms may be deployed physically on-premises or might use cloud technologies and thus get installed as software services on the cloud.

The Dark Side of IoT

Along with the bright side of IoT comes a dark side. Security researchers raise concerns about the security of IoT devices and their impact on the privacy and safety of users [START_REF] Lo'ai Tawalbeh | Iot privacy and security: Challenges and solutions[END_REF]. We identify three types of adversaries for IoT that raise serious security problems: Adversaries controlling some IoT devices, adversaries controlling the IoT platform, and external adversaries that are on the same network of the IoT devices. In this section, we present the different types of adversaries and their impact on the user's safety and privacy.

Adversaries Controlling The End-Devices

It is possible to have IoT end-devices performing attacks on the IoT application. This can happen either due to users of these devices acting maliciously or due to the devices being compromised. In such cases, the adversary aims to compromise the IoT application to influence its logic or to leak private information about other users. In these attacks, the adversary controls the inputs of the compromised devices. Hence, it can influence the results and decisions. An example of such attacks is the attack on the implantable cardiac devices from St. Jude Medical (2017) [START_REF] Larson | Fda confirms that st. jude's cardiac devices can be hacked[END_REF]. The attacker compromised these implementable and threatened the safety of the users. Another example is the famous StuxNet Malware (2009) [START_REF] Kushner | The real story of stuxnet[END_REF]. This malware infected PLC devices at Iranian nuclear plant and caused damage to its components while remaining undetected by reporting false information about the actual performance. Therefore, to secure the IoT, one should consider the malicious behavior of IoT end-devices and thus verify their inputs.

Adversaries Controlling The Platform

The IoT platform collects users' data for further processing. However, users cannot trust the platform as this data often contains private information. IoT platform owners might be interested in increasing their profit by reselling these data to malicious entities. Indeed, in 2009 the Dutch parliament rejected a smart metering program, basing their decision on privacy concerns [START_REF] Mckenna | Smart meter data: Balancing consumer privacy concerns with legitimate applications[END_REF]. The smart metering program aims to collect live data from Dutch households about their electricity consumption. However, the Dutch parliament raised concerns about the misuse of this data by electricity companies. Therefore, to secure the IoT, one should consider the malicious behavior of the IoT platform.

External Adversaries

External attackers are connected to the IoT network. Hence, they can see the messages sent from the devices to the platform. This allows the adversary to tamper with these messages. Moreover, external attackers may exploit existing vulnerabilities on the IoT end-devices and thus take control of these end-devices. In addition, some external attackers may also have physical access to the IoT end-devices which allows them to perform hardware attacks on the devices. These types of adversaries are mainly interested in three attacks types:

• Leaking Sensitive Data: In this type of attack, the attacker exploits the lack of security mechanisms on IoT end-devices to collect private information from the user of that device. These attacks happen either due to insecure communication between the IoT end-devices and the IoT platform or due to software and hardware vulnerabilities that allow the attacker to leak private data.

• Privilege Escalation: External adversaries aim to get more privileges by compromising the end-devices. This allows the adversaries to perform more sophisticated attacks and gain more information as shown in Section 1.3.1.

• Creating Botnets: The adversaries can compromise a large number of IoT devices to create botnets. A botnet is a group of Internet-connected devices used to perform Distributed Denial-of-Service (DDoS) attacks, steal data, send spam, and allow the attacker to access the device and its connection. The owner can control the botnet using command and control (C&C) softwares [START_REF] Sabanal | Thingbots: The future of botnets in the internet of things[END_REF]. One of the most popular botnets that hit the IoT is "Mirai Botnet (2016)" [AAB + 17]. It is composed primarily of embedded and IoT devices, and it took the Internet by storm in late 2016 when it overwhelmed several high-profile targets with some of the largest distributed denial-of-service (DDoS) attacks on record.

Problem Statement

It is clear how important IoT is to our world. It is even more clear that the trend of integrating more and more IoT devices will keep increasing. Therefore, one very important goal for researchers is securing these IoT devices to make sure that this integration is not a curse but rather a benefit for humanity. In this thesis, we aim for designing security protocols for IoT devices. We first start by posing the question: Are existing protocols designed for standard IT devices (e.g., computers) can solve the security concerns of IoT? The direct answer to this question is No. Researchers have already identified the limitation of IT world security solutions and traced back this limitation to the unique characteristics of IoT devices (see Section 1.2.1). Therefore, in this thesis, we aim to design customized security protocols that take into consideration all the constraints of the IoT ecosystem. We specifically study the security protocols on three main axes: scalability, fault tolerance, and verifiability.

• Scalability: We aim to design scalable security protocols that involve thousands or possibly millions of devices. This allows for more practical solutions targeting IoT applications that run with a large number of IoT devices.

• Fault Tolerance: We aim to design security protocols that are reliable in case of failures of some devices. This allows for more practical solutions targeting IoT applications with mobile devices that may encounter connectivity problems and occasionally fail to receive and deliver messages.

• Verifiability: We aim to design security protocols that do not rely on trusting the different IoT components (processing platform, end-devices, etc.). By integrating verification mechanisms into our design, we can verify that third-party IoT platforms are correctly processing the collected data. Additionally, verifiable security protocols can also ensure that compromised devices cannot affect the results of our protocol without being detected.

Security Protocols for IoT

In this thesis, we focus on two very important security protocols that can be gamechangers for improving IoT security. Namely, secure aggregation protocols and remote attestation protocols.

Secure Aggregation Protocols

Secure aggregation consists of computing the sum of data collected from multiple sources without disclosing these individual inputs. Hence, the goal of a secure aggregation protocol is to preserve the privacy of the data sources. Researchers identified that such protocols are useful to improve privacy guarantees in IoT applications. More precisely, secure aggregation can be used at the network layer to secure the data exchange from the enddevices to the platform. Smart grid applications are a good example. Moreover, secure aggregation can also be used at the processing layer to allow multiple IoT platforms to aggregate securely their collected data. For example, secure aggregation can be applied to IoT platforms that are using federated learning. Therefore, we classify secure aggregation into the following two categories.

• Intra-Platform Secure Aggregation: Smart grids are IoT end-devices that monitor energy consumption in households and industries. These devices collect live measurements of energy consumption and send them to service providers. The service providers compute statistics on the collected data thus enabling them to optimize their energy supply and improve their business model. Collecting these data from households poses a privacy problem. It allows the service providers to perform real-time surveillance and profile the tenants by determining their behavior patterns. Service providers may also determine the used electric appliances in households and track the behavior of renters/leasers.

Secure aggregation can be used to protect the energy consumption measurements of each household and allows the service provider to only compute their sum. By only disclosing the statistical average value of a large inhabited area, the privacy of inhabitants is preserved.

• Inter-Platform Secure Aggregation: One of the most important technologies used at the IoT processing layer is machine learning. The processing units of IoT platforms use machine learning to train models from the data collected from IoT devices. These models are used to improve the quality of the IoT application. Recently, federated learning emerged as a new collaborative machine learning technology to train machine learning models. This new technology consists of several federated clients holding private data and contributing to the training of a machine learning model collaboratively: Each client first trains a local machine learning model using its dataset and further shares training updates with a server. The server computes the average of the training updates and sends the average back to the clients. The clients update their local model and repeat the process so that they finally converge to one shared, global model. Thanks to this new technology, several IoT platforms (acting as FL clients) can train more accurate machine learning models using larger and more diverse datasets (collected from different IoT infrastructures).

Unfortunately, federated learning may compromise the privacy of IoT users. Adversaries, who have access only to the training updates (sent by each FL client) can perform inference attacks to reveal some data samples from the private training dataset. Therefore, it is very important to secure the federated learning protocol. Secure aggregation can be used to protect the training updates and allows the federated learning server to only compute the average of the updates. By protecting the individual training updates from each IoT platform, secure aggregation helps improve the privacy of IoT users.

In this thesis, we are interested in designing secure aggregation protocols that can scale to a large number of users, do not require the availability of all users, and where their results are publicly verifiable.

Remote Attestation Protocols

Remote Attestation (RA) schemes are protocols that enable a device to prove the integrity of its software to another remote device. It involves two roles: the prover (the device that proves its software integrity) and the verifier (the device that verifies the integrity of the prover's software). In RA, the verifier relies on a root of trust existing on the prover device to perform integrity checks on the prover's running software. It then creates a cryptographic proof and sends it to the verifier. The verifier upon validating this proof authenticates the prover and thus trusts its software. RA is very useful for IoT applications since it can be used to detect compromised IoT end-devices. Basic RA solutions require installing a verifier in the IoT platform which verifies the state of all IoT end-devices. Such a solution is not practical since it does not scale well with the number of IoT devices. To solve this problem, collaborative RA protocols are used where the IoT devices attest to each other and create a single proof for their software integrity. In this thesis, we raise questions about the scalability of existing collaborative RA protocols in dynamic and heterogeneous networks. Thus, we aim to design efficient RA protocols that scale with a large number of IoT end-devices and can support their dynamic nature and heterogeneity of IoT devices in the network.

Contributions

The thesis describes novel secure aggregation and remote attestation protocols that are suitable for the IoT. The thesis is organized intro three parts. In what follows, we summarize the contributions in each part:

Part I: Secure Aggregation

In Chapter 3, we perform an in-depth literature study of secure aggregation protocols that are based on cryptographic techniques and consequently propose a new definition of this concept. We present existing techniques for secure aggregation as instantiations of our new definition and we compare them. The chapter gives a clear view of the advantages and disadvantages of each of the secure aggregation types.

In Chapter 4, we present the first formal definition of security for secure aggregation protocols in the malicious model. Our new security definitions captures malicious aggregators and users. Then, we design a novel verifiable secure aggregation (VSA) protocol and prove that it achieve our security definitions.

Part II: Secure Aggregation for Federated Learning

In Chapter 5, we conduct a large-scale study on secure aggregation solutions specifically designed for federated learning applications. We identify the main security, privacy, and performance challenges raised by using secure aggregation for federated learning and we categories the existing solutions based on the challenges they tackle. The study finishes with key takeaways that can help developers design, develop or improve secure aggregation schemes for federated learning.

In Chapter 6, we design a novel secure and fault-tolerant aggregation protocol for federated learning. For this purpose, we propose a new threshold encryption scheme (based on the Joye-Libert encryption scheme [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF]) and we use it to achieve a highly scalable secure aggregation protocol that supports users dropping frequently from the network. We are able to reach the theoretical limit in terms of scalability with respect to the number of users.

Part III: Remote Attestation

In this Chapter 7 we design a novel collaborative remote attestation protocol that relies on device-to-device connection to perform attestation of a large network. Our solution has better scalability than the existing collaborative remote attestation protocol. It focuses on the heterogeneity aspect of IoT networks and integrates fairness by design. We show by experiments that by developing a fair-by-design protocol, we can achieve better scalability for a RA protocol.

Chapter 2

Preliminaries and Cryptographic Building Blocks

In this thesis, we propose new protocols that improve IoT in terms of security. To build these protocols we rely on a set of security assumptions and some existing cryptographic primitives. For this purpose, we introduce, in this chapter, the relevant assumptions and tools used throughout the thesis. Additionally, we present the basic security protocols and cryptographic schemes that are considered interesting building blocks for our solutions.

Notations

We use some common notations throughout the thesis. We present these notations in Table 2.1.

N

The set of natural numbers {1, .., inf}.

Zn

The set of integer modulus n {0, .., n-1}.

[n]

The set {1, .., n}.

[n] -

The set {1, .., n-1}.

I

An interval of integers. F An algebraic field. G An algebraic group. Z * n The multiplicative group modulus n.

x ⟨i⟩ The i-th bit of x = x ⟨1⟩ ||...||x ⟨ℓ⟩ .

|U |

The cardinality of the set U . r ←$ D r is sampled uniformly at random from distribution D.

D 1 c ≈ D 2
The two distributions are not distinguishable by a computationally bounded adversary.

D 1 s ≈ D 2
The two distributions are not distinguishable by a computationally unbounded adversary.

Hard Problems and Assumptions

In cryptography, it is common to rely on the hardness of some mathematical problems to build secure systems. In this thesis, we rely on a set of hard problems which we present in this section.

Decisional and Computational Diffie-Hellman Assumptions

Given a finite, cyclic group G of order p and generator g, we present the following four assumptions (ordered from strongest to weakest):

Definition 2.2.1: Inv-DDH Assumption

Given the two distributions: D 1 : {(g, g a , g c )} and D 2 : {(g, g a , g a -1 )} such that a, c ←$ Z p and a -1 is the inverse of a in Z p , the assumption states that D 1 c ≈ D 2 .

Definition 2.2.2: DDH Assumption

Given the two distributions: D 1 : {(g, g a , g b , g c )} and D 2 : {(g, g a , g b , g ab )} such that a, b, c ←$ Z p , the assumption states that D 1 c ≈ D 2 .

Definition 2.2.3: GDH Assumption

The assumption states that given g a , g b ∈ G and O DDH such that a, b ←$ Z p and O DDH (g x , g y , g z ) is an oracle that returns (g xy ? = g z ), there is no polynomial time algorithm that outputs g ab except with some negligible probability.

Definition 2.2.4: CDH Assumption

The assumption states that given g a , g b ∈ G such that a, b ←$ Z p , there is no polynomial time algorithm that outputs g ab except with some negligible probability.

Decisional Composite Residuosity Assumption

Given N = pq where p and q are two large primes. We define the following assumption (initially introduced in [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]) in the multiplicative group Z * N 2 :

Definition 2.2.5: DCR Assumption Given two distributions:

D 1 : {x N mod N 2 } and D 2 : {x mod N 2 } such that x ←$ Z * N 2 .
The assumption states that D 1 c ≈ D 2 .

Cryptographic Schemes

In this section, we present the main cryptographic schemes used in our thesis.

Threshold Secret Sharing (SS)

A threshold secret sharing scheme (SS) is a scheme that allows sharing a secret value with n parties such that a threshold number of these parties can reconstruct the secret value. It is composed of two algorithms:

• SS.Share(s, t, n, I) → {(i, ⟨s⟩ i )} ∀i∈[n] :
The algorithm takes as input secret s ∈ I and a reconstruction threshold t, and generates n random shares.

n]) ∧ (|I| < t) ∧ (s ∈ I) ∧ (s ′ ∈ I), SS.Share(s, t, n, I) → {(i, ⟨s⟩ i )} ∀i∈[n] : {(i, ⟨s⟩ i )} ∀i∈I s ≈ SS.Share(s ′ , t, n, I) → {(i, ⟨s ′ ⟩ i )} ∀i∈[n] : {(i, ⟨s ′ ⟩ i )} ∀i∈I Definition 2.

3.3: Homomorphism

SS is said to be homomorphic in I if and only if:

∀s 1 , ∀s 2 , ∀n, ∀t, ∀I, s.t. (I ⊂ [n]) ∧ (|I| ≥ t) ∧ (s 1 , s 2 ∈ I), Pr   r ̸ = s 1 + s 2 SS.Share(s 1 , t, n, I) → {(i, ⟨s 1 ⟩ i )} ∀i∈[n] , SS.Share(s 2 , t, n, I) → {(i, ⟨s 2 ⟩ i )} ∀i∈[n] , SS.Recon({(i, ⟨s 1 ⟩ i + ⟨s 2 ⟩ i )} ∀i∈I , I) → r   = 0
Realization over the Field Z p Shamir's secret sharinf scheme (SSS) [START_REF] Shamir | How to share a secret[END_REF] is a realization of the threshold secret sharing scheme SSS in the field Z p . SSS is correct, secure, and homomorphic, and defined as follows:

• SSS.Share(s, t, n, Z p ) → {(i, ⟨s⟩ i )} ∀i∈[n] :
The algorithm first generates a polynomial p(x) with uniformly random coefficients in Z p and of degree t -1 such that p(0) = s.

It then sets

⟨s⟩ i = p(i), ∀i ∈ [n].
• SSS.Recon({(i, ⟨s⟩ i )} ∀i∈I , Z p ) → s: The algorithm uses the Lagrange interpolation formula [START_REF] Meijering | A chronology of interpolation: from ancient astronomy to modern signal and image processing[END_REF] to compute the value of p(0) as follows:

s = p(0) = ∀i∈I η i ⟨s⟩ i mod p where η i = ∀j∈I,j̸ =i j j -i mod p
We additionally define the following algorithm for Shamir's Secret Sharing:

• SSS.ReconExp({(i, g ⟨s⟩ i )} ∀i∈I , G) → g s :
The algorithm uses the Lagrange interpolation formula on the exponent to compute the value of g s = g p(0) = ∀i∈I (g ⟨s⟩ i ) η i .

Lemma 2.3.1

Given the cyclic group G of prime order p and generator g, it holds that:

∀s, ∀n, ∀t, ∀I, ∀g ∈ G s.t. (I ⊂ [n]) ∧ (|I| ≥ t) ∧ (s ∈ Z p ), Pr r ̸ = g s SSS.Share(s, t, n, Z p ) → {(i, ⟨s⟩ i )} ∀i∈[n] , SSS.ReconExp({(i, g ⟨s⟩ i )} ∀i∈I , G) → r = 0 Lemma 2.3.2
Given the cyclic group G of prime order p and generator g, it holds that:

∀s 1 , ∀s 2 , ∀n, ∀t, ∀I, ∀g 1 , ∀g 2 s.t. (I ⊂ [n]) ∧ (|I| ≥ t) ∧ (s 1 , s 2 ∈ Z p ) ∧ (g 1 , g 2 ∈ G), Pr   r ̸ = g s 1 1 g s 2 2 SSS.Share(s 1 , t, n, Z p ) → {(i, ⟨s 1 ⟩ i )} ∀i∈[n] , SSS.Share(s 2 , t, n, Z p ) → {(i, ⟨s 2 ⟩ i )} ∀i∈[n] , SSS.ReconExp({(i, g ⟨s 1 ⟩ i 1 g ⟨s 2 ⟩ i 2 )} ∀i∈I , G) → r   = 0
Realization over the Integers A variant of Shamir's secret sharing is defined over the integers (rather than in a field). The secret sharing scheme over the integers is defined by Rabin [START_REF] Rabin | A simplified approach to threshold and proactive rsa[END_REF] and we denote it by ISS. The scheme shares a secret integer s in an interval I = [-η, η] and provides σ-bits statistical security where σ is a security parameter.

• ISS.Share(s, t, n, I) → {(i, ⟨s⟩ i )} ∀i∈[n] : The algorithm first generates a polynomial p(x) with uniformly random coefficients in [-2 σ ∆ 2 η, 2 σ ∆ 2 η] and of degree t -1 such that p(0) = ∆s where ∆ = n!. It then sets

⟨s⟩ i = p(i), ∀i ∈ [n].
• ISS.Recon({(i, ⟨s⟩ i )} ∀i∈I , Z p ) → s: The algorithm uses the Lagrange interpolation formula to compute the value of p(0) as follows:

s = p(0) = ∀i∈I ν i ⟨s⟩ i ∆ 2 where ν i = ∆ ∀j∈I,j̸ =i j ∀j∈I,j̸ =i j -i

Symmetric Encryption

A symmetric encryption scheme parameterized with a security parameter λ, its key space K, message space M, and ciphertext space C is composed of the following algorithms.

• Enc k (m) → e: It encrypts the message m with key k. ≈ D 2 where D 1 and D 2 are defined as follows:

∀k ∈ K, m ∈ M, Pr[m ̸ = Dec k (Enc k (m))] = 0 Definition 2.
• D 1 : {(e, k)} such that k ←$ K and e ← Enc k (m) • D 2 : {(e ′ , k ′ )} such that e ′ ←$ S 1 (1 λ ), k ′ ←$ S 2 (e ′ ,
m) and S 1 , S 2 are any PPT algorithms that may share a state.

Definition 2.3.7 of non-committing encryption says that it is possible for a simulator to come up with a ciphertext which can later be explained as an encryption of any message, in such a way that the joint distribution of the ciphertext and the key in this simulated experiment is indistinguishable from the normal use of the encryption scheme, where a key is first sampled and then an encryption of m is generated.

In this thesis, we will use (Enc, Dec) for authenticated encryption scheme and (Enc * , Dec * ) for a non-commiting authenticated encryption scheme.

Pseudo Random Generator

Key Agreement Scheme

A key agreement scheme KA is a scheme parameterized by the security parameter λ and the key space K. It is composed of the following algorithms:

• KA.Param(1 λ ) → pp: Given a security parameter λ it generates the public parameters pp.

• KA.Gen(pp) → (pk, sk): This algorithm generates a key pair from the public parameter.

• KA.Agree(pp, sk, pk 1 , pk 2 , G) → k: This algorithm uses a private key, two public keys, and a hash function G to generate an encryption key.

Definition 2.3.9: Correctness

The key agreement scheme is correct if and only if:

∀λ, Pr       k 1,2 ̸ = k 2,1 KA.Param(1 λ ) → pp, KA.Gen(pp) → (pk 1 , sk 1 ), KA.Gen(pp) → (pk 2 , sk 2 ), KA.Agree(pp, sk 1 , pk 1 , pk 2 , G) → k 1,2 , KA.Agree(pp, sk 2 , pk 2 , pk 1 , G) → k 2,1       = 0 Definition 2.

3.10: Security

The key agreement scheme is secure if and only if D 1 c ≈ D 2 where the two distributions are defined as follows:

D 1 :        (pk 1 , pk 2 , r) KA.Param(1 λ ) → pp, KA.Gen(pp) → (pk 1 , sk 1 ), KA.Gen(pp) → (pk 2 , sk 2 ), r ←$ K        D 2 :        (pk 1 , pk 2 , k) KA.Param(1 λ ) → pp, KA.Gen(pp) → (pk 1 , sk 1 ), KA.Gen(pp) → (pk 2 , sk 2 ), KA.Agree(pp, sk 1 , pk 1 , pk 2 , G) → k       
Realization based on DDH Under the DDH assumption we can construct a KA scheme that is secure in the random oracle G (see Section 2.4.3) as follows:

• KA.Param(1 λ ) → pp: From the security parameter λ, it chooses a group G of order p and generator g where the DDH holds in G. The public parameters are set to pp = (G, g, p).

• KA.Gen(pp) → (pk, sk): It outputs (g a , a) where a ←$ Z p .

• KA.Agree(pp, sk, pk 1 , pk 2 , G) →:

It outputs k ← G G (pk 1 ,pk 2 ) (pk sk 2 ).

Ideal Functionalities and Protocols

The Universal Composability Framework (UC)

In this thesis, we use the standard universal composability framework proposed by Canetti [START_REF] Canetti | Universally composable security[END_REF]. The UC framework defines a probabilistic polynomial time (PPT) environment machine Z that oversees the execution of a protocol in one of two worlds:

The "ideal world" execution involves "dummy parties" (some of whom may be corrupted by an ideal adversary S) interacting with a functionality F. The "real world" execution involves PPT parties (some of whom may be corrupted by a PPT real-world adversary A) interacting only with each other in some protocol Π. Let EXEC Π,A,Z (x) denote the random variable (over the local random choices of all the real world parties) describing the output of an execution of Π with environment Z and adversary A, on input x.

Similarly, let IDEAL F ,S,Z (x) denote the random variable (over the local random choices of a simulator S) describing the output of an execution of F with environment Z and simulated adversary S, on input x. Moreover, Let EXEC Π,A,Z and IDEAL F ,S,Z denote the ensembles {EXEC Π,A,Z (x)} x∈{0,1} * and {IDEAL F ,S,Z (x)} x∈{0,1} * respectively. We refer to [START_REF] Canetti | Universally composable security[END_REF] for a more detailed description of both executions.

Definition 2.4.1: Protocol Realization

Let F be an ideal functionality. A protocol Π is said to UC-realize F if for any adversary A, there exists a simulator S such that for all environments Z,

IDEAL F ,S,Z c ≈ EXEC Π,A,Z .
Additionally, we say that protocol Π operates in G-hybrid-model, if Π uses the ideal functionality G.

Definition 2.4.2: Protocol Emulation

Let G 1 , G 2 be ideal functionalities and let Π 1 , Π 2 be multi-party protocols. We say Π 1 in the G 1 -hybrid model UC-emulates Π 2 in the G 2 -hybrid model if for any adversary A 1 , there exists an adversary A 2 such that for all environments Z,

EXEC Π 1 ,A 1 ,Z c ≈ EXEC Π 2 ,A 2 ,Z .
Furthermore, we follow the definitions in [START_REF] Canetti | Universally composable security[END_REF] for modeling adversary corruptions. When the adversary corrupts a party it sends a backdoor message (sid, ID) where sid denotes the session id and ID denotes the identifier of the corrupted party. This happens at the very beginning of the protocol execution in the case of static corruption. For simplicity, we do not show these messages in the ideal functionalities as we assume the default behavior is that party ID is recorded as corrupted.

We also use the work in [START_REF] Canetti | Universal composition with joint state[END_REF] which describes the execution of multi-sessions of a protocol. We denote by Π and F, the multi-session extensions of the protocol Π and functionality F respectively. We recall that the UC theorem with joint state (JUC theorem): Theorem 2.4.1: Universal Composability with Joint State [START_REF] Canetti | Universal composition with joint state[END_REF] Given protocol Π that UC-realizes F in G-hybrid-model and a protocol Ψ that UC-realizes functionality Ĝ in the real-world model, it is true that the composition of Π and Ψ: Π • Ψ in the real-world model UC-emulates Π in G-hybrid-model.

In this section, we present the ideal functionality of the primitives we use in this thesis. Additionally, we discuss a possible realization for some of these functionalities.

Common Reference String (CRS)

We use the ideal functionality F D,n CRS parameterized by the sampling algorithm D and the number of parties n. The purpose of this functionality is to have a common string crs sampled from a fixed distribution and available to all parties of the protocol. Notice that this proposed functionality differs from the one proposed in [START_REF] Canetti | Universal composition with joint state[END_REF] because it supports distributing the CRS to n parties. It is described in Figure 2.1.

Functionality F D,n CRS F D,n
CRS runs with parties P 1 ,..., P n and is parameterized by an algorithm D and a security parameter λ.

• When receiving a message (sid, CRS, P i ) from P i , if this is the first CRS message, compute crs ←$ D(1 λ ). Then, send (sid, CRS, crs) to P i and S. Check if received message (sid, CRS, ...) from all parties. If yes, halt. If no, continue.

Random Oracle Model

Random oracles are typically used as an idealised replacement for cryptographic hash functions in schemes where strong randomness assumptions are needed. The ideal functionality of the random oracle returns a uniformly random response from the output domain. Additionally, if a query is repeated, it responds the same way every time that the same query is submitted. Throughout this thesis, we use the following hash functions modeled as random oracles.

• H G : {0, 1} * → G. This hash function is used to generate random group elements from arbitrary strings. The group used in this hash function is indicated as a parameter in its superscript.

• G G : G 3 → {0, 1} λ . This hash function is used as a key-derivation function to extract a λ-bit key from a group element, and the first two inputs are used to seed the function.

Sharing Random Number (RShare)

We define the ideal functionality F t,n,F RShare parameterized by the field F, the number of parties n, and a threshold t ≤ n. The purpose of this functionality is to generate a uniformly random element in the field F and secretly share it (using Shamir's secret sharing) with the n parties. The functionality is described in Figure 2.2.

Realization This functionality can be realized by letting each party P i generate its random value r i ←$ F and secretly share it (using authenticated channels) with the other parties SS.Share(r i , t, n, F) → {(j, ⟨r i ⟩ j )} ∀j∈ [n] . Then, each partly P i simply sums the shares it receives to obtain the share ⟨r⟩ i = n j=1 ⟨r j ⟩ i where r = n 1 r i .

Oblivious Transfer (OT)

An oblivious transfer protocol (OT) is a protocol executed between two parties: the sender and the receiver. The sender inputs a pair (m 0 , m 1 ) whereas the receiver inputs a selection bit x ∈ {0, 1}. At the end of the protocol, the receiver outputs value m x Functionality F t,n,F RShare F t,n,F RShare runs with parties P 1 ,..., P n and is parameterized by field F, the number of parties n, and a threshold t ≤ n.

• When receiving a message (sid, init, P i ) from P i , if this is the first init message, compute r ←$ F.

• When all init messages are received from the n parties, compute SS.Share(r, t, n, F) → {(i, ⟨r⟩ i )} ∀i∈[n] and send (sid, share, ⟨r⟩ i ) to each P i and send (sid, share) to S.

Functionality F OT

F OT interacts with a receiver R and a sender S. Auxiliary Inputs: the length of the sender input ℓ

• Upon receiving a message (sid, send, S, m 0 , m 1 ) from S, where m i ∈ {0, 1} ℓ , store (m 0 , m 1 ).

• Upon receiving a message (sid, recv, R, x) from R, check if a (send, sid, S, ...) message was previously sent. If yes, send (sid, sent, m x ) to R and (sid, sent) to adversary S and halt. If not, send nothing to R (but continue running). We present the construction proposed by Chou and Orlandi [START_REF] Chou | The simplest protocol for oblivious transfer[END_REF] in Figure 2.4. The authors of the OT protocol prove that it UC-realizes the functionality F OT in the random oracle model. Their proof relies on the CDH assumption. Later Hauck and Loss [START_REF] Hauck | Efficient and universally composable protocols for oblivious transfer from the cdh assumption[END_REF] identify a flow in the proof from [START_REF] Chou | The simplest protocol for oblivious transfer[END_REF] and provide a patch for the proof that relies on the hardness of the GDH assumption. Based on the work of Hauck and Loss [START_REF] Hauck | Efficient and universally composable protocols for oblivious transfer from the cdh assumption[END_REF] we restate the following two Lemmas.

Lemma 2.4.1

For any PPT adversary A that statically corrupts a receiver in Π OT protocol, and any PPT environment Z, the algorithm S rcv (defined in [START_REF] Hauck | Efficient and universally composable protocols for oblivious transfer from the cdh assumption[END_REF]) simulates the execution for A under the GDH assumption (i.e., IDEAL FOT,Srcv,Z c ≈ EXEC ΠOT,A,Z ).

OT Protocol Π OT Receiver Sender (x ∈ {0, 1}) (m 0 , m 1 ) A = g α α ←$ Z p β ←$ Z p B ← A x g β κ ← G G (A,B) (A β ) B κ 0 ← G G (A,B) (B α ) κ 1 ← G G (A,B) (( B A ) α ) c 0 ← Enc * κ 0 (m 0 ) (c 0 , c 1 ) c 1 ← Enc * κ 1 (m 1 ) m x ← Dec κ (c x )
Figure 2.4: The OT protocol [START_REF] Chou | The simplest protocol for oblivious transfer[END_REF] parameterized by the cyclic group G of order p and generator g.

Lemma 2.4.2

For any PPT adversary A that statically corrupts a sender in Π OT protocol, and any PPT environment Z, the algorithm S snd (defined in [START_REF] Hauck | Efficient and universally composable protocols for oblivious transfer from the cdh assumption[END_REF]) simulates the execution for A under the CDH assumption (i.e., IDEAL FOT,Ssnd,Z c ≈ EXEC ΠOT,A,Z ).

In a nutshell, the simulator S rcv takes the messages of the receiver and extracts the receiver's choice. It then gets the output from F OT and generates the simulated sender messages accordingly. On the other hand, the simulator S snd takes the messages of the sender and extracts the sender's input pair. In our work, we are interested in reusing S snd and S rcv algorithms for our proofs.

Garbled Circuits (GC)

A garbled circuit protocol proposed by Yao [START_REF] Andrew | How to generate and exchange secrets[END_REF] runs between two parties (a garbler G and an evaluator E). It is used to evaluate an arbitrary function f chosen by G on the private input x of E. Yao garbling scheme is defined as two algorithms:

• GC.Grb(1 λ , f ) → (F, {l b x,i } ∀b∈{0,1},∀i∈[ℓx] , {l b out,i } ∀b∈{0,1},∀i∈[ℓout]
): Given the security parameter λ and the function f , the algorithm generates a garbled circuit F and a label for each bit of the input and output (ℓ x and ℓ out are the bit-length of the input and output, respectively).

• GC.Eval(F, {l x ⟨i⟩ x,i } ∀i∈[ℓx] ) → {l out ⟨i⟩ out,i } ∀i∈[ℓout]
: Given the garbled circuit F and the labels of the input bits, the algorithm outputs the labels of the result out = f (x).

Protocol with GC and OT to compute

f θ,M Evaluator (x = x 1 ||...||x ℓ ) Garbler (θ, M ) F, {l b x,i }, l b out ← GC.Grb(1 λ , f θ ) ∀i ∈ [ℓ], ∀b ∈ {0, 1} A = g α , F α ←$ Z p β i ←$ Z p ∀i ∈ [ℓ] B i ← A x ⟨i⟩ g βi ∀i ∈ [ℓ] κ i ← G G (A,Bi) (A βi ) ∀i ∈ [ℓ] {B i } ∀i∈[ℓ] κ 0 i ← G G (A,Bi) (B α i ) ∀i ∈ [ℓ] κ 1 i ← G G (A,Bi) (( B i A ) α ) ∀i ∈ [ℓ] c 0 i ← Enc * κ 0 i (l 0 x,i ) ∀i ∈ [ℓ] c 1 i ← Enc * κ 1 i (l 1 x,i ) ∀i ∈ [ℓ] {(c 0 i , c 1 i } ∀i∈[ℓ] , C C ← Enc * l 1 out (M ) l x ⟨i⟩ x,i ← Dec κi (c x ⟨i⟩ i ) ∀i ∈ [ℓ] l res out ← GC.Eval(F, {l x ⟨i⟩ x,i } ∀i∈[ℓ] ) M ← Dec l res out (C)
Figure 2.5: Protocol to evaluate f θ,M using a garbled circuit and oblivious transfer. The protocol is parameterized by the cyclic group G of order p and generator g

In this thesis, we are interested in the function f θ,M which checks if the evaluator's input is less than θ and if so, returns a message M . We define the two functions f θ and f θ,M as follows

f θ (x) = 1 , if x ≤ θ 0 , otherwise f θ,M (x) = M , if x ≤ θ ⊥ , otherwise (2.1)
To evaluate f θ,M using a garbled circuit, the garbler G generates and sends a garbled circuit F of f θ and a label for each bit of the input. G sends F to E and then transfers the labels of x to E using OT. G also uses the output label l 1 out to encrypt the message M and send the ciphertext to E. Finally, E evaluates F on the labels of x and obtains l res out where res ∈ {0, 1}. If res = 1 the evaluator decrypts the ciphertext and obtains M . We describe the protocol in Figure 2.5. Notice, that this protocol is secure when the garbler is honest-but-curious (follows the protocol steps).

Zero-Knowledge Proofs (ZKP)

Zero-Knowledge Proof protocols are two-party protocols where a prover P interacts with a verifier V to convince it that a given statement is true while P avoids conveying any additional information apart from the fact that the statement is indeed true. We show the ideal functionality of ZKP in Figure 2.6.

Functionality F R ZK F R
ZK interacts with a prover P and a verifier V and is parameterized by the relation R.

• Upon receiving a message (sid, prove, x, w) from P , store x and w, and continue.

• Upon receiving a message (sid, verify, x ′ ) from P , abort if x ′ ̸ = x, otherwise, send (sid, R(x, w)) to V and S, and halt.

(B i = A w i ) Realization: We can realize F R n

DL

ZK as an extension of Schnorr's zero-knowledge proof for discrete logarithm [START_REF] Schnorr | Efficient identification and signatures for smart cards[END_REF]. More precisely, P samples n uniformly random values r i ←$ Z p ∀i ∈ [n] and sends {g r i } ∀i∈[n] to V . V samples the challenge c ←$ Z p and sends it to P . P computes the proof z i ← wc + r i mod Z p , and sends

{z i } ∀i∈[n] to V which finally checks ∀i∈[n] (g r i B c i = g z i )
. This protocol can be transformed into a non-interactive zero-knowledge proof using the Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

Tag Relation R Tag

Given G (a group where DDH holds) of order p, we define the tag relation R Tag (x, w) :

G 3 × Z 2 p → {0, 1} as: R Tag ({A, B, C}, (a, b)) : C = A a B b
Realization: Similarly, we can realize F RTag ZK as an extension of Schnorr's zero-knowledge proof for discrete logarithm [START_REF] Schnorr | Efficient identification and signatures for smart cards[END_REF]. More precisely, P samples two uniformly random values r 1 , r 2 ←$ Z p and sends (g r 1 +r 2 ) to V . V samples the challenge c ←$ Z p and sends it to P . P computes the proof z 1 ← ac + r 1 mod Z p and z 2 ← bc + r 2 mod Z p , then sends (z 1 , z 2 ) to V which finally checks Cg r 1 +r 2 = g z 1 g z 2 . This protocol can also be transformed into a non-interactive zero-knowledge proof using Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF].

Part I

Secure Aggregation

Chapter 3

Characterization of Secure Aggregation

In this chapter, we provide a formal definition of a secure aggregation protocol and we study the existing threat models studied in the literature: the honest-but-curious model and the malicious model. We first identify the four major technologies used to build secure aggregation solutions: differential privacy, trusted execution environment, anonymity, and cryptography. Then, we focus on solutions that are based on cryptography. We study the existing cryptography-based solutions in the honest-but-curious model and we suggest a systematic categorization of these solutions.

Environment of Secure Aggregation

One of the most important functionalities of the IoT is aggregating the data collected by the end-devices. Many IoT applications such as smart grids [START_REF] Muhammad Rizwan Asghar | Smart meter data privacy: A survey[END_REF], water management systems, and traffic control in cities use this functionality. In most of these applications, aggregating the data involves the operation of the statistical sum of the data points collected from multiple geo-dispersed data sources (eg., sensors).

Nevertheless, these individual data points usually involve sensitive data. This raises serious privacy concerns and thus calls for suitable privacy-enhancing technologies to protect the confidentiality of end-devices' data while still being able to perform the aggregation operation. During the past 20 years, a huge amount of research focused on designing secure aggregation (SA) solutions [ ÖM07, LEM14a, BSK + 19, BIK + 17, DA16, CMT05] for various applications. The goal is to enable the computation of the sum of several parties' inputs without leaking any information about each individual input except the aggregate (the sum).

In this thesis, aggregation refers to the process where data collected from multiple sources are summed up. Usually, data is collected in consecutive timestamps and the sum (aggregate) is calculated for each timestamp. For many applications, the data contains sensitive information. Usually, secure aggregation involves the following actors:

• Users (U): Parties that provide the input data x i,τ at each timestamp τ .

... • Aggregators (A): Parties that perform the aggregation to obtain the sum X τ of the input data at each timestamp τ .

• Trusted Third Party (T P): A trusted part that may be required for setup purposes in some secure aggregation protocols.

Threat Models and Security Requirements for Secure Aggregation

We describe the most popular threat models considered for secure aggregation. Namely, the honest-but-curious model and the malicious model. Then, we define the security requirements for secure aggregation.

Threat Models

Honest-but-curious Model A common security model for secure aggregation schemes is the honest-but-curious model. An honest-but-curious adversary correctly follows the protocol steps but remains curious to discover any private information. The adversary may corrupt the aggregator and some users. When the aggregator corrupts multiple parties it accesses all their private information. This models collusion between the corrupted aggregator and corrupted users.

Malicious Model

In addition to the honest-but-curious model, several research works consider a malicious model where the adversaries are more powerful. A malicious adversary may deviate from the protocol steps and thus has arbitrary inputs to the protocol. There are some variations of this model where the adversary only corrupts the aggregator (a.k.a. malicious aggregator model) or only corrupts a subset of users (a.k.a. malicious users model).

In this chapter, we only study SA solutions secure under the honest-but-curious model.

Security Requirements

We present the main two security requirements that define the security of secure aggregation protocols. The first requirement is Aggregator Obliviousness and it was initially proposed by Shi et Aggregate Unforgeability: This security notion ensures that an adversary (by corrupting the aggregator) cannot output an incorrect sum without being detected by honest users. If the adversary corrupts a small subset of users (U corr ), the notion requires that the adversary can only make an insignificant change in the result of the sum. This means that given X is the sum of the honest users' inputs, the adversary can only output a result X ′ such that X ≤ X ′ ≤ X + θ|U corr | where θ is the maximum allowed value of a user input (x i,τ < θ) .

Existing Secure Aggregation Protocols

There are mainly four types of secure aggregation (SA) protocols: SA based on differential privacy, SA based on Trusted-Execution Environment (TEE), SA based on anonymity, and SA based on cryptography. In the following, we elaborate on each type of secure aggregation.

SA based on differential privacy

Differential privacy (DP) [DR14] is a technique of adding a controlled amount of randomness (noise) to some data such that this noise is sufficient to hide sensitive information but also keeps this data useful. Hence, differential privacy provides a mathematically quantifiable way to balance data privacy and data utility. To achieve secure aggregation using DP mechanisms, users protect their trained models by adding statistical noise [MASN21, ASY + 18, TF19, YWW21, CYD20, STL20, DHCP21]. By adding some noise to the individual data points, the users preserve their privacy. The sum of the noisy data points is an inaccurate but useful result for many applications. Therefore, the main concern with this approach is the accuracy of the result since noise is amplified during the aggregation.

SA based on trusted-execution environment

Another method to perform secure aggregation is to use a TEE at the server [ZJF + 21, NMZ + 21, ZWC + 21, MHK + 21]. The TEE is a hardware-separated area of the main processor that guarantees the confidentiality and integrity of the processed data. SA can be achieved by computing the aggregation within the TEE. This method requires strong trust assumptions regarding the use of the TEE.

SA based on anonymity

A different method relies on anonymous communication assumption [START_REF] Ishai | Cryptography from anonymity[END_REF]. This method is also known as secure shuffling where users split their inputs into shares and send them anonymously to the aggregator [ZWC + 21]. Thanks to the anonymous communication, the server cannot discover the origin of the received shares and thus is unable to reconstruct the user inputs. In most applications, it is often impossible to have completely anonymous communication channels between the end-devices and the IoT platform.

SA based on cryptography

Finally, cryptographic techniques are used to design secure aggregation protocols. Many researchers are particularly interested in this type of secure aggregation since it does not significantly affect the accuracy of the aggregation result. It also does not rely on impractical assumptions such as in the case of TEE and secure shuffling which makes this choice suitable for many IoT applications.

In this thesis, we only study secure aggregation (SA) solutions based on cryptographic schemes as these seem to be the most popular ones for many applications. We believe that this is mainly due to their practical setup and the fact that they do not affect the accuracy of the results.

Secure Aggregation based on Cryptography

We first identify and investigate the three phases of secure aggregation protocol: Setup, Protection, and Aggregation. Then, we regroup secure aggregation solutions into two categories based on the underlying cryptographic tools used to build the SA protocol. Specif-ically, we distinguish encryption-based secure aggregation and multi-party-computation (MPC)-based secure aggregation. For each of the categories, we show how to build the baseline1 secure aggregation protocol from the existing cryptographic schemes by defining the algorithms executed at each SA phase. We provide some realizations of the different categories and we summarize their advantages and disadvantages in Table 3.1.

Secure Aggregation Protocol Phases

A secure aggregation protocol consists of three consecutive phases: SA.Setup, SA.Protect, and SA.Agg. Each of these phases achieves a specific task described as follows:

• SA.Setup: In this phase, the n users and the aggregator get the public parameters and the key material. The public parameters and the keys are generated either using a trusted third party (T P) or through a distributed mechanism. At the end of this phase, each user stores a single, unique key k i where i ∈ [n] and the aggregator stores its aggregation key k 0 .

• SA.Protect: Each user U i locally executes a protection algorithm to protect its input x i,τ at timestamp τ . The resulting protected input is sent to the aggregator(s).

• SA.Agg: Once the aggregators collect all the protected inputs, they collaboratively execute an aggregation algorithm to retrieve the sum of user inputs for timestamp τ .

In the case with a single aggregator, the aggregation algorithm is locally executed by the aggregator.

Encryption-based SA

Encryption-based SA protocols use encryption schemes to protect the inputs of the users. Encryption utilizes a secret key to ensure the confidentiality of the user input. To achieve Aggregator Obliviousness (see Definition 3.2.1), users should not be allowed to encrypt their inputs with the same key. Moreover, the encryption scheme should allow the computation of the sum of the inputs over the ciphertexts without leaking the individual cleartext values. There are three types of encryption schemes that are used to build a secure aggregation protocol: (i) masking, (ii) additively homomorphic encryption (AHE), and (iii) functional encryption (FE). In general, encryption-based SAs rely on a single aggregator to perform the aggregation which minimizes the communication overhead of the protocol.

Secure Aggregation using Masking

Masking is a symmetric encryption technique based on one-time pad [START_REF] Rubin | One-time pad cryptography[END_REF]. It uses modular addition to mask the data owner inputs. Given a shared key k between two parties and an upper bound R of the input, masking is defined by two algorithms:

... Layered Masking Variant In this type of masking scheme, the users are assumed to have network connectivity with each other. Hence, the users are arranged in a tree structure. In the SA.Setup phase, the ones that are at a distance of h hops from each other, share the same keys (h being a security parameter). Each user representing a node in the tree runs a secure aggregation process with its children. In SA.Protect, each child node masks its input with the sum of the keys it holds using Masking.Mask. It then sends it to its parent node. In SA.Agg, the parent sums the masked inputs received from all its children and then removes the layers of the masks that correspond to their keys using Masking.UnMask. The same process is repeated from bottom to up for each parent node until the aggregated value reaches the root of the tree at which the final layers are removed. Castelluccia et al. [START_REF] Castelluccia | Efficient aggregation of encrypted data in wireless sensor networks[END_REF] proposed a specific version of this scheme when h = ∞. Önen et al. [ ÖM07] later generalized this scheme.

DC-Net Variant

In the variant, secure aggregation is seen as a variation of the dining cryptographers problem [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF]. The solution is realized from masking as follows: In the SA.Setup phase, each pair of users (U i , U j ) agrees on a random key k (i,j),τ using a Key Agreement protocol (ex., Diffie Hellman (DH) [START_REF] Diffie | New directions in cryptography[END_REF] using the aggregator as a proxy to forward the public keys). Also, each user U i agrees on a random key k (i,0),τ with the aggregator. As a result, each user U i and the aggregator A computes their own unique key as follows:

k i,τ ← i-1 j=1 k (i,j),τ - n j=i+1 k (i,j),τ -k (i,0),τ s.t. k (i,j),τ = k (j,i),τ and k (i,i),τ = 0 ∀ i ∈ [0, .., n] (3.1)
In the SA.Protect phase, each user masks its own input x i,τ with the key k i,τ :

c i,τ ← Masking.Mask(k i,τ , x i,τ )
In the SA.Agg phase, the aggregator adds the masked inputs from all users. Then, it removes the mask using its key k 0,τ (all the operations are mod R = nR u where Z Ru is the range for the input values of each user):

Masking.UnMask(k 0,τ , n i=1 c i,τ ) = n i=1 c i,τ -k 0,τ = n i=1 (x i,τ + i-1 j=1 k (i,j),τ - n j=i+1 k (i,j),τ -k (i,0),τ ) -k 0,τ = n i=1 x i,τ + $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ X 0 n i=1 ( i-1 j=1 k (i,j),τ - n j=i+1 k (i,j),τ ) - n i=1 k (i,0),τ -k 0,τ = n i=1 x i,τ - n i=1 k (i,0),τ -(- n i=1 k (0,i),τ ) = n 1 x i,τ (3.2)
Analysis (DC-Net Variant): This scheme does not require a key dealer (KD) to distribute the masks. However, it relies on a trusted public key infrastructure (PKI). On the other hand, the masking operations are themselves very lightweight since they only include modular additions. However, the setup phase incurs significant overhead in terms of computation and communication costs per user which increases linearly with the total number of users. Since masking uses one-time pad encryption, the setup phase is performed on each timestamp τ (notice the use of the tag τ for each key). Another disadvantage is that once keys are distributed, all users should provide their protected inputs (i.e., does not support dynamic users). Indeed, if some users did not participate, the masks on the aggregated value cannot be removed. Note that masking itself is information-theoretically secure but the setup relies on a key agreement protocol that is computationally secure.

Secure Aggregation using Additively Homomorphic Encryption

A special type of Additively Homomorphic Encryption (AHE) schemes can be used for secure aggregation. Specifically, multi-user AHE is proposed such that "addition homomorphism" property is maintained across ciphertexts generated by different users with different keys. These schemes are generally defined by the three following algorithms:

• AHE.Setup(λ) → (pp, {k i } i∈[n]
, k 0 ): Given a security parameter λ, it generates the public parameters, the encryption keys, and the decryption key.

• AHE.Enc(pp, k i , τ, x i,τ ) → c i,τ : It encrypts message x i,τ for timestamp τ using key k i and outputs ciphertext c i,τ .

• AHE.Agg(pp, k 0 , τ, {c i,τ } i∈[n] ) → n 1 x i,τ : It evaluates the homomorphic operation on the n ciphertexts generated at timestamp τ . Then decrypts the resulting ciphertext using decryption key k 0 .

A multi-user AHE scheme can guarantee Aggregator Obliviousness if each user encrypts only one input per timestamp. Several instantiations are proposed in [SCR + 11, ET12, JL13, BJL16]. Multi-user AHE schemes are specifically designed for secure aggregation protocols: In the SA.Setup phase, T P runs AHE.Setup(λ) and distributes the keys to the users and the aggregator. The SA.Setup phase is executed only once; In the SA.Protect phase, U i executes AHE.Enc(pp, k i , τ, x i,τ ) and sends the ciphertext to the aggregator; Finally, in the SA.Agg phase, the aggregator executes AHE.Agg(pp, k 0 , τ, {c i,τ } i∈[n] ) and retrieves the sum of the inputs. , and the secret key of the aggregator k 0 .

• AHE.Enc(pp, k i , τ, x i,τ ) → c i,τ :

c i,τ ← g x i,τ H G (τ ) k i • AHE.Agg(pp, k 0 , τ, {c i,τ } i∈[n] ) → n 1 x i,τ : c τ ← n 1 c i,τ = g n 1 x i,τ H G (τ ) x 1 k i V ← H(τ ) k 0 c τ = g n 1 x i,τ mod n
Then, it computes the discrete logarithm base g of V to obtain n 1 x i,τ mod p. For an efficient computation of the discrete logarithm using Pollard's method [START_REF] Pollard | Monte carlo methods for index computation[END_REF], the output n 1 x i,τ should be a small number.

Theorem 3.4.1

The scheme provides Aggregator Obliviousness (see 3. , and the secret key of the aggregator k 0 .

• AHE.Enc(pp, k i , τ, x i,τ ) → c i,τ : The scheme provides Aggregator Obliviousness (see 3.2.1) security under the DCR assumption in the random oracle model if each user encrypts at most one value per timestamp.

c i,τ ← (1 + x i,τ N )H Z * N 2 (τ ) k i mod N 2 • AHE.Agg(pp, k 0 , τ, {c i,τ } i∈[n] ) → n 1 x i,τ : c τ ← n 1 c i,τ = (1 + N n 1 x i,τ )H Z * N 2 (τ ) n 1 k i mod N 2 H Z * N 2 (τ ) k 0 c τ -1 N = n 1 x i,

Proof.

For the proof of correctness and security of this scheme, refer to [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF].

Analysis:

The main advantage of AHE schemes is that they require running the setup phase only one time, and hence they are effective when aggregating a stream of data. This originally comes with the cost of relying on a trusted key dealer (KD) to perform the setup. Nevertheless, previous work has improved these schemes to enable running them without the need for a key dealer [START_REF] Leontiadis | Private and dynamic time-series data aggregation with trust relaxation[END_REF]. The per-user computational cost resulting from SA.Protect does not depend on the total number of users but remains significant.

Similarly, the communication cost per user does not depend on the total number of users but incurs a size expansion because of the size of the ciphertext. Additionally, similar to masking schemes, AHE does not support dynamic users since all users should provide their inputs to correctly aggregate them.

Secure Aggregation using Functional Encryption

Functional encryption (FE) is a type of encryption scheme that enables a user to learn a function on the encrypted data [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF]. Multi-Input Function Encryption (MIFE), introduced by Goldwasser [GGG + 14], enables the learning of a function over multiple encrypted inputs. A special type of MIFE scheme can be designed to compute the inner product function of multiple inputs [AGRW17, ACF + 18a, DOT18]. Assuming that we have two vectors x and y, each consisting of l elements, the inner product of x and y is as follows:

IP (x, y) = ℓ i=1 x i y i (3.3)
An inner product MIFE scheme is defined by four algorithms:

• MIFE.Setup(λ) → (pp, msk, {k i } i∈[n]
) : Given a security parameter λ, it generates the public parameters pp, master secret key msk, and n user keys {k i } i∈[n] .

• MIFE.Enc(pp, k i , x i,τ ) → c i,τ : It encrypts message x i,τ using key k i and outputs ciphertext c i,τ .

• MIFE.DKGen(pp, msk, y τ ) → dk τ : It generates decryption key dk τ using the master secret key and vector y τ of n elements.

• Analysis: Similar to AHE schemes, MIFE-based SA incurs constant computation and communication costs per user with respect to the total number of users. A very important property of these schemes is that they can deal with dynamic users by replacing zero weights in vector y τ for the users that do not provide input at timestamp τ . On the other hand, the disadvantage of these schemes is that they require an online key dealer (KD) as a trusted third party to generate the decryption key for each timestamp.

MPC-based SA

Another cryptographic tool used to build secure aggregation protocols is multi-party computation (MPC). In MPC, keys are not needed to protect user inputs. Instead, private messages are split into shares and distributed to multiple servers such that t of them can collaborate to reconstruct them. The secret sharing scheme presented in Section 2.3.1 can be used to construct a secure aggregation protocol.

To design a secure aggregation protocol from MPC, the SA.Setup phase is not needed since no keys are generated. In the SA.Protect phase, a user protects its input by splitting it into l random shares using SSS.Share(x i,τ , t, l, Z p ) where l is the number of aggregators and p is the first prime number such that p ≥ nR u . It then sends one unique share to each aggregator. In the SA.Agg phase, each aggregator locally sums up the shares. Because secret sharing is additively homomorphic, the sum of the shares will result in a share of the sum. Finally, at least t aggregators broadcast their shares of the sum so that any aggregator can then run SSS.Recon and retrieve the sum n 1 x i,τ .

Analysis: An important property of MPC-based SA is that it does not need a trusted third party since it does not need a key setup phase. Also, MPC supports dynamic users since it allows any subset of users to participate in the aggregation. This is mainly because MPC does not rely on secret keys that uniquely identify a user. On the contrary, MPC incurs high computation and communication costs since the protection of a user input involves creating O(nm) shares where n is the number of users and m is the size of the input. Furthermore, to distribute the shares, pre-existing secure channels are needed between the users and the aggregators. The secure channels ensure that each share is received and accessed only by its destined aggregator. In this chapter, we introduced secure aggregation protocols by defining their three phases of execution. Then, we surveyed existing solutions and presented them as instantiations of our definitions. We categorized these solutions into encryption-based solutions (Masking, AHE, FE) and MPC-based solutions and we compared their pros and cons. We found out that secure aggregation based on MPC can offer less strict setup assumptions and allow user dynamics. However, this comes at a cost of higher computation and communication costs. On the other hand, secure aggregation based on additively homomorphic encryption can perform with much better scalability in terms of the number of users. However, the latter requires a strong setup assumption where a key dealer is needed to initialize the protocol. Secure aggregation based on masking serves as a mid-way between AHE and MPC solutions. Finally, all properties can be achieved by secure aggregation based on functional encryption, but it requires a very strong assumption that the trusted key dealer should stay online during the protocol execution.

Summary of Honest-but-Curious Secure Aggregation

Schemes T P No SC Dynamic Comp. Comm. required required users Masking (DC-net) [ ÁC11, DA16] PKI O(n + m) O(n + m) AHE [LEM14a, JL13, SCR + 11] KD O(m) O(m) Encryption FE [ACF + 18b, ABM + 20, L Ţ19] KD O(m) O(m) n-out-of-n SS [BSMD10, GJ11] MPC t-out-of-n SS [Sha79] - O(nm) O(nm)
This chapter tackled the solutions in the honest-but-curious threat model only. Unfortunately, the adversary in many real-life applications is more powerful. Therefore, these schemes provide a good starting point to build solutions that can achieve stronger and more realistic threat models. In the next chapters, we focus on secure aggregation in the malicious model and we propose a new secure aggregation protocol.

Chapter 4

Secure Aggregation in the Malicious Model

In this chapter, we study secure aggregation protocols when the aggregator and a subset of the users are considered malicious. We review some of the previous work and then we propose a new verifiable secure aggregation protocol (VSA). We first formalize the security definitions of a verifiable secure aggregation which capture stronger security guarantees than previous work. Then we construct our protocol VSA that satisfies these security definitions.

Secure Aggregation with Malicious Parties

In the malicious model, the adversary controlling the aggregator and a subset of the users may deviate from the protocol steps. This model represents more realistic scenarios than the honest-but-curious model. For example, in smart grid systems, the adversary may control some of the smart meters and additionally succeed in compromising the aggregation server. In such a case, we need to guarantee that the electricity consumption of honest users remains private. Moreover, we need to guarantee that the adversary is detected if the aggregation server produces incorrect statistics about the total electricity consumption.

In general, a secure aggregation protocol in the malicious model involves some verification mechanism to ensure Aggregate Unforgeability in addition to Aggregator Obliviousness (see Definitions 3.2.1 and 3.2.2). For this purpose, we propose a formal definition for verifiable secure aggregation protocols which capture both the privacy and verifiability of the protocol. Moreover, we present in this chapter the first verifiable secure aggregation protocol (VSA) that meets our definition. Secure Aggregation against Malicious Aggregator All the solutions in the malicious aggregator model share the idea of using tags created by the users to authenticate the sum of the inputs. More precisely, the user sends a tag along with its protected input. Then, the aggregator adds all the tags to produce a final tag that proves the correctness of the sum. There are mainly two types of tags proposed in the literature:

Previous Work

• Hash-based tags: In DEVA [TLB + 21] and VERSA [START_REF] Hahn | Versa: Verifiable secure aggregation for cross-device federated learning[END_REF], the authors use homomorphic hashes [START_REF] Yao | Homomorphic hash and blockchain based authentication key exchange protocol for strangers[END_REF][START_REF] Krohn | On-the-fly verification of rateless erasure codes for efficient content distribution[END_REF] as tags. The problem with the hash approach is that the tags a need to be authenticated and saved on a public bulletin board. The public verifier later aggregates the hashes and verifies the sum. This approach leads to a linear increase in the size of the tags with respect to the number of users.

• Signature-based tags: In PUDA [LE ÖM15], the authors modify the SCRCS secure aggregation scheme (see Section 3.4.2.2) to provide a verification mechanism of the aggregate. PUDA users generates homomorphic tags based on a homomorphic signature scheme. The homomorphic signature scheme is an extension of the signature scheme in [START_REF] Mandell | Improved security for linearly homomorphic signatures: A generic framework[END_REF] to the multi-user setting. The advantage of PUDA over hash-based tags is the succinctness of the aggregated tag (i.e., constant size with respect to the number of users). We present PUDA scheme in details in Section 4.4.1 since it is one of the building blocks for VSA.

The problem with these solutions is that they do not consider the case where one or more users are corrupted. In such a case, the adversary who controls both the aggregator and one user can forge a tag for any arbitrary value. Therefore, these solutions are limited to a few applications.

Secure Aggregation against Malicious Users Another type of secure aggregation protocols target applications where the user is not trusted. In these protocols, the user produces a tag that proves to the aggregator that the input is within a valid range. To generate these tags, Karakoç et al. propose KOB [START_REF] Karakoç | Secure aggregation against malicious users[END_REF] which uses an Oblivious Programable Pseudo-Random Function (OPPRF) protocol. The protocol runs between the user which provides its input and the aggregator which provides an upper-bound value. If the user input is less than the upper bound chosen by the aggregator, the user receives a valid tag of its input. They build their OPPRF using an OT protocol. More specifically, the user and the aggregator perform a secure comparison of their inputs using ℓ OT executions (ℓ is the bit-size of the input). In each run, the aggregator sends a masked part of the tag. After executing all the OTs, the user can reconstruct the tag and unmask it if its input is less than the aggregator's upper bound. This solution ensures that a malicious user cannot provide out-of-bound input and thus limits their influence on the sum of all users' inputs. Unfortunately, in this solution, the aggregator is trusted to perform the check on the user inputs. Additionally, in the case of a malicious aggregator, this solution cannot ensure privacy. Indeed, the malicious aggregator can compute an arbitrary function of the user input instead of computing the tag. Therefore, this secure aggregation solution is insecure when the aggregator is controlled by the adversary.

Secure Aggregation against both Malicious Users and Aggregator

There is only one solution that studies this extreme case where both the aggregator and the users are malicious. Guo et al. propose a solution [GLL + 21] that considers the case where the aggregator is malicious and it colludes with a subset of the user. However, the authors assume that the users provide correct inputs. In their solution, the users commit to their inputs using a homomorphic commitment scheme [START_REF] Pryds | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF] and send the commitments to all the other users before the aggregation process starts. After the users receive the commitments, they send their protected inputs to the aggregator. This solution does not prevent the adversary from providing bad inputs and changing the sum. Instead, it only guarantees that the adversary can influence the aggregation result before knowing the actual sum of the honest users. Hence, this solution does not provide strong security guarantees. Therefore, we identify the need for a strong definition of security for secure aggregation in the case of malicious parties as a missing requirement.

VSA -Overview

We aim to build a verifiable secure aggregation protocol that ensures both Aggregator Obliviousness and Aggregate Unforgeability in the malicious model. Thus, we propose to extend PUDA [LE ÖM15] (which is secure in the malicious aggregator model) to achieve security when both the aggregator and a subset of users are malicious. The main problem with PUDA is that users are trusted in generating tags for their inputs. Thus, a malicious user can produce tags for any input and thus compromise the sum while still having a valid tag. Alternatively, KOB protocol [START_REF] Karakoç | Secure aggregation against malicious users[END_REF] allows the aggregator to generate the tags instead of the user after privately checking the correctness of the user inputs. However, this approach requires the aggregator to be trusted. Therefore, our idea is to involve additional parties in the protocol called taggers. The purpose of the taggers is to generate user tags. More precisely, each user runs a tagging protocol with the taggers. If the user input is less than the upper bound set by each tagger, the user receives a PUDA-like tag. Then, the user continues as in PUDA protocol but instead of generating its own tag, it uses the tag computed by the taggers. The aggregator receives the protected input and the tag of each user and finally outputs the sum and its corresponding tag. In our protocol VSA, the final tag ensures both, that the users provided well-formed inputs, and that the aggregator correctly computed the sum.

One challenge in building VSA is building a secure and robust tagging protocol that even when some taggers (less than a threshold) are malicious, the tag can still be produced. To build this protocol we use threshold secret sharing to share the tagging keys among the taggers. Each tagger computes a partial tag using the key share. The user robustly aggregates the partial tags under the assumption that there is a sufficient number of honest taggers.

One more challenge to deal with is how each tagger privately checks that the user input is in the correct range. KOB proposes an OPPRF approach for this purpose. However, this solution is only secure when the tagger is honest-but-curious since it allows the tagger to compute any function of the user input instead of computing the tag. To solve this problem, we design our tagging protocol using zero-knowledge proofs to ensure correct behavior of the tagger.

Leontiadis et al. presented PUDA [LE ÖM15

] as a model for aggregating inputs from n users using a single aggregator. We describe this model and its properties. Then, we present the construction proposed by the authors.

PUDA model

The PUDA model involves n users, one aggregator, and a trusted key dealer. It consists of the five following algorithms:

• PUDA.Setup(1 λ ): An interactive randomized algorithm which on the input of security parameter λ, generates public parameters pp, an encryption and tagging key (ek i , tk i ) for user U i , an aggregator key ak, and a public verification key vk.

• PUDA.Enc(ek i , x i , τ ) → c i : It encrypts the private value x i using key ek i for timestamp τ .

• PUDA.Tag(tk i , x i , τ ) → σ i : It generates a tag for private value x i using tagging key tk i for timestamp τ .

• PUDA.Agg(ak,

{c i } ∀i∈[n] , {σ i } ∀i∈[n] , τ ) → (X τ , Υ τ ):
It aggregates the ciphertext and the tags of all users for timestamp τ using the aggregation key ak. It outputs the sum X τ and the corresponding tag Υ τ .

• PUDA.Verify(vk, X τ , Υ τ , τ ) → {0, 1}: It uses the verification key vk to verify the tag Υ τ of the sum X τ for timestamp τ .

The authors define security using the two notions of Aggregator Obliviousness and Aggregate Unforgeability (see Section 3.2). They propose a formal definition of these notions using security games AO PUDA and AU PUDA respectively1 .

PUDA construction

PUDA construction is based on SCRCS secure aggregation scheme (see Section 3.4.2.2). It is described as follows:

• PUDA.Setup(1 λ ):
-The trusted key dealer generates the public parameters: It selects the groups G 1 , G 2 , and G T (where DDH holds) of prime order p; the generators g 1 ∈ G 1 and g 2 ∈ G 2 ; a bilinear map e : {G 1 , G 2 } → G T ; and a hash function

H G1 (see Section 2.4.3). It gives pp = (g 1 , g 2 , G 1 , G 2 , G T , e, H G1
) to all users and the aggregator.

-The key dealer generates a uniformly random encryption key per user ek i ←$ Z p . It sets the aggregation key ak = -∀i∈[n] ek i . It gives ek i for each user and ak to the aggregator.

-The key dealer generates a uniformly random key a and sends it to all the users. Then, each user generates a uniformly random key b i ←$ Z p and forwards g b i 2

to the key dealer. The user sets tk i = (a, b i ) as its tagging key.

-The key dealer computes vk 1 = g a 2 and

vk 2 = n 1 g b i 2 = g n 1 b i 2
and then sets the verification key as vk = (vk 1 , vk 2 )

• PUDA.Enc(ek i , x i , τ ):
The user encrypts x i for timestamp τ as follows:

c i ← (g x i 1 )H G1 (τ ) ek i • PUDA.Tag(tk i , x i , τ ):
The user parses tk i =(a, b i ) and generates a tag of x i for timestamp τ as follows:

σ i ← (g a 1 ) x i H G1 (τ ) b i • PUDA.Agg(ak, {c i } ∀i∈[n] , {σ i } ∀i∈[n] , τ ):
The aggregator aggregates the ciphertexts and the tags from each user:

V τ ← ( i∈[n] c i )H G1 (τ ) ak = g Xτ 1 Υτ ← i∈[n] σ i = (g a 1 ) Xτ H G1 (τ ) i∈[n] b i It then finds X τ = i∈[n]
x i by computing the discrete logarithm of V τ .

• PUDA.Verify(vk, X τ , Υ τ , τ ):

e(Υ τ , g 2 ) ? = e(H G1 (τ ), vk 1 )e(g Xτ 1 , vk 2 )

VSA -Formal Definitions

In this section, we present the VSA model and its security properties. VSA is composed of n users U = {U 1 , ..., U n }, m taggers T = {T 1 , ..., T m }, and one aggregator A. The users generate inputs at each timestamp τ . The taggers are parties that compute the tag of a user's inputs at a given timestamp. Finally, the aggregator is the party that produces the sum of all inputs and its corresponding authenticating tag for a given timestamp.

VSA is composed of the following PPT algorithms:

• VSA.Setup(1 λ , t): An interactive randomized algorithm which on input of security parameter λ and threshold t ≤ m, generates the public parameters pp, an encryption key ek i for user U i , an aggregator key ak, a list of n tagging keys TK j = {tk 1,j , ..., tk n,j } (one key per user) for each tagger T j , and a public verification key vk.

• VSA.Enc(ek i , x i , τ ) → c i : It encrypts the private value x i using key ek i for timestamp τ .

• VSA.Tag({tk i,j } j∈J i , {θ j } j∈J i , x i , τ ) → σ i : An interactive randomized algorithm which takes an input x i , a higher bound on the inputs θ, a subset of tagging keys {tk i,j } j∈J i , and a timestamp τ . It outputs a tag σ i .

• VSA.Agg(ak, {c i } ∀i∈[n] , {σ i } ∀i∈[n] , τ ) → (X τ , Υ τ ):
It aggregates the ciphertext and the tags of all users for timestamp τ using the aggregation key ak. It outputs the sum X τ and a tag Υ τ .

• VSA.Verify(vk, X τ , Υ τ , τ ) → {0, 1}: It uses the verification key vk to verify the tag Υ τ of the sum X τ for timestamp τ .

The main difference between VSA model and PUDA model is due to the additional parties called taggers. Moreover, each user's tagging key is distributed to the m taggers and not to the users. Consequently, the tagging algorithm becomes an interactive protocol between the user and the taggers to produce the tag of the user's input.

Correctness of VSA

We require that when all users provide inputs that are less than all the bounds set by the participating taggers, and when the number of taggers that participate in producing the tag of each user is higher than a threshold t, the verification algorithm outputs 1 with an overwhelming probability. More formally: ∀λ, ∀t, ∀J i , ∀x i , and

∀θ j s.t. i ∈ [n], j ∈ J i , J i ⊂ [m], |J i | ≥ t, and x i ≤ θ j , Pr     VSA.Verify(vk, X τ , Υ τ ) = 0 VSA.Setup(1 λ ) → (pp, {ek i }, {tk i,j }, ak, vk), VSA.Enc(ek i , x i , τ ) → c i,τ ∀i ∈ [n], VSA.Tag({tk i,j } j∈J i , {θ j } j∈J i , x i , τ ) → σ i,τ ∀i ∈ [n], VSA.Agg(ak, {c i } i∈[n] , {σ i } i∈[n] , τ ) → (X τ , Υ τ )     ≤ µ(λ)
where µ is a negligible function.

Security of VSA

We consider that the adversary controls the aggregator A, a set of taggers T corr ⊂ T , and a set of users U corr ⊂ U. We present the oracle O EncTag that we use to define the security games. Throughout the games, we consider that the minimal upper bound value

θ min = min({θ j } ∀j∈[m]
) is known to the adversary. .

• O EncTag : When queried with a user identifier i, input x, and timestamp τ , the oracle first checks if i and τ are queried before. If so, it aborts. The oracle computes c i and σ i as VSA.Enc(ek i , x, τ ) and VSA.Tag({tk i,j } ∀j∈[m] , {θ min , ..., θ min }, x, τ ) respectively. Then, if U i / ∈ U corr , it outputs the result (c i , σ i ), otherwise it outputs (σ i ).

Aggregator Obliviousness (AO) We give a formal definition of AO using a security game.

Our game is an improved version of AO PUDA game from PUDA [LE ÖM15] that captures (in addition to the static corruption of the aggregator and some users) the corruptions of some taggers. The game proceeds in three phases:

Setup and Corruption Phase: The adversary A chooses the security parameter λ and the threshold t ≤ m and accordingly gets the public parameters of the protocol pp, the aggregator's key ak, the verification key vk, the secret keys of the parties in U corr (i.e., {ek i } ∀U i ∈Ucorr ), and the secret keys of the parties in T corr (i.e., {TK j } ∀T j ∈Tcorr ).

Learning Phase: The adversary A interacts with oracle O EncTag in polynomial times by sending tuples (i, x, τ ) such that for every user identifier i, if U i / ∈ U corr , then x ≤ θ.

Challenge Phase:

The adversary A chooses a timestamp τ * that has never been queried, and a set of non-corrupted users U * (i.e., U * ∩ U corr = ϕ). It chooses two lists X 0 τ * and X1 τ * each corresponds to the inputs for each user in U * at τ * . It queries the oracle O AO with these lists which is defined as follows:

• O AO : The oracle is called with the a set of users U * ⊂ U \ U corr and two list of inputs (i,

x 0 i , τ ) ∀U i ∈U * and (i, x 1 i , τ ) ∀U i ∈U * such that ∀U i ∈U * x 0 i = ∀U i ∈U * x 1 i .
It flips a coin b ∈ {0, 1} and returns the ciphertexts and tags of the input (i,

x b i , τ ) ∀U i ∈U * .
After receiving the ciphertexts {c b i } ∀U i ∈U * and their corresponding tags {σ b i } ∀U i ∈U * , A submits a guess bit b * and wins the game if b * = b.

Game 1 Aggregator Obliviousness (AO)

The Learning Phase: /* A queries the oracle poly-number of times for any i, x, and τ s.t. U i / ∈ Ucorr and x≤θ */

(c i , σ i ) ← O EncTag(i,x,τ )
/* A queries the oracle poly-number of times for any i, x, and τ s.t.

U i ∈ Ucorr*/ (σ i ) ← O EncTag(i,x,τ )
The Challenge Phase:

A → τ * , U * ⊂ U \ U corr A → X 0 τ * , X 1 τ * {(c b i , σ b i )} ∀Ui∈U * ← O AO(X 0 τ * ,X 1 τ * ) A → b * ∈ {0, 1} Definition

Aggregate Unforgeability (AU)

We give a formal definition of AU using a security game. Our game is an improved version of AU PUDA game that captures (in addition to the static corruption of the aggregator) the corruptions of some users and taggers.

Similar to the previous definition (i.e., AO) the game proceeds in three phases. The Setup and Corruption Phase and Learning Phase are the same as in AO game. In the Challenge Phase A submits a tuple (τ * , sum τ * , Υ τ * ).

Game 2 Aggregate Unforgeability (AU)

The Learning Phase: /* A queries the oracle poly-number of times for any i, x, and τ s.t. U i / ∈ Ucorr and x≤θ */

(c i , σ i ) ← O EncTag(i,x,τ )
/* A queries the oracle poly-number of times for any i, x, and τ s.t.

U i ∈ Ucorr*/ (σ i ) ← O EncTag(i,x,τ )
The Challenge Phase:

A → (τ * , sum τ * , Υ τ * )
The adversary wins the game if it succeeds in forging a valid tag of a sum. In [LE ÖM15], the authors define two types of forgeries. We reconsider these types and add a new type.

• Type I Forgery: VSA.Verify(vk, sum τ * , Υ τ * ) = 1 and the adversary A never made a previous query with timestamp τ * .

• Type II Forgery: VSA.Verify(vk, sum τ * , Υ τ * ) = 1 and A already made queries with timestamp τ * , however the sum sum τ * ̸ = ∀U i ∈U x i,τ * .

•

Ideal Functionality for Distributed Tagging Protocol

In this section, we present the ideal functionality F t,G DTAG for the distributed tagging protocol Π t,G DTAG ≡ VSA.Tag. The protocol runs between the user and the m taggers. The user provides an input x and each tagger provides a share of the tagging key k and a bound θ j . The protocol outputs a tag computed by PUDA.Tag(k, x, τ ) if x is less than all the bounds of the honest taggers. Otherwise, it gets no output. Figure 4.2 shows the functionality F t,G DTAG .

VSA -Construction in the Ft,G DTAG -Hybrid Model

In this section, we first present our VSA protocol. Then, we prove its correctness and that it achieves the security properties defined in Section 4.5. We describe the protocol in the hybrid model of the functionalities F D,n CRS (Section 2.4.2), F t,G DTAG (Section 4.6), and F t,n,F RShare (Section 2.4.4). Figure 4.3 illustrates a single run of the protocol.

VSA Scheme

Let Λ be a sampling algorithm that returns a uniformly random tuple of the form (g 1 , g 2 , p, G 1 , G 2 , G T , e, H G1 ) where G 1 , G 2 , and G T are groups where DDH holds of prime order p; g 1 is a generator of G 1 ; g 2 is generator of G 2 ; e : {G 1 , G 2 } → G T is a bilinear map; and H G1 is a hash function as defined in Section 2.4.3.

Functionality F t,G DTAG F t,G
DTAG runs between user U and m taggers T = {T 1 , ..., T m } and is parameterized by the reconstruction threshold t ≤ m of the SSS scheme. Let T h ⊂ T be the set of honest taggers such that |T h | ≥ t. Auxiliary Inputs: The bit size ℓ of the user's input x and the tagger's bound θ j . A function PUDA.Tag :

Z 2 p × [2 ℓ ] -× {0, 1} * → G
where G is a cyclic group of order p.

• Upon receiving a message (sid, input, x) from U where x ∈ [2 ℓ ] -, store x. Then, send message (sid, input, U ) to S.

• Upon receiving a message (sid, input, ⟨tk⟩ j , θ j ) from T j where ⟨tk⟩ j =(⟨a⟩ j , ⟨b⟩ j ) ∈ Z 2 p and θ j ∈ [2 ℓ ] -, store ⟨tk⟩ j and θ j . Then, send message (sid, input, T j ) to S and continue. • VSA.Setup(1 λ , t):

-Distributing the public parameters:

The m taggers, the aggregator, and the n users query F Λ,m+n+1

CRS

and receives the public parameters pp = (g 1 , g 2 , p, G 1 , G 2 , G T , e, H G1 ).

-Distributing the encryption and aggregation keys:

Each tagger T j uniformly samples ek i,j ←$ Z p per user (i.e. ∀U i ∈ U), and computes ak j = -∀U i ∈U ek i,j . It sends to each user U i ∈ U the key ek i,j and to the aggregator ak j . Each user computes its encryption key ek i = j∈[n] ek i,j and the aggregator computes the aggregation key ak = j∈[n] ak j .

-Distributing the tagging keys:

Each tagger T j queries F t,m,Zp
RShare n + 1 times and receives the share ⟨a⟩ j and the n shares

⟨b i ⟩ j for each i ∈ [n]. It sets tagging keys tk i,j = (⟨a⟩ j , ⟨b i ⟩ j ) ∀i ∈ [n].
The tagger key is TK j = {tk 1,j , ..., tk n,j }.

-Distributing the verification keys: • VSA.Enc(ek i , x i , τ ) ≡ PUDA.Enc(ek i , x i , τ )

Each tagger T j publishes vk 1,j = g ⟨a⟩ j 2 and vk 2,j = g i∈[n] ⟨b i ⟩ j 2 . Each tag- ger then computes SSS.ExpRecon([m], {vk 1,j } ∀j∈[m] , G 2 ) → vk 1 = g a 2 and SSS.ExpRecon([m], {vk 2,j } ∀j∈[m] , G 2 ) → vk 2 = g i∈[n] b i
• VSA.Tag({tk i,j } j∈J i , {θ j } j∈J i , x i , τ ):
The user U i (with input x i ) and each tagger T j (with input (tk i,j , θ j )) query Ft,G 1 DTAG . The user receives the output σ τ from Ft,G 1 DTAG .

• VSA.Agg(ak,

{c i } ∀i∈[n] , {σ i } ∀i∈[n] , τ ) ≡ PUDA.Agg(ak, {c i } ∀i∈[n] , {σ i } ∀i∈[n] , τ ) • VSA.Verify(vk, X τ , Υ τ , τ ) ≡ PUDA.Verify(vk, X τ , Υ τ , τ )

Proof of Correctness

The correctness of our construction directly follows from the correctness of PUDA protocol. To prove this argument, observe that ∀λ, ∀t, such that VSA.Setup(1 λ , t) and PUDA.Setup(1 λ ), the following holds:

• ∀x i , the ciphertexts produced by PUDA and VSA schemes are statistically indistinguishable since VSA.Enc ≡ PUDA.Enc.

• ∀J i , ∀x i , ∀θ j s.t. (J i ⊂ [m]) ∧ (|J i | ≥ t) ∧ (x i ≤ θ j )
, the tags produced by PUDA and VSA schemes are statistically indistinguishable. This holds because VSA outputs the result of Ft,G 1 DTAG which produces tags computed with PUDA.Tag algorithm if x i is less than the minimum bound and a sufficient number of taggers participate.

• The aggregation and verification algorithms are equivalent: VSA.Agg ≡ PUDA.Agg and VSA.Verify ≡ PUDA.Verify.

VSA -Security Analysis

We now perform a security analysis of the scheme. To prove that our VSA scheme achieves Aggregator Obliviousness and Aggregate Unforgeability, we first take a step to show that both our AO game and AU game can be reduced to AO PUDA game and AU PUDA game.

Lemma

′ i ←$ Z p for each i ∈ [n]. Then it computes SSS.Share(a ′ , t, m, Z p ) and SSS.Share(b ′ i , t, m, Z p ) for each i ∈ [n]. It sets TK j = {(⟨a ′ ⟩ j , ⟨b ′ 1 ⟩ j ), ..., (⟨a ′ ⟩ j , ⟨b ′ n ⟩ j )}
for each corrupted T j ∈ T corr . B gives A the public parameters pp, the verification key of PUDA vk, the aggregation key ak, the corrupted users' encryption keys {ek i } ∀U i ∈Ucorr , and the randomly generated list of shares TK j of the corrupted taggers.

During the Learning Phase: When A queries O EncTag , B returns the values from

History if the user identifier and timestamp were previously queried. Otherwise,

• If U i ̸ ∈ U corr : it queries O PUDA EncTag with (i, x, τ ) and gets (c u,τ , σ u,τ ), saves it to History and sends σ i to A.

• If U i ∈ U corr and x ≤ θ min : B computes PUDA.Tag(tk i , x, τ ) → σ i , saves σ i
to History and sends it to A.

• If U i ∈ U corr and x > θ min it sets σ i ←⊥ saves σ i to History and sends it to A.

During the

= {(⟨a ′ ⟩ j , ⟨b ′ 1 ⟩ j ), .
.., (⟨a ′ ⟩ j , ⟨b ′ n ⟩ j )} for each corrupted T j ∈ T corr . B gives A the public parameters pp, the verification key of PUDA vk, the aggregation key ak, the randomly generated encryption keys of the corrupted users {rk i } ∀U i ∈Ucorr , and the randomly generated list of shares TK j of the corrupted taggers. B maintains a list History of the queried ciphertexts and tags.

2. During the Learning Phase: When A queries O EncTag , B returns the values from History if the user identifier and timestamp where previously queried. Otherwise,

• If x ≤ θ min : B queries O PUDA EncTag with (i, x, τ ) and gets (c i , σ i ). B computes c ′ i ← VSA.Enc(rk i , x, τ ), saves (c ′ i , σ i )
to History and sends it to A.

• If x > θ min : B computes c ′ i ← VSA.Enc(rk i , x, τ ), saves (c ′ i , ⊥)
to History and sends it to A. In this reduction, the differences between A's simulated view (by B) and A's real view (when it plays the real game) are: (i) the encryption keys of the corrupted users, (ii) the tagging keys' shares of the corrupted taggers, and (iii) the ciphertexts received from the oracles. The tagging keys' shares are statistically indistinguishable in both views as shown in the previous proof. Similarly, the encryption keys are chosen uniformly randomly as if they were generated by the setup algorithm. It remains to show that the ciphertexts received from the oracles are indistinguishable in both views. In both views, the ciphertexts are generated by randomly generated encryption keys.

Additionally, they both satisfy the relation i∈

[n] c i = (g i∈[n] x i 1 )H(τ ) -
τ * )= 1 is P r[A AU III ]
. Now observe that to have ∀U i ∈Ucorr x i,τ * > |U corr |θ min there exists at least one x i,τ * > θ min . Let U ′ corr ̸ =ϕ be the set of users that their user identifiers were queried with x i,τ * > θ min . Observe that VSA.Tag returns ⊥ when run with input x > θ min . Therefore, the oracle O EncTag returns σ i =⊥ (no output) for all queries (i, x, τ * ) where

U i ∈ U ′ corr . Let sum ′ τ * = ∀U i ∈U \U ′ corr x i,τ * + ∀U i ∈U ′ corr x ′ i,τ * such that sum τ * ̸ = sum ′ τ * and x ′ i,τ * > θ min ∀U i ∈ U ′ corr .
The oracle O EncTag returns the same result (i.e., ⊥) for both queries (i, x i,τ * , τ * ) and (i,

x ′ i,τ * , τ * ) ∀U i ∈ U ′ corr . Thus, we can deduce that P r[VSA.Verify(vk, sum τ * , Υ τ * ) = 1] ≃ P r[VSA.Verify(vk, sum ′ τ * , Υ τ * ) = 1]. There- fore, P r[A AU III ] = P r[A AU II ]
. By relying on Corollary 4.8.3, we conclude that our scheme ensures aggregate unforgeability against Type III Forgery under the LEOM assumption in the random oracle model and F t,G 1 DTAG -hybrid model.

Realization of Distributed Tagging Protocol

In this section, we show how to build the protocol Π

| < m -t (eg., for t = m 2 , it is sufficient to choose |T corr | < m 2 ).
Proof.

To prove the theorem we build a simulator S that runs in the ideal world and interacts with F t,G DTAG and Z. It simulates for the adversary A the interaction with the noncorrupted parties and Z. We consider three different cases depending on which parties A corrupts. In each case, S runs internally an instance of A. It simulates the interaction with Z by forwarding the messages sent from Z to A and vice-versa. It simulates the interaction with the protocol parties based on a well-defined strategy described in what follows.

Case 1: A corrupts U Observe that U only interacts with FG TAG . Thus, S simply forwards the messages between A and FG TAG and vice-versa. Hence, the simulated execution of A and the real one are identical. Additionally, the honest parties do not get any output. Therefore, we proved that Π t,G DTAG UC-realizes the functionality

F t,G DTAG in the F G TAG -hybrid model if A corrupts only U .
Case 2: A corrupts T corr ⊂ T Observe that each T j ∈ T corr sends a message to FG TAG only and receives nothing. So S simply forwards the message from A to FG TAG . Hence, the simulated execution of A and the real one are identical. We only need to show that the

Functionality F G TAG F G
TAG runs between user U and a tagger T and is parameterized by the function f and the reconstruction threshold of the SSS scheme t ≤ m. Auxiliary Inputs: The bit size ℓ of the user's input x and the tagger's bound θ j . A function PUDA.Tag :

Z 2 p × [2 ℓ ] -× {0, 1} * → G
where G is a cyclic group of order p.

• Upon receiving a message (sid, input, x) from U where x ∈ [2 ℓ ] -, store x. Then, if the T is corrupted, send message (sid, input, U ) to S and receive the message (sid, ok, η) where η : [2 ℓ ] -→ {0, 1}. If η(x) = 0 abort, otherwise, continue.

• Upon receiving a message (sid, input, k, θ) from T where k ∈ Z 2 p and θ ∈ [2 ℓ ] -, store k and θ. Then, if U is corrupted send message (sid, input, T ) to S.

-If S sends (sid, abort), send abort to all parties and abort.

-If S sends (sid, ok), continue.

• When (sid, input) is received from U and all T i , compute σ ← PUDA.Tag(k, x, sid a ).

If no, set σ ←⊥. Send (sid, output, σ) to U and halt.

a The session id (sid) is the same as the timestamp (sid=τ )

Protocol Π t,G DTAG Π t,G
DTAG runs between user U and m taggers T = {T 1 , ..., T m } and is parameterized by the reconstruction threshold of the SSS scheme t ≤ m. Inputs: User's input x ∈ [2 ℓ ] -and tagger T j input ⟨tk⟩ j =(⟨a⟩ j , ⟨b⟩ j ),

θ j ∈ Z 2 p × [2 ℓ ] -.
• User U initializes an empty set Ω then interacts with each tagger T j as follows:

-U sends (sid, ssid, input, x) to FG TAG . -T j sends (sid, ssid, input, ⟨tk⟩ j , θ j ) to FG TAG . -U receives (sid, ssid, output, σ j ) from FG TAG (or the sub-session ssid aborts). If σ j ̸ =⊥, add (j, σ j ) to the set Ω. output of the honest parties (the user since it is the only party that gets an output) is identical in both worlds. In the real world, the user outputs

• ∀J k ⊂ Ω s.t. |J k | = t, U computes SSS.ReconExp({(j, σ j )} ∀(j,σ j )∈J k , G) → σ ′ k . The user outputs σ ← majority({σ ′ k } ∀k∈[( t n )] ).
σ REAL ← majority({σ ′ k } ∀k∈[( t n )] ) where σ ′ k ← SSS.ReconExp({(j, σ j )} ∀(j,σ j )∈J k , G).
In the ideal world, the user outputs σ IDEAL ← PUDA.Tag(tk, x, sid) where tk ← (a, b) such that a ← SSS.Recon({(j, ⟨a⟩ j )} ∀j|T j ∈T h , Z p ) and b ← SSS.Recon({(j, ⟨b⟩ j )} ∀j|T j ∈T h , Z p ). Thus, we need to show that σ IDEAL = σ REAL .

Notice that T h = T \ T corr . Thus, for |T corr | < m -t, we have |T h | > t and thus σ IDEAL = (g x 1 ) a H(τ ) b where g 1 , H(τ ) ∈ G. In the real world, σ j = (g x 1 ) ⟨a⟩ j H(τ ) ⟨b⟩ j ∀T j ∈ T h . So, we have for each

σ ′ k ← SSS.ReconExp({(j, σ j )} ∀(j,σ j )∈J k , G), where J k ⊂ T h , σ ′ k = (g x 1 ) a H(τ ) b = σ IDEAL (from Lemma 2.3.2). Since |T h | > t, then t |T h | > 1.
Hence, the number of σ ′ k 's that are equal to σ IDEAL are more than one. On the other hand, since

|T corr | < t, for each J k , we have P r[σ ′ k 1 = σ ′ k 2 ̸ = σ IDEAL ] ≃ 0 (from Definition 2.3.2). Therefore, P r[majority({σ ′ k } ∀k∈[( t n )] ) ̸ = σ IDEAL ] ≃ 0.
This proves that σ IDEAL = σ REAL and consequently we proved Π t,G DTAG UC-realizes the functionality

F t,G DTAG in the F G TAG -hybrid model if A corrupts T corr ⊂ T and |T corr | < t and |T corr | < m -t.
Case 3: A corrupts U and T corr ⊂ T Similar to the previous two cases, S will forward messages between A and FG TAG . Hence, the simulated execution of A and the real one are identical. Additionally, the honest parties do not get any output. Therefore, we proved that Π

Realization of The Tagging Protocol

The ideal functionality of the protocol Π G TAG (depicted in Figure 4.5) computes the tag PUDA.Tag(k = (a, b), x, τ ) = (g a ) x H(τ ) b if the user input x is less than a bound θ chosen by the tagger.

For illustration purposes, we first present a version of the protocol that is secure in the honest-but-curious (HBC) model (the user and the tagger follow the protocol steps). Next, we present our Π G TAG protocol and prove that it UC-realizes F G TAG in the malicious model.

Tagging Protocol in the HBC model

The user generates a uniformly random value r ←$ Z p and computes P =(g x ) r and Q=H(τ ) r then send P and Q to the tagger. The tagger computes E=P a Q b . Notice that the user now can obtain the tag from E by computing σ = E 1 r . To prevent the user from obtaining the tag σ if its input x > θ, the tagger does not send E to the user. Instead, it runs a garbled circuit protocol as described in Section 2.4.6 with the function f θ,E :

f θ,E (x) = E , if x ≤ θ ⊥ , otherwise
This protocol is only secure in the HBC model since a malicious user may compute the tag on a value x > θ, then evaluate the garbled circuit on a different value x ′ ≤ θ. On the other hand, a malicious tagger may garble any arbitrary function f ′ and thus influence the protocol to output f ′ (x) instead of σ.

Tagging Protocol Π G TAG in the malicious model To correctly realize the protocol Π G TAG in the malicious model, we need the tagger to ensure that the tag is evaluated on the same input used to evaluate the garbled circuit. Additionally, we need the user to ensure that the garbled circuit is evaluating a tag of data point x.

To solve the first issue, we propose to modify the OT protocol used in the garbled circuit protocol. The goal is to use the messages sent by the user in the OT protocol to evaluate the tag σ directly. By reusing these messages, we make sure that the tag is computed on the same input used to evaluate the circuit.

To solve the second issue, we use a zero-knowledge proof of knowledge of language R Tag (see Section 2.4.7) to verify the result of the protocol. The details of the protocol are described in Figure 4.7.

Proof.

To prove the theorem we build a simulator S that runs in the ideal world and interacts with F G TAG and Z. It simulates for the adversary A the interaction with the noncorrupted parties and Z. We consider two different cases depending on what parties A corrupts. In each case, S runs internally an instance of A. It simulates the interaction with Z by forwarding the messages sent from Z to A and vice-versa. It simulates the interaction with the protocol parties based on a well-defined strategy described in what follows.

x,i }, l b out ← GC.Grb(1 λ , f θ ) ∀i ∈ [ℓ]
, ∀b ∈ {0, 1} and samples value α, γ ←$ Z p uniformly at random. It sends the message (sid,γ, A = g α , F ) to A and waits for A ′ s response. 3. When A sends the message (sid,prove,({(

Tagging Protocol Π G TAG User (x = x 1 ||...||x ℓ ) Tagger θ, k=(a, b) F, {l b x,i }, l b out ← Grb(1 λ , f θ ) ∀i ∈ [ℓ], ∀b ∈ {0, 1} γ, A = g α , F α ←$ Z p , γ ←$ Z p r ←$ Z p , β ←$ Z p | γ=rβ β i ←$ Z p ∀i ∈ [ℓ] | β= ℓ 1 (β i ×2 i-1 ) B i ← A x ⟨i⟩ g βi ∀i ∈ [ℓ] κ i ← G G (A,Bi) (A βi ) ∀i ∈ [ℓ] P i ← B r i ∀i ∈ [ℓ] Q ← H(τ ) r {B i , P i } ∀i∈[ℓ] , Q {(B i , P i )} i∈[ℓ] , (H(τ ), Q) witness = r F R ℓ+1 DL ZK {(B i , P i )} i∈[ℓ] , (H(τ ), Q) True κ 0 i ← G G (A,Bi) (B α i ) ∀i ∈ [ℓ] κ 1 i ← G G (A,Bi) (( B i A ) α ) ∀i ∈ [ℓ] c 0 i ← Enc * κ 0 i (l 0 x,i ) ∀i ∈ [ℓ] c 1 i ← Enc * κ 1 i (l 1 x,i ) ∀i ∈ [ℓ] P ← (g -γ ℓ 1 (P i ) 2 i-1 ) 1 α E ← P a Q b C ← Enc * l 1 out (E) {(c 0 i , c 1 i } ∀i∈[ℓ] , C l x ⟨i⟩ x,i ← Dec κi (c x ⟨i⟩ i ) ∀i ∈ [ℓ] l res out ← Eval(F, {l x ⟨i⟩ x,i } ∀i∈[ℓ] ) E ← Dec l res out (C) (g xr , Q, E) F R Tag ZK (P, Q, E) witness = (a, b) True return σ ← E 1 r
B ′ i , P ′ i )} i∈[ℓ] , (H ′ , Q ′ )), r) to F R ℓ+1 DL ZK . S checks if H ′ =H(sid), Q ′ =Q, B i =B ′
i , and

P i =P ′ i ∀i ∈ [ℓ]
, and the relation R ℓ+1

DL hold, and send (sid, abort) to F G TAG if any of the checks fail. If the values are valid and the relation R ℓ+1

DL holds, then S sets β = γ r and checks if

ℓ 1 (B i ) 2 i-1 = (g α ) x g β . If this equality does not hold, this means A chose β i such that ( n 1 β i ×2 i-1 ) ̸ = β.
In this case, S sets the value bad_input = 1 and continues.

4. S sends the message (sid, input, x) to F G TAG and receives (sid, output, σ). S computes:

• κ 0 i ← G G (A,B i ) (B α i ) ∀i ∈ [ℓ], • κ 1 i ← G G (A,B i ) (( B i A ) α ) ∀i ∈ [ℓ] • c 0 i ← Enc * κ 0 i (l 0 x,i ) ∀i ∈ [ℓ] • c 1 i ← Enc * κ 1 i (l 1 x,i ) ∀i ∈ [ℓ]
Then, S computes:

• if σ =⊥, samples ε ←$ {0, 1} λ and E ←$ G then computes C ← Enc * ε (E). • if σ ̸ =⊥ and bad_input = 0, sets E = σ r then computes C ← Enc * l 1 out (E). • if σ ̸ =⊥ and bad_input = 1 sets E ←$ G then computes C ← Enc * l 1 out (E).
S finally sends (sid,{(c 0 i , c 1 i } ∀i∈[ℓ] , C) to A. In this simulation, the difference between the simulated execution of A and the real one is in the generated garbled circuit F and in the ciphertext C. We argue that both values are indistinguishable between the real world and the ideal world.

(Proceed to this step only if

σ ̸ =⊥). When A sends (sid,(P ′ , Q ′ , E ′ )) to F RTag ZK , if P ′ =g rx , Q ′ =Q,
Indistinguishability of the simulated garbled circuit F : The simulated garbled circuit is garbled from the function f θIDEAL where θ IDEAL = 2 ℓ -1. The only difference is in the value of θ. However, the security of the garbled circuit scheme (see [START_REF] Andrew | How to generate and exchange secrets[END_REF]) guarantees computational indistinguishablity between these two circuits.

Indistinguishability of the simulated ciphertext C: There are three different cases in our simulation: Case (i) when σ =⊥: This means that A's input x is greater than θ REAL (input of the honest tagger). In this case, the adversary in the real world will not be able to decrypt the value of C since it will not obtain l 1 out from the evaluation of the garbled circuit (A will obtain l 0 out since x ̸ ≤ θ REAL ). Hence the ciphertext C in the ideal world which is encrypted by a random key ε is computationally indistinguishable from C in the real world based on the security property of the encryption scheme (see Definition 2.3.5 and Definition 2.3.7).

Case (ii) when σ ̸ =⊥ and bad_input = 0: In the ideal world, the value of C is the encryption of σ r with l 1 out where σ is the output of F G TAG and r is the randomness chosen by A (extracted from the F R ℓ+1 DL ZK message). In the real world, the value of C is the encryption of E with l 1

out where E = P a Q b . We have

P = (g -γ ℓ 1 (P i ) 2 i-1 ) 1 α = g rαx+rβ-γ α
= g rx (since γ = rβ when bad_input = 0). Additionally, Q = H(τ ) r , so we have E = (g rx ) a H(τ ) rb = σ r . Hence, the values of C are identical from both worlds.

Case (iii): σ ̸ =⊥ and bad_input = 1: In the ideal world, the value of C is the encryption of E IDEAL with l 1

out where E IDEAL is chosen uniformly random in G. In the real world, the value of C is the encryption of E REAL with l 1 out where E REAL = P a Q b . We have P = (g -γ ℓ 1 (P i ) 2 i-1 )

1 α = g rαx+rβ-γ α ̸ = g rx (since γ ̸ = rβ when bad_input = 1). So we have E REAL = (g rαx+rβ-γ α
) a H(τ ) rb . Notice that Z does not know α which is chosen uniformly random in Z p . We can write the value of E REAL = g c 1 +c 2 α -1 H(τ ) c 3 where c 1 = arx, c 2 = b(rβ -γ) ̸ = 0 (since rβ ̸ = γ), and c 3 = rb are three values chosen by Z. Let us assume that Z can distinguish E REAL from E IDEAL with a non-negligible probability given only g, g α ∈ G and τ ∈ {0, 1} * . We show that we can solve the Inv-DDH problem (i.e., given the tuple (g, g X , g Z ) tell of g Z = g X -1 ) using Z. For a tuple (g, g X , g Z ) query Z with (g, g α =g X ,E REAL = g c 1 (g Z ) c 2 H(τ ) c 3 ). Hence, the values of C are computationally indistinguishable from both worlds under the Inv-DDH assumption.

This proves that Π

, P ′ i )} i∈[ℓ] , (H ′ , Q ′ ))) to F R ℓ+1 DL ZK . If H ′ =H(sid), Q ′ =Q, B i =B ′
i , and

P i =P ′ i ∀i ∈ [ℓ]
, and the relation R ℓ+1 DL holds, S sends (sid,True) to A, otherwise send (sid,False) to A and (sid, abort) to F G TAG .

3. When A sends the message (sid,{(c 0 i , c 1 i } ∀i∈[ℓ] , C), S starts internally S snd (defined in Lemma 2.4.2) and handles the OT sender's message A = g α ,(c 0 i , c 1 i ), and the random oracle G G queries to S snd . S snd extracts the sender's input (l 0

x,i , l 1 x,i ) and sends it out to S. S repeats the process for every i ∈ [ℓ]. Hence, S extracts all the input labels of the garbled circuit {l b

x,i } ∀i∈[ℓ],b∈{0,1} . Then, S evaluates the garbled circuit F on all possible values of x ∈ [2 ℓ ] -using the labels and uses the output label to decrypt C and obtain E. If this operation fails for any x, S sets η(x)=0, otherwise η(x)=1. S finally sends (sid, ok, η) to F G TAG .

4. When A sends (sid,(( In this simulation, the difference between the simulated execution of A and the real one is only in the choice of the input x = 1. As a result, the only messages that are different are B i and P i , ∀i ∈ [ℓ]. Recall that B i is the OT message defined in the OT protocol in Section 2.4.5. By relying on the UC proof of [START_REF] Hauck | Efficient and universally composable protocols for oblivious transfer from the cdh assumption[END_REF] (when simulating the corrupted sender), we can show that B i are computationally indistinguishable from both views under the CDH problem. The indistinguishability of P i follows directly since P i = B r i , and r is chosen uniformly random in Z p . This proves that Π G TAG UC-realizes the functionality F G TAG in the F R ZK -hybrid model if A statically corrupts T under the CDH assumption.

P ′ , Q ′ , E ′ ), (a, b)) to F RTag ZK , If P ′ ̸ =P , Q ′ ̸ =Q,
We finally deduce that, IDEAL F G TAG ,S,Z s ≈ EXEC Π G TAG ,A,Z under static corruption and under the Inv-DDH assumption which proves our theorem.

Conclusion on Verifiable SA

In conclusion, we proposed a new formal definition for verifiable secure aggregation protocol. Our new definition captures the privacy of the user inputs and the verifiability of the aggregation result in the malicious model. Moreover, we presented VSA protocol and proved that it satisfies these security guarantees. VSA improves PUDA protocol which originally provides a verification mechanism against a malicious aggregator. VSA extends it by generating the PUDA tags using a distributed tagging protocol. Our distributed tagging protocol runs between a user and m taggers. It guarantees that an honest user receives a valid tag of its input and that a malicious user receives nothing. Thanks to this tagging protocol, VSA guarantees that an adversary controlling the aggregator and few users cannot compromise the aggregation result.

Part II

Secure Aggregation for Federated Learning

Chapter 5

Privacy-Preserving Federated Learning with Secure Aggregation

In this chapter, we study federated learning, one of the recent technologies used in IoT platforms. We specifically discuss its limitations in terms of privacy and we propose to improve its security using secure aggregation. For this purpose, we study all existing solutions that integrate secure aggregation within federated learning and we regroup them based on the specific challenge they tackle. We finally derive some takeaway messages that would help for a secure design of federated learning protocol and identify research directions in this topic.

Introduction to Privacy-Preserving Federated Learning

With the recent advancements in information technologies, machine learning techniques take a substantial part of data processing. Machine learning is a set of techniques that uses real data (e.g., measurements) to improve the accuracy and performance of existing systems [START_REF] Tom | Machine learning[END_REF]. These techniques aim to develop the so-called machine learning models by learning to perform some well-specified tasks. This operation is known as training machine learning models on collected data. As a consequence, data becomes the most important resource for such systems to achieve better accuracy.

In the case of IoT platforms, machine learning is an essential technique to improve their business targets. IoT platforms collect data from IoT devices and process them using machine learning techniques. Lately, these IoT platforms started to collaborate with each other to train better machine learning models. However, they cannot simply share their collected data due to privacy reasons. Thus, federated learning technology emerged as a privacy-preserving technique to train on private datasets from multiple sources.

The The main goal of FL is to protect the privacy of the local data while still being able to use them for training public models. This technology provides a great advantage over other techniques that try to achieve the same goal (eg., training on encrypted data [VNP + 20, HTGW18, WGC19, DGBL + 16, WTB + 20]). The latter adds a large computational overhead since it involves encryption of the inputs then performing complex computations on encrypted data. FL requires less computation as it only involves the averaging operation at the server.

While FL is proposed for privacy-protection purposes, it lacks a formal guarantee of privacy. For example, adversaries who have access to the training results sent from each client to the server might be able to infer a training sample from a client's private dataset. Many types of inference attacks on FL are investigated and researched in [MSDCS19, ZLH19, LHCH20, NSH19]. One of the solutions to mitigate these inference attacks is secure aggregation. In this chapter, we study the use of secure aggregation to perform the averaging operation in federated learning. To better understand the integration of secure aggregation in federated learning, we study the specific requirements and characteristics of federated learning compared to the legacy application of secure aggregation. Additionally, we survey all 37 existing solutions that propose to do this integration and we regroup them based on the specific challenge they tackle. As a result, we identify the limitations and gaps in the literature and present them as a set of take-aways.

Characteristics of Federated Learning

Federated learning has a wide range of use cases and applications. These applications differ based on the scale of federation, the partitioning of the training data, and the learning algorithm used in training.

Scale of Federation

Two types of FL exists with respect to the scale of federation: Cross-silo FL and cross-device FL [KMA + 19].

• Cross-silo Scenarios (X-Silo): A small number of powerful users host the data.

These often have decent computational power with a reliable and high bandwidth network connection.

• Cross-device Scenarios (X-Device): It involves a large number of users. These users often correspond to end-devices with moderate computational power. In many applications, these devices directly interact with end-users from which they collect data.

Partitioning of the training data

There exist three categories of data partitioning [YLCT19, LWH19, DP21]: Horizontal partitioning, vertical partitioning, and hybrid partitioning.

• Horizontal Partitioning: Each FL client holds a set of complete training samples.

Each sample contains all the training features and the corresponding label. Hence, each client can train a local model on these samples.

• Vertical Partitioning: A client may hold part of the features of each training sample while the other parts might be held by other FL clients. In this FL type, the clients are not able to locally train a model without collecting the missing information of each sample from other clients.

• Hybrid Partitioning: A hybrid partitioned dataset is a combination of horizontally and vertically partitioned datasets.

Secure aggregation is only suitable to FL based on horizontally partitioned datasets since those based on vertically partitioned datasets require more operations than just summing the clients' updates. In this thesis, we only consider horizontally partitioned datasets since it is the most realistic case in real-life applications.

Learning algorithm

The most used learning algorithm for horizontal FL is Federated Averaging [MMR + 17], which is based on Stochastic Gradient Descent (SGD) [iA93]. SGD is an iterative algorithm used to train a model on a dataset (i.e., find the best weights of a model that can fit the dataset). At each SGD step, client i uses model M τ and a loss function f to compute gradient g τ i from the values in its dataset D i :

g τ i = ∆f (M τ , D i ) = ∆ (x,y)∈D i f (M τ , x, y)
Then, the gradient is used to update the weights of the model with learning rate η

(M τ i = M τ -ηg τ i ).
The FL clients send their new trained model M τ i to the FL server who aggregates them:

M τ +1 ← n 1 M τ i n
Finally, each FL client obtains the aggregated model M τ +1 and starts a new federated learning round.

Privacy of the Datasets in Federated Learning

An adversary having access to the model update M τ i sent by client i can perform inference attacks. These attacks allow an attacker to retrieve some private information about the client's datasets. Based on the type of private information, there exist three categories of inference attacks:

• Membership Inference Attacks [SSSS17a, NSH19]: The attackers learn whether a specific data record is part of the training dataset or not.

• Reconstruction Attacks [DN03,WLW + 09]: The attacker learns some of the attributes of a record in the dataset. These attacks are also known as model invasion attacks [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF].

• Data Properties Inference Attacks [AMS + 15, GWY + 18]: The attacker learns global properties of the training dataset, such as the environment in which the data was produced.

All these attacks show that federated learning is not sufficient to preserve data privacy when used alone. To mitigate these attacks, it is crucial to protect the model updates sent by the federated learning clients while still being able to compute their aggregate. Table 5.1: Challenges in using secure aggregation for FL based on the specific requirements of FL. It shows for each challenge whether the baseline SA protocols defined in Chapter 3 can originally cope with that challenge.

Existing Secure Aggregation for Privacy-Preserving Federated Learning

Federated learning features some unique properties and characteristics that differ from previous applications where secure aggregation was used. This makes integrating secure aggregation schemes to federating learning a challenging task. We hereby identify seven unique properties for FL that raise significant challenges for the integration of secure aggregation in FL. We further analyze the suitability of each secure aggregation category (see Chapter 3) to cope with these characteristics. We summarize the results in Table 5.1.

Failures and Drops of Clients at Realtime (C 1 )

In cross-device FL scenarios, it is common to have mobile, unreliable FL clients. The mobility of a client may cause failures (drops) of some FL clients causing their unavailability for some federated learning rounds. Failures of clients may even happen within the FL round as well. All this can be a problem for some secure aggregation schemes that do not support dynamic users. In particular, SA schemes based on masking and AHE are not fundamentally designed to cope with user failures. Therefore, the need for fault-tolerant secure aggregation is a requirement for FL.

Client's Inputs are Vectors of High Dimension (C 2 ) In FL, the user's input is a vector that holds all the model parameters (weights). Not all types of secure aggregation protocols can efficiently work with vectors. For example, MPC-based SA incurs a significant communication overhead since the shares of the inputs have the same size of the input. Therefore, it is not practical to run secret sharing to share large vectors. Also, in masking-based SA, the users should run a key-agreement protocol to compute new masks for each FL round. This adds significant overhead. Additionally, for AHE, the encryption algorithm results in large ciphertexts. Thus, encrypting each element in the input vector adds a large overhead. This calls for efficient packing techniques designed for AHE-based SA. Unlike other methods, for FE-based secure aggregation, it is possible to construct a solution where each party sends exactly one value of the size of the input vector (see the SA scheme construction presented in Section 3.4.2.3 in Chapter 3).

Client's Inputs are of Floating Point Type (C 3 ) All the baseline secure aggregation protocols are designed to operate on integer types. In FL, the user's input usually is of floating point (float) type. This calls for efficient quantization techniques that transform floats to integers while preserving a high accuracy in the result. Representing floats with integers incurs an increase in the size of the input. Hence, the use of quantization techniques helps achieve a good trade-off between accuracy and communication overhead.

Huge Number of Clients (C 4 ) Recently, we start to observe FL applications involving thousands of FL clients. Google is researching how to train Gboard (the Android's keyboard application) search suggestion system using federated learning on large scale [YAE + 18, HKR + 18]. With secure aggregation integrated with federated learning, the scalability problem becomes a serious challenge. MPC-based SA protocols do not scale well with huge number of users since they suffer from a quadratic complexity in terms of communication and computation. Similarly, masking-based SA suffers from a quadratic complexity in the setup phase. Additionally, with a large number of clients, the typical synchronized FL protocol is not practical. In an asynchronous FL protocol, clients do not wait for the updates of a sufficient number of users at each FL round. Instead, the updates of the users are incorporated as soon as they arrive at the server. Adopting SA for asynchronous FL is challenging because updates may be protected with keys corresponding to different FL rounds.

Privacy Attacks that Bypass SA (C 5 ) The aggregated model M τ +1 is a public information that is accessible for all FL clients. Therefore, secure aggregation is not used to hide this value. There exists a different type of inference attacks that can still infer private information from the aggregated model, only [START_REF] Shokri | Membership inference attacks against machine learning models[END_REF]. For example, recently So et al. [SAG + 21] pointed out a new attack to leak the client's updates even when protected with secure aggregation. The authors notice that the models from the FL clients do not change a lot between one training step and another one when the trained model starts to converge. This causes a privacy leakage if a FL client did not participate. In more details, if all FL clients participate in round τ -1 and all clients except one participate in round τ , and if the inputs did not change a lot, an adversary who has access to the aggregated model updates for rounds τ and τ -1 will be able to approximate the inputs of the missing FL client. Such specific attacks can bypass the security measures of SA. Gao et al. [GHG + 21] implemented these types of attacks and show how they can effectively infer the category of the given data samples.

Secure aggregation protocols by definition do not provide protection against these types of attacks. Therefore, additional security mechanisms should be used with secure aggregation to mitigate these attacks.

Malicious Users (C 6 ) Earlier SA protocols proposed before the FL paradigm appeared, mainly consider a honest-but-curious threat model with colluding users (see Section 3.2 in Chapter 3). Such a threat model is not sufficient in the context of federated learning. Specifically, FL clients cannot be trusted to provide their inputs truthfully at each FL round. Thus, we should consider an extended threat model which considers malicious users.

Indeed, poisoning attacks (a.k.a., backdooring attacks) are attacks where malicious FL clients manipulate their model updates M τ i to affect the aggregated model M τ +1 . Their goal is to install a backdoor in the trained model. A "backdoored" model behaves almost normally on all inputs except for some attacker-chosen inputs at which it outputs attacker-desired predictions. Malicious FL clients use two main methods to poison a model: Dataset poisoning [START_REF] Shen | Auror: Defending against poisoning attacks in collaborative deep learning systems[END_REF] where attackers insert malicious records in their dataset; and model poisoning [BVH + 20a] (a.k.a., constrain-and-scale attacks) where the attacker replaces the trained model by a malicious model and send it instead of the trained model. An even more recent attack method consists of distributed poisoning attacks [START_REF] Xie | Dba: Distributed backdoor attacks against federated learning[END_REF] in which the poison is distributed among several malicious clients inputs so that it is harder to detect malicious models. On the other hand, malicious clients can perform less stealthy attacks by sending ill-formed inputs to prevent the calculation of the aggregation. To further prevent all these types of attacks we need to implement additional security mechanisms for SA.

Malicious Aggregator (C 7 ) Similar to challenge C 6 , the honest-but-curious threat model is not sufficient to prevent the cheating of a server in the context of federated learning. More specifically, the SA protocols described in Section 3 prevent a curious FL server from learning the clients inputs, but cannot protect against a malicious server that modifies the aggregated model. Indeed a malicious server can cause a huge damage because it has full control of the final aggregated value. Therefore, an adversary controlling the FL server can force the clients to receive an adversary chosen model. In fact, the impact of a malicious aggregator can even go beyond forging the aggregation result. Pasquini et al. [START_REF] Pasquini | Eluding secure aggregation in federated learning via model inconsistency[END_REF] showed that a malicious aggregator can even compromise the privacy by bypassing the secure aggregation protocol. An example for these attacks illustrated by the authors is when the malicious aggregator chooses specific values for the aggregated result. The values are chosen such that when the clients train the forged model sent by the aggregator, the training outputs a model of zero parameters. Hence, the malicious aggregator can suppress arbitrary clients of his choice from the aggregation by sending them malformed models. Therefore, it can suppress all clients except a targeted one and leak its input. To prevent such attacks, SA protocols should consider a malicious aggregator in their threat model.

Secure Aggregation Solutions for Federated Learning

A lot of research has been conducted on designing secure aggregation protocols based on cryptographic schemes for federated learning applications. Most of the proposed schemes are improvements of the basic secure aggregation protocols described in Chapter 3 and tackle one or more of the aforementioned challenges (C 1 -C 7 ). The proposed schemes can be categorized based on the challenge they tackle. We summarize how these solutions propose different solutions for each of the challenges. Table 5.2 presents an overview of these solutions grouped by their challenge scope. Also, Figure 5.3 regroups them per SA MIFE-based SA also are fault-tolerant by design since the data aggregator can assign zero weights for missing clients [XBZ + 19]. However, these schemes require a key dealer to stay online for each federated learning round.

On the other hand, Bonawitz et al. [BIK + 17] propose a fault-tolerant variant of the masking-based SA. Later, this scheme is widely adopted and improved by [BBG + 20, EA20, SGA21b, KLS21, XLL + 20, GLL + 21]. The idea of this scheme is to merge Shamir's SS scheme with masking. More specifically, it benefits from the lightweight operations and low communication overhead of the masking scheme and on the other hand, the solution inherits the fault-tolerance property of Shamir's SS scheme. Thanks to this trade-off, it is considered a big jump towards designing practical secure aggregation scheme for cross-device FL scenarios. A similar scheme is proposed by Stevens et + 20]. Batch encryption allows encrypting of multiple values in a single operation and thus optimizing the encryption of vector inputs (representing machine learning models). In BatchCrypt [ZLX + 20], the authors propose a method to quantize and batch the elements of a model before encryption. The strength of their approach is that it preserves the additively homomorphic property of the ciphertexts. Another interesting technique presented by Wu et al. [WPX + 20] is to use the All Or Nothing Transformation (AONT) [START_REF] Ronald | All-or-nothing encryption and the package transform[END_REF]. AONT is a technique for transforming data into a different form such that, the new data can only be understood if all of it is known. The authors show that by transforming clients' models with AONT, it is sufficient to encrypt a small part of the transformed model. Thanks to AONT property, the non-encrypted part of the transformed model does not give any useful information as long as the other part of it is encrypted. This can decrease the size of the protected user input by several orders.

For masking-based SA, Bonawitz et al. [BIK + 17] propose to execute a key agreement protocol to produce small random numbers that are used as seeds of a pseudo-random generator. These seeds are then used to generate the masks. + 17] does not require that all the clients are connected. Thus, they propose to generalize the scheme by creating random graphs. Each FL client executes the FT-Masking with its neighbors. The new protocol assumes that not all the neighbors will be corrupted at the same time and it proposes a method to build the so-called "good" graphs.

Accurate Secure Aggregation

Similarly, both So et al. (TurboAgg) [SGA21b] and Sandholm et al. (SAFE) [SMH21]

propose a circular topology. Clients perform a chain of aggregations by passing the aggregated updates to the next client. To further deal with a large number of clients, So et al. [START_REF] So | Secure aggregation for buffered asynchronous federated learning[END_REF] propose a SA protocol that can be integrated into asynchronous FL. The solution uses the scheme proposed in [YSH + 21] and adapts it to enable secure aggregation of inputs from different timestamps.

Secure Aggregation Resilient to Privacy Attack

To deal with inference attacks on the aggregated model (C 5 ), Differential Privacy (DP) solutions [START_REF] Dwork | Differential privacy. In Automa, Languages and Programming[END_REF] should be used with secure aggregation. Notice that the goal of using DP mechanism with SA is to protect the aggregated model, only, and not user inputs.

A simple method is to let the aggregator apply DP mechanism on the aggregated model [START_REF] Delgado Fernández | Secure federated learning for residential short term load forecasting[END_REF]. However, this requires trusting the aggregator. A better method is to use a distributed version of DP (DDP) along with SA to mitigate the information leakage caused by the public aggregated model. Few works have followed this approach for FL [KLS21, TBA + 19]. These solutions add Gaussian noise to the FL clients' inputs. They leverage the fact that FL clients' inputs are protected with cryptographic tools (thanks to SA) which permit them to decrease the level of noise while achieving sufficient privacy level. Therefore, using DDP with SA limits the degradation of the accuracy of the trained model compared to using DP alone. Stevens et al. [SSV + 21] follow a similar approach by using Learning with Error (LWE) masking technique to make the final aggregate differentially private.

On the other hand, a multi-round privacy concept is introduced by So et al. [SAG + 21]. This concept is to ensure that an adversary cannot learn valuable information by monitoring the changes in the aggregated model across different FL rounds. The authors propose a solution enlightened by the work in [TNW + 21]. They propose to randomly and fairly (using weights) select participants in each FL round based on well-defined criteria called Batch Partitioning. Using this technique they can guarantee the long-term privacy of the data at the FL clients.

Secure Aggregation Against Malicious Users

To deal with malicious users who perform poisoning attacks (C 6 ), the FL server needs a mechanism to validate the inputs of the clients. Mitigating poisoning attacks is studied by researchers independently from using secure aggregation for FL [START_REF] Fung | Mitigating sybils in federated learning poisoning[END_REF][START_REF] Andreina | Baffle: Backdoor detection via feedback-based federated learning[END_REF]. One of the methods used to prevent such attacks is to use the cosine distance [START_REF] Fung | Mitigating sybils in federated learning poisoning[END_REF] to detect poisoned inputs that deviate from the other benign inputs. Clustering [STS16, BEMGS17] and anomaly detection methods [START_REF] Andreina | Baffle: Backdoor detection via feedback-based federated learning[END_REF] are also used to detect malicious model updates. An orthogonal approach is to use clipping and noising to smooth the model updates and remove the differences [BVH + 20b]. While all these solutions are shown to be efficient in preventing poisoning attacks, using them with secure aggregation is a big challenge. The problem is that all these solutions rely on analyzing the FL clients' inputs while secure aggregation aims to hide and protect these inputs. Several methods are proposed to verify the inputs while keeping them protected to preserve their privacy.

For MPC-based SA, it is possible to build circuits that can perform complex operations on the shares. This can be used to evaluate functions on the inputs other than just computing the sum. Indeed, MLGuard [START_REF] Khazbak | Mlguard: Mitigating poisoning attacks in privacy preserving distributed collaborative learning[END_REF] proposes to verify the users' inputs by transforming a verification function into a circuit that gets executed by the two servers using 2PC. The verification function computes the distance between the clients' inputs. The circuit compares the distance to pre-defined thresholds and thus rejects the input if it exceeds it. FLGuard [NRY + 21] follows the same approach by building two circuits: One circuit for detecting poisoned inputs using a dynamic clustering algorithm (HDBSCAN [START_REF] Ricardo | Densitybased clustering based on hierarchical density estimates[END_REF]) and another circuit for reducing the impact of poisoned inputs using clipping and noising. The communication cost of running these circuits is significant thus making scalability even harder to achieve for SA in the federated learning context. A promising approach to reduce this cost is through the use of secret-sharing noninteractive proof (SNIP). This approach was proposed in [CGB17] (Prio). Using SNIP enables the aggregators to validate the user inputs without interacting with the users and with minimal interaction between themselves. This scheme is not yet deployed in FL applications. SNIP brings a great advantage over standard 2-PC validation circuits since it does not limit the number of aggregators thanks to its lower communication cost. The limitation of SNIP is that it only supports specific validation functions. Therefore, it is an open challenge to design validation circuits for detecting poisoning attacks using SNIP.

On the other hand, regarding AHE-based SA, Karakoc et al. [START_REF] Karakoç | Secure aggregation against malicious users[END_REF] propose OPPRF, an algorithm based on private set membership (PSM) [START_REF] Ciampi | Combining private set-intersection with secure two-party computation[END_REF] and oblivious transfer (OT) [START_REF] Naor | Computationally secure oblivious transfer[END_REF]. OPPRF uses PSM to perform equality checks between values (i.e., equivalent to finding an intersection between sets of cardinality equal to one [START_REF] Couteau | New protocols for secure equality test and comparison[END_REF]). Using OPPRF, the users can create tags that are only valid if their inputs are lower than a threshold provided by the aggregator. Karakoc et al. [START_REF] Karakoç | Secure aggregation against malicious users[END_REF] applied this scheme for AHE-based SA schemes and evaluated it in FL applications. The scheme enables the FL server to detect poisoning attacks by checking that the minimum, maximum and average of the model elements do not cross a certain threshold value. The threshold is configured based on an observation of the models of benign clients. Another approach is proposed by Lukas et al. [BLV + 21]. The authors use a non-interactive commitment scheme proposed in [START_REF] Pryds | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF]. Using this scheme, the users create proofs that the Euclidean distance of their inputs satisfies the bound set by the aggregator. Upon receiving the client's protected input and the commitment, the server verifies that the proof is valid.

For masking-based SA, two techniques are proposed. One technique is proposed by So et al. [START_REF] So | Byzantine-resilient secure federated learning[END_REF] in which users secretly share their model updates with all other clients and then compute the squared distance between the model shares. The server can finally reconstruct the squared distances and use the result to detect malicious inputs. An alternative technique is proposed by Zhang et al. [START_REF] Zhang | Safelearning: Enable backdoor detectability in federated learning with secure aggregation[END_REF] and Velicheti et al. [START_REF] Velicheti | Secure byzantinerobust distributed learning via clustering[END_REF]. In more detail, users are anonymously and randomly grouped into clusters. Aggregation happens per cluster and then a following round of aggregation happens on the results of each cluster. For each cluster, the intermediate aggregation results are checked to prevent poisoning attacks. The fact that attackers do not know to which cluster the compromised device belongs to, protects from distributed poisoning attacks (see C 6 ).

Secure Aggregation Against Malicious Aggregator

In a malicious aggregator threat model, the FL server forges false aggregation results (C 7 ). Mitigating these attacks requires a verifiable secure aggregation scheme. Many solutions are proposed to enable the verification of the aggregation outcome [KShS12, SS11, DOS18, CDE + 18]. However, these solutions do not fit well in federated learning applications due to their high communication overhead. In the context of federated learning, six solutions are proposed [GLL + 21, HKKH21, XLL + 20, ZFW + 20, TLB + 21, BTL + + 20] use Homomorphic Hash Functions (HHF) to verify the result of the aggregation. HHF can be built using bilinear maps [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF][START_REF] Mandell | Improved security for linearly homomorphic signatures: A generic framework[END_REF]. First, the data owners create authentication tags for their inputs and send them to the aggregator. The latter aggregate them to prove the outcome of the aggregation. Finally, the aggregator verifies the result. Hahn et al. [START_REF] Hahn | Versa: Verifiable secure aggregation for cross-device federated learning[END_REF] detect possible brute-force attacks on VerifyNet and improve it by deploying a keyed HHF. All these solutions do not prevent collusions between the users and the aggregator. Therefore, they cannot be considered secure based on our security definitions for secure aggregation in Chapter 3). Another problem with these solutions is that they significantly affect the performance of SA. This is because of the linear increase in computation and communication overhead with the increase of the dimension of inputs. This is a clear limitation since the performance of the ML model highly depends on its size (i.e., number of parameters). To solve this problem, Guo et al. (VeriFL) [GLL + 21] focus on designing a verification scheme specifically for secure aggregation applications with inputs of high dimension. To support user-aggregator collusions, the authors integrated a commitment scheme to prevent users from changing their hashes after the computation of the aggregate. The authors of VeriFL apply this scheme to the fault-tolerant masking scheme in [BIK + 17]. The evaluation of their solution on federated learning applications shows a significant reduction in communication overhead with respect to other verification schemes. However, VeriFL still suffers from a quadratic computation and communication cost with respect to the number of FL clients. Achieving better scalability for verification systems is an open problem.

For MPC-based SA, Brunetta et al. [BTL + 21] propose NIVA as a non-interactive secure aggregation protocol that includes the verification of the result. The users create a tag for each of their input shares. Upon computing the aggregate, the result can be verified using all the generated tags. Tsaloli et al. [TLB + 21] propose DEVA which improves the number of tags created for each user. DEVA requires that a user creates a single tag for its input rather than creating a tag for each share. Both approaches do not support collusions between users and the aggregator and incur very high communication overhead since they use MPC.

Observations and Conclusion on Secure Aggregation for FL

We have extensively studied federated learning solutions that integrate secure aggregation schemes. In this section, we identify and share the following observations and takeaway messages: O 2 We notice that secure aggregation solutions based on AHE are not widely adopted in federated learning. This is mainly because they do not support user dynamics. However, we see that AHE-based SA is promising since they provide long-term security using the same user keys. We hope to see more research improving these schemes towards a practical deployment in federated learning context.

O 3 We notice that some of the solutions proposed to preserve the privacy in federated learning do not adhere to the minimal security requirements for secure aggregation protocols (see Definition 3.2.1 for Aggregator Obliviousness). Specifically, AHE schemes [PAH + 18, LCV19, ZLX + 20, ZFW + 20] and masking-based verification schemes [ZFW + 20, XLL + 20, HKKH21] that use the same key for all users should not be considered secure since they do not guarantee security in case of a collusion between a user and the aggregator.

O 4 We note that secure aggregation alone is insufficient to guarantee the privacy of the clients' datasets in the context of federated learning. Although SA helps prevent inference attacks, the global model that is collaboratively computed from private individual inputs can still leak information. Therefore, additional protection mechanisms are required. Differentially private mechanisms and multi-round privacy solutions are suitable candidates to cope with this problem.

O 5 Poisoning attacks against federated learning call for some integrity mechanisms that would allow the aggregator (the FL server in this context) to verify the correctness/veracity of received inputs. Nevertheless, the cost of such mechanisms can be significant. Therefore, we can consider the design of such mechanisms that can (i) detect stealthy and sophisticated poisoning attacks, and (ii) ensure the security and scalability requirements, as an open challenge.

O 6 Similar to the previous observation, we identify the need for an integrity mechanism for verifying the correctness of the actual aggregate. Basic solutions would linearly increase the size of the transmitted data between parties w.r.t. the model size. Using incremental HHF is promising as shown in VeriFL [GLL + 21]. However, this solution is still far from being applied for FL applications in larger scale since it still implies a linear increase in communication and computation cost w.r.t the number of clients.

Based on all the previous observations, we propose revisiting the definition of cryptobased secure aggregation to make it suitable for FL. Specifically, we revise the description of the protocol phases (i.e., SA.Setup, SA.Protect, and SA.Agg) to meet all the security requirements for FL applications. Following observation O 4 , the SA.Protect phase should be modified such that users first pre-process their inputs with distributed DP mechanisms before running the actual protection algorithm. Additionally, based on observation O 5 , SA.Protect should also generate integrity proofs of inputs which are sent together with the protected inputs to the data aggregators. On the other hand, SA.Agg should include a verification mechanism of the inputs which validates the integrity proofs. Moreover, observation O 6 indicates that SA.Agg should compute a proof of the aggregation which is sent to the users along with the aggregation result. In order for the users to validate the aggregation result, we require an additional phase: Namely, the SA.Verify phase should be performed as a final step by the users. In this phase, the users verify the received result of the aggregation.

Summary In summary, we propose a better definition of secure aggregation protocols based on cryptographic schemes which cope with the security requirements of federated learning. The definition consists of four phases: SA.Setup, SA.Protect, SA.Agg, and SA.Verify. Figure 5. [START_REF] Mansouri | Verifiable Secure aggregation in The Malicious Model[END_REF] shows the details of the improvements in each of the phases. It is worth noting that this new definition combines and generalizes all the improvements proposed by the state-of-the-art solutions. It would be interesting to develop the first SA solution for FL implementing our proposed definition by combining all the state-of-the-art techniques.

Chapter 6

Scalable and Fault-Tolerant Secure Aggregation for Federated Learning

In the previous chapter, we have identified and enumerated the main challenges of integrating secure aggregation schemes in federated learning (FL) protocol. In this chapter, we tackle one of these challenges, namely, failures and drops of FL clients in realtime. We first provide an extensive study of the existing solutions against such failures. We further propose a novel fault-tolerant secure aggregation solution for federated learning (FTSA) that is the first one based on additively homomorphic encryption.

Fault-Tolerant Secure Aggregation

Consider a scenario where hundreds of companies manage IoT platforms and would like to collaboratively train a machine learning model over their private datasets. Their goal is to provide better services to their customers by sharing their resources. The different IoT platforms use federated learning to train a common model. Additionally, these platforms do not wish to rely on a trusted third party to run the federated learning server. Therefore, they integrate secure aggregation into federated learning to preserve the privacy of their customers. Each company may have multiple federated learning clients (clients may correspond to different geolocated branches or different company sectors). Consequently, running federated learning protocols on large scale (with a large number of clients) may frequently encounter client failures and dropouts. Such a use case calls for a secure and fault-tolerant federated learning solution with an untrusted server (that can be located on any of the companies' premises).

Most secure aggregation solutions fall short to address such a problem (see Chapter 6). Previous work from Bonawitz et al. [BIK + 17] develops a fault-tolerant secure aggregation that enables the server to recover the aggregate from up to t out of n client failures. The authors design their solution by extending an existing masking scheme [START_REF] Dimitriou | Secure and scalable aggregation in the smart grid resilient against malicious entities[END_REF] with Shamir's secret sharing to enable fault tolerance. Their scheme has been used as a building block for a significant number of privacy-preserving federated learning solutions [BSK + 19,EA20,BEG + 19,BBG + 20,SGA21b,KLS21,SAG + 21,XLL + 20,GLL + 21,SGA21a].

Nevertheless, masking is based on one-time-pad encryption (i.e., modular addition) and hence requires the re-distribution of new keys for each aggregation process. This incurs a significant computation and communication overhead originating from the execution of the key re-distribution among clients and the generation of new masks at each FL round.

We, therefore, propose a new solution that enables a client to use the same key for multiple FL rounds. We revisit the Joye-Libert (JL) secure aggregation scheme proposed in [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF] (see Section 3.4.2.2 in Chapter 3) and propose a variant that supports clients' failures. Compared to [BIK + 17], we provide a more efficient and fault-tolerant secure aggregation scheme since it does not require the re-distribution of the protection keys for each FL round.

Threat Model

We consider a threat model with an untrusted FL server that colludes with some clients. Additionally, we consider some of the honest clients to unintentionally fail (i.e., drop from the protocol) in some federated learning rounds. The failures can happen at any stage of the protocol. The adversary (controlling the server and the colluding clients) is interested in discovering any private information about the individual inputs of the honest clients.

We consider the two possible settings for the adversary as defined in Section 3.2. Namely, the honest-but-curious model and the malicious model. For each of these settings, we identify the minimum required security parameters to achieve Aggregator Obliviousness (see Definition 3.2.1). We rely on a trusted party only to generate the public parameters of our protocol. Attacks that aim to change the result of the aggregated data or to perform some denial of service are out of the scope. Additionally, we do not consider attacks where the adversary impersonates existing clients as these can be prevented by deploying a public key infrastructure with signed certificates. Note that this threat model is common among secure aggregation protocols and it is the same as the one adopted by [BIK + 17] except for the dependency on a trusted party for the setup. We show later how to avoid this dependency.

Prior Work based on Masking

In this section, we discuss the previous works on fault-tolerant secure aggregation. All the existing work focus on masking-based secure aggregation. To achieve fault tolerance, these solutions integrate different types of secret sharing with masking. + 17] as a secure aggregation scheme based on masking. The solution is briefly described in Section 5.4. We here give a more detailed description of the protocol. Every two clients agree on a mutual mask using a keyagreement scheme and use these masks to protect their inputs. To recover from some potential drops of clients, the clients secretly share their secret keys such that any t online clients can help the aggregator reconstruct the missing client's masks and remove them from the aggregate. In more detail, in the SA.Setup phase, the users agree on mutual seeds using Diffie-Hellman key-agreement scheme similar to the case in standard masking-based SA. Additionally, they use the t-out-of-n Shamir's Secret Sharing [START_REF] Shamir | How to share a secret[END_REF] to share their key-agreement [START_REF] Diffie | New directions in cryptography[END_REF] private keys. Using this approach, masks of dropped users can be recovered as long as t users are still online. While this solves the problem of dropped users, it causes a new security problem. More specifically, the aggregator can claim that an online user actually dropped and thus ask for reconstructing its masks and hence reveal the user input. To solve this problem, a double masking technique is used in the SA.Protect phase. Each user adds another layer of masking using a randomly generated mask b i,τ :

SecAgg

Bonawitz et al. propose SecAgg [BIK

c i,τ ← x i,τ + k i,τ + b i,τ
where k i,τ is computed based on the masking construction discussed in Chapter 3 (Equation 3.1). This new mask b i,τ is generated from a randomly generated seed which is also shared using Shamir's Secret Sharing with all other users. In SA.Agg, the aggregator can ask to either reconstruct the blinding mask b i,τ or the Diffie-Hellman private key of a user. Therefore, the aggregator will not be able to reveal individual inputs. So, it first collects t shares of the seed of each mask b i,τ of every online user U i and reconstructs it. Then, it gets t shares of the Diffie-Hellman's secret key of the dropped users and thus reconstructs the missing masks. Consider X and Y as the set of remaining and dropped users, respectively, the aggregation operation is described as follows (all the operations are performed mod R = nR i where Z R i is the range for the input values of each user): + 20] to increase the scalability of secure aggregation protocols. In their solution, the clients do not need to share secret keys with all other clients to achieve robustness against dropouts. The authors propose to build partially connected (as opposed to fully connected) graphs where secure aggregation runs between the connected graph nodes (representing clients) only. More specifically, each client sends and receives secret shares of its keys to/from its neighbor nodes (according to the graph). Since the graph is connected, the correctness of mask cancellation and the privacy of individual values are both guaranteed under certain thresholds. The authors further propose a method to build these graphs to achieve a good tradeoff between security and efficiency. They apply this technique to SecAgg and show that their technique reduces the complexity in a logarithmic scale with respect to the number of users. It relies on Fast Fourier Transfer (FFT) and it decreases the computation cost of sharing and reconstructing a secret. Using FastShare, the authors reduce the computational complexity of the fault-tolerant secure aggregation. However, this comes at a cost of lower security guarantees. Indeed, FastSecAgg can reconstruct the aggregate (with a good probability) if the failed clients are arbitrarily chosen. Therefore, an adversary may prevent the recovery of the aggregate by cherry-picking a few clients and isolating them.

U i ∈X c i,τ - U i ∈X b i,τ + U j ∈Y k i,τ = U i ∈X x i,τ + U i ∈X k i,τ + U i ∈X b i,τ - U i ∈X b i,τ + U j ∈Y k i,τ = U i ∈X x i,τ + ¨¨¨¨B 0 U i ∈X ∪Y k i,τ = n 1 x i,τ 6.3.2 SecAgg +

Bell et al. propose a new technique [BBG

TurboAgg

FTSA -Overview

In this section, we present our fault-tolerant secure aggregation protocol (FTSA) by giving an overview of the main idea. Joye-Libert (JL) scheme [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF] is an AHE-based SA scheme (see the construction of the scheme in Section 3.4.2.2). The scheme allows n users to encrypt their private input with a unique long-term pre-distributed key. Its main interesting property is that it is homomorphic with respect to both the messages and the encryption keys. An aggregator holding the sum of the user keys can decrypt the aggregate of the messages. Since this secure aggregation scheme supports long-term keys, it features a significant advantage in terms of computation and communication cost as it allows the use of the same keys for all FL rounds. However, JL introduces the following challenges when used for federated learning:

Client failures It is common in federated learning that some clients drop in several FL rounds. When one or more clients do not provide a ciphertext for FL round τ , the aggregation fails. This is because the aggregation key used to aggregate the ciphertext is equal to the sum of the user keys. If a client fails, its encryption key will not be involved in the aggregation. We deal with this problem by designing a threshold version of JL to recover from dropouts. Our Idea (Threshold-variant of JL scheme): We design a threshold JL scheme, whereby clients can secretly share their individual keys with each other so that when one or more clients fail, t out of n clients that are still online help provide a protected zero-value that is computed with the failed clients' individual keys. By computing the protected zero-value of the missing clients, the server can correctly compute the aggregated result.

Larger inputs In federated learning, the inputs are the parameters of the client's model and are of vector type. JL is originally designed to encrypt single integers. We extend JL to support vector inputs.

Our Idea (JL scheme with vector inputs): We propose to encode the vector elements in a single integer. The vector sum is decoded after aggregation.

No trusted key dealer JL requires a key dealer to distribute some keys to the users and the aggregator. However, a trusted key dealer may not be feasible in federated learning applications. Therefore, we propose a decentralised key setup phase to distribute the keys.

Our Idea (JL scheme with decentralized key setup): In order not to rely on a trusted key dealer, we propose a distributed key generation mechanism. We mainly use secure multi-party computation such that each of the n users and the aggregator get a random additive share of zero. Each user will use its share as a secret key so that the sum of the keys with the aggregator key equals zero.

Threshold Joye-Libert Scheme

We describe a threshold version of the Joye-Libert secure aggregation scheme (see Section 3.4.2.2 for the original scheme). The design of this scheme mainly transplants the design of the threshold version of the Paillier encryption scheme [START_REF] Damgård | A generalization of paillier's public-key system with applications to electronic voting[END_REF] into this context. This extended solution mainly helps the aggregator recover failed users' inputs (which consists of the protection of the zero-value under each failed user's individual key) and hence compute the final aggregate value. The goal is to distribute user key k i to the n users such that any subset of at least t (online) users can produce a ciphertext on behalf of user U i while less than t users learn

Pr                X τ ̸ = ∀U i ∈Uon x i,τ TJL.Setup(λ, σ) → (pp, k 0 , {k i } ∀i∈[n] ), TJL.SKShare(pp, k i , t, n) → {(i, ⟨k i ⟩ j )} ∀j∈[n] ∀i∈[n] , TJL.ShareProtect(pp, {⟨k j ⟩ i } ∀U j ∈U \Uon , τ ) → ⟨y ′ τ ⟩ i ∀U i ∈U τ shares , TJL.Protect(pp, k i , τ, x i,τ ) → y i,τ ∀U i ∈Uon , TJL.ShareCombine(pp, {(i, ⟨y ′ τ ⟩ i )} ∀U i ∈Ushares ) → y ′ τ , TJL.Agg(pp, k 0 , τ, {y i,τ } ∀U i ∈Uon , y ′ τ ) → X τ                = 0
Theorem 6.5.1

The scheme TJL is correct.

Proof.

To prove the correctness of TJL, observe that the following equalities hold:

1) y i,τ = (1 + x i,τ N )H Z * N 2 (τ ) k i mod N 2 2) ⟨y ′ τ ⟩ i =H Z * N 2 (τ ) U j ∈U \Uon ⟨k j ⟩ i mod N 2 3) y ′ τ = U i ∈Ushares (⟨y ′ τ ⟩ i ) ν i = H Z * N 2 (τ ) U i ∈U shares ν i U j ∈U \Uon ⟨k j ⟩ i = H Z * N 2 (τ ) U j ∈U \Uon U i ∈U shares ν i ⟨k j ⟩ i = H Z * N 2 (τ ) ∆ 2 U j ∈U \Uon k j 4) y τ = ( U i ∈Uon y i,τ ) ∆ 2 • y ′ τ mod N 2 = (1 + ∆ 2 ∀U i ∈Uon x i,τ N )H Z * N 2 (τ ) ∆ 2 ∀U i ∈Uon k i • H Z * N 2 (τ ) ∆ 2 ∀U i ∈U \Uon k i = (1 + ∆ 2 ∀U i ∈Uon x i,τ N )H Z * N 2 (τ ) ∆ 2 ∀U i ∈U k i = (1 + ∆ 2 ∀U i ∈Uon x i,τ N )H Z * N 2 (τ ) -∆ 2 k 0 5) V τ = H(τ ) ∆ 2 k 0 • y τ = (1 + ∆ 2 ∀U i ∈Uon x i,τ N ) Theorem 6.5.2
This scheme provides Aggregator Obliviousness security under the DCR assumption in the random oracle model if the number of corrupted users is less than threshold t.

Proof.

The security of this scheme mainly relies on the security of the JL secure aggregation scheme which is proved secure under the DCR assumption (Theorem 3.4.2). Similar to the original scheme, we assume that each user encrypts at most one input per timestamp. Additionally, we assume that failed users do not provide any encrypted values for that timestamp and the non-corrupted users construct at most one encrypted value on behalf of the failed clients. By relying on the security of the secret sharing scheme over integers (which is proved to be statistically secure in Theorem 1 in [START_REF] Veugen | An implementation of the paillier crypto system with threshold decryption without a trusted dealer[END_REF]), we can show that less than t users cannot construct an encrypted value. Therefore, Aggregator Obliviousness is guaranteed in the random oracle model under the DCR assumption if less than t users are corrupted.

FTSA -Complete Specifications

We now describe the newly designed secure and fault-tolerant aggregation protocol based on the proposed TJL scheme. The protocol consists of a setup phase and an online phase each of them defined with two communication rounds. The setup phase is performed once, while the online phase is repeated for each federated learning round. We describe the details of each protocol phase.

The Setup Phase

The setup phase consists of the registration of the clients and the distribution of the security keys. In TJL, a trusted key dealer is needed to generate the keys. To avoid the dependence on a key dealer, we propose a distributed method to setup the TJL user keys.

Distribution of TJL keys

We recall that the aggregator's key k 0 allows the aggregator to recover the sum of the inputs from the set of users' ciphertexts (see Equation 6.1). The goal of this key is to protect the final aggregate result. In the case of FL applications, the aggregated ML model is considered public and thus does not need to be hidden. Therefore, we set the aggregator's key to a publicly known value (for example zero). Indeed, the security proof in [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF] considers the case where an adversary controls the key of the aggregator. In such case, the scheme cannot protect the result of the aggregation but it still protects the individual inputs of the users which is sufficient for FL. To generate the user keys, every two clients U i and U j agree using the KA scheme on a shared mutual key k i,j . Then, client U i computes its protection key k i ← U j ∈U (δ i,j • k i,j ) where δ i,j = 1 0's at the beginning of the element. Then the elements of the vector are packed to form a large integer ω. The number of elements that ω represents corresponds to ptsize which denotes the plaintext size of TJL divided by the actual size of the extended element (i.e ⌊ ptsize log 2 (R)+log 2 (n) ⌋,R being the maximum possible value for vector elements). Note that for TJL scheme, the plaintext size is equal to half of the size of the user key (ptsize = |k i | 2 ). The decoding operation simply consists of unpacking ω into bitmaps of log 2 (R) + log 2 (n).

To execute TJL.Protect and TJL.ShareProtect, the user input is first encoded. In the case where the user input vectors are too large to be encoded in a single integer of size ptsize, the vectors are split into multiple vectors of length ⌊ ptsize log 2 (R)+log 2 (n) ⌋ and encoded separately. We use a counter to generate a unique timestamp for each encoded part.

Protocol steps In the Encryption step, the client generates random seed b i which is further extended to blinding mask B i using a PRG. The client first blinds its input with B i then protects it with TJL.Protect. After that, the client secretly shares the seed b i with other clients and sends its masked and protected input to the server.

In the Aggregation step, the client learns the list of failed clients and computes TJL.ShareProtect using the sum of their TJL keys' shares. Then, it sends to the server the blinding mask share of each online client and the share of the protected zero-value corresponding to all the failed clients. The server constructs the blinding masks and the protected zero-value using TJL.ShareCombine. Finally, it uses TJL.Agg to obtain the blinded sum which is unblinded by removing the clients' masks. The detailed specification of this phase is provided in Figure 6.3.

Deployment of FTSA on Semi-Connected Graphs (FTSA + )

In the current description of the protocol, we assumed that all clients secretly share their keys with each other. This gives the maximum security guarantee. However, as shown in [BBG + 20], the client doesn't need to share its key with all other clients (see Section 6.3). Indeed it is sufficient to build a connected graph where each node (representing a client) is connected to a subset of all clients and only shares its key with this subset. As we presented in Section 6.3, this technique is used to improve the scalability of SecAgg [BIK + 17]. We observe that the same method can also be applied to FTSA. We refer to our protocol as FTSA + when deployed on such graphs. Given a connected graph as described in [BBG + 20], FTSA + , involves the same steps as FTSA, except that the sharing of the key is done only with the neighbor clients. By using this optimization, the complexity of our protocol in terms of the number of users is reduced into a logarithmic factor.

Security Analysis

In this section, we evaluate the security of our secure and fault-tolerant aggregation protocol (FTSA) and prove that it ensures Aggregator Obliviousness (see Definition 3.2.1)

FTSA -Online Phase

• Online -Encryption (step τ ):

User u:

-Sample a random element bi,τ R ← -F (to be used as a seed for a PRG). -Extend bi,τ using the PRG: Bi,τ ← PRG(bi,τ ).

-Protect the private input Xi,τ ∈ Z m R (after masking it with Bi,τ ) using TJL scheme: Yi,τ ← TJL.Protect(pp, ki, τ, Xi,τ + Bi,τ ).

-Generate t-out-of-n shares of bi,τ using the SSS scheme: {(j, ⟨bi,τ ⟩j)} ∀U j ∈U ← SSS.Share(bi,τ , t, n, F).

-For each registered user Uj ∈ U \ {Ui}, encrypt its corresponding shares e (i,j),τ ← Encc i,j (Ui || Uj || ⟨bi,τ ⟩j) -If any of the above operations fails, abort.

-Send all the encrypted shares {e (i,j),τ } ∀U j ∈U (with addressing information Ui, Uj as metadata)

and the protected input Yi,τ to the server . Server: -Collect from each user u its encrypted shares {(Ui, Uj, e (i,j),τ )} ∀U j ∈U and its protected input Yi,τ (or time out).

-Denote with U τ on ⊂ U the set of online users. Abort if |U τ on | < t. -Forward to each user Uj ∈ U τ on its corresponding encrypted shares: {(i, j, e (i,j),τ )} ∀U i ∈U τ on . • Online -Aggregation (step τ ):

User u:

-Receive the encrypted shares and deduce the list of online users U τ on from the received shares. Verify that U τ on ⊂ U and |U τ on | >= t. -Decrypt all the encrypted secret shares:

U ′ j || U ′ i || ⟨bj,τ ⟩i ← Decc i,j (e (j,i),τ ) . Assert that Ui = U ′ i ∧ Uj = U ′ j
-Compute the share of the zero-value corresponding to all failed users: ⟨Y ′ τ ⟩i ← TJL.ShareProtect(pp TJL , {⟨kj⟩i} ∀U j ∈U \U τ on , τ ). -Abort if any operation failed.

-Send the secret shares of the blinding mask seeds {⟨bj,τ ⟩i} ∀U j ∈U τ on and of the share of the protected zero-value ⟨Y ′ τ ⟩i to the server. Server: -Collect shares from at least t honest users. Denote with U τ shares ⊂ U τ on the set of users. Abort if |U τ shares | < t. -Construct the blinding mask seed of all users bi,τ ∀Ui ∈ U τ on : bi,τ ← SSS.Recon({⟨bi,τ ⟩j} ∀U j ∈U τ shares , F) -Recompute the blinding mask: Bi,τ ← P RG(bi,τ ) -Construct the protected zero-value corresponding to all failed users:

Y ′ τ ← TJL.ShareCombine(pp, {⟨Y ′ τ ⟩j} ∀U j ∈U τ shares )
-Aggregate all the protected inputs of the online clients and the protected zero-value:

Cτ ← TJL.Agg(pp, 0, τ, {Yi,τ } ∀U i ∈U τ on , Y ′ τ ) -Remove the blinding masks Cτ - ∀U i ∈U τ on Bi,τ = ∀U i ∈U τ on Xi,τ

Security in the honest-but-curious model

As explained in Section 3.2, in the honest-but-curious model, the adversary, who corrupts the aggregator and a subset of the clients, correctly follows the protocol but colludes with up to n -t clients. Let U corr be the set of corrupted clients and C = U corr ∪ A (A represents the aggregator). Theorem 6.7.1: Security in the honest-but-curious model

In the honest-but-curious model, the protocol FTSA achieves Aggregator Obliviousness if the number of corrupted clients is less than threshold t (|U corr | < t).

Proof.

To prove this argument, we show that the view of C is computationally indistinguishable from a simulated view where all inputs of the honest clients are replaced with random values (given that the sum of the random inputs is equal to the sum in the real view). For the offline phase, the proof is trivial as the offline phase is considered as a distribution of a secret sharing a zero value between n parties using Diffie-Hellman. Thus, we focus on proving security in the online phase using a hybrid argument that relies on the security of the underlying cryptographic primitives.

H 0 H 0 H 0 : This hybrid view is the same as the real view.

H 1 H 1 H 1 :
In this hybrid view, we replace all channel keys established by KA.agree between honest clients with uniformly random keys. The Decisional Diffie-Hellman assumption guarantees that this hybrid view is indistinguishable from the previous one.

H 2 H 2 H 2 : In this hybrid view, we replace all ciphertexts generated from Enc between honest clients with encryptions of zeros (padded to the right length). The IND-CPA security of the encryption scheme (see Definition 2.3.5) guarantees that this hybrid view is indistinguishable from the previous one.

H 3 H 3 H 3 :
In this hybrid view, we replace all shares of b i sent in the online phase from honest clients U i ∈ U \ U τ on \ U corr to corrupted ones with a random share of zero. Notice that the adversary does not receive additional shares of b i in the construction phase since the honest clients do not provide shares of b i for U i ∈ U \ U τ on . Hence, if |U corr | < t, this hybrid view is indistinguishable from the previous one due to the security of the ISS scheme (see Definition 2.3.2).

H 4 H 4 H 4 : In this hybrid view, we replace all honest clients' (U \U corr ) inputs with uniformly random values such that the sum of the online clients' random inputs is equal to the aggregate. The simulator masks these random values and then protects them with TJL.Protect and gives the resulting ciphertexts to the adversary. Notice that we allow the adversary to receive TJL.Protect ciphertexts from offline clients as this may happen in benign scenarios where the aggregator receives the delayed ciphertext after it had considered the user offline.

-For the online honest clients (U i ∈ U τ on \ U corr ) the adversary does not receive the shares of the zero-protected value from the honest clients. Thus, the adversary cannot construct the zero-protected value of the user U i if |U corr | < t. Hence, the adversary only sees one ciphertext of TJL.Protect of the user U i . The security of TJL states that the ciphertext of two different values cannot be distinguished under the DCR assumption if only one ciphertext per timestamp is provided (see Theorem 6.5.2). Therefore, the ciphertext of the uniformly random input in this hybrid is indistinguishable from the ciphertext of the real input from the real view.

-For the offline honest clients (U i ∈ U \ U τ on \ U corr ) the adversary does not receive the shares of the mask b i from honest clients. Thus, the adversary cannot construct the mask b i of the user U i if |U corr | < t. Hence, the masked random input in this hybrid view cannot be distinguished from the masked real input in the real view.

Since the adversary cannot distinguish the messages in the hybrid view from that in the real view for both online and offline clients, we can deduce that this hybrid view is indistinguishable from the previous one if |U corr | < t.

We showed that we can define a simulator that can simulate the view of parties in C, where for any adversary in polynomial time the output of the simulation is indistinguishable from the real view of C if |U corr | < t. Thus, the aggregator learns nothing more than the sum of the inputs of the online honest clients. This proves Aggregator Obliviousness. Corollary 6.7.1

In the honest-but-curious model, security is guaranteed if the minimum number of honest clients t should be strictly larger than half of the number of clients in the protocol (t > n

2 ) and the protocol can recover from up to n 2 -1 client failures.

Proof.

From Theorem 6.7.1, |U corr | < t. We also have the number of honest users set to the threshold t (i.e, |U corr | = n -t). Therefore, t > n 2 .

Security in the malicious model

As explained in Section 3.2, in the malicious model, the adversary, who corrupts the aggregator and a subset of users, can additionally manipulate the messages of the corrupted parties.

Theorem 6.7.2: Security in the malicious model

In the malicious model, the protocol FTSA achieves Aggregator Obliviousness if the number of corrupted clients is

|U corr | < 2t -n.
Proof.

The only messages that the aggregator distributes, are the encrypted shares. The aggregator cannot modify the values of these encrypted shares thanks to the underlying authenticated encryption Enc scheme (see Definition 2.3.6). Therefore, the aggregator's power in the protocol is limited to not forwarding some of the shares. This will make clients reach some false conclusions about the set of online clients in the protocol. Note, importantly, that the aggregator can give different views to different clients about which clients have failed. Therefore, the aggregator can convince a set of honest clients to send the protected zero-value Y ′ τ corresponding to client U i (i.e., U \ U τ on = {U i }) while asking another set of honest clients to send the shares of the blinding mask b i,τ . The aggregator should not obtain the protected zero-value Y ′ τ corresponding to a client U i and its blinding mask b i,τ for the same FL round τ . If that happens, the aggregator can recover the masked input from Y ′ τ and Y i,τ , then remove the mask using b i,τ . Knowing that the aggregator may collude with |U corr | corrupted clients, The adversary controlling Finally, we can use the same hybrid argument used in the proof of security in the honest-but-curious model except that in the active model the adversary chooses to receive the share ⟨Y ′ τ ⟩ j or the share ⟨b i,τ ⟩ j from each honest client U j (instead of being fixed according to U τ on ). Hence, the indistinguishablity can be ensured as long as the maximum number of shares of both values obtained by the adversary is less than the reconstruction threshold ( n+|Ucorr| 2 < t). Therefore, we can prove Aggregator Obliviousness if the number of corrupted clients is

C obtains |U corr | shares of Y ′ τ s.t. U \ U τ on = {U i }
|U corr | < 2t -n. Corollary 6.7.2
In the active model, security is guaranteed if the minimum number of honest clients t should be strictly larger than two third of the number of clients in the protocol (t > 2n

3 ) and the protocol can recover from up to n 3 -1 client failures.

Proof.

From Theorem 6.7.2, |U corr | < 2t -n. We also have the number of honest users set to the threshold t (i.e, |U corr | = n -t). Therefore, the reconstruction threshold is t > 2n 3 .

Performance Analysis

In this section, we analyze the performance of FTSA in terms of computation, communication, and storage costs at both the client and the server and compare it with the state-of-the-art. We first perform the complexity analysis with respect to the number of clients n and the dimension of the client's input m. Then, we implement the protocol and conduct an experimental evaluation of it. For completeness, we analyze both the offline and online phases. We only compare the online phases of different protocols since the offline setup phase is a one-time process.

Table 6.1: Complexity analysis of the online phase of FTSA and the state-of-the-art protocols. The values represent the order of complexity. n is the number of clients (order of hundreds) and m is the dimension of the client's input (order of hundreds of thousands).

Communication Computation

Client Server Client Server

SecAgg [BIK + 17] m + n nm + n 2 nm + n 2 n 2 m SecAgg + [BBG + 20] m + log(n) m + log(n) m + log(n) nm + n log(n) nm + n log(n) nm + n log(n) log(n)m + log 2 (n) n log(n)m + n log 2 (n) TurboAgg [SGA21b] log(n)m n log(n)m log(n)m nm nm nm FastSecAgg [KRKR20] m + n nm + log 2 (n) log(n)m nm nm nm FTSA m + n nm + n 2 m + n 2 nm + n 2 FTSA + m + log(n) m + log(n) m + log(n) nm + n log(n) nm + n log(n) nm + n log(n) m + log 2 (n) m + log 2 (n) m + log 2 (n) nm + n log 2 (n)

Scalability Analysis of The Offline Phase

In terms of communication cost, the offline phase consists of each client receiving n public keys and sending n shares of its secret keys. Thus, the complexity is O(n) for the client and O(n 2 ) for the server. In terms of computation cost, the server only relays the messages between the clients so it does not perform cryptographic operations. However, the client's cost is dominated with creating t shares of its secret keys which is O(n 2 ). Finally, the storage requirement of the client depends on the number of shares which is

O(n) while it is O(n 2 )
for the server since it has to collect and forward the encrypted shares of all clients.

Scalability Analysis of The Online Phase at the Client

Communication The communication cost consists of: During the Encryption step:

1. Sending O(n) shares of b i,τ and receiving O(n) shares.

2. Sending the encrypted client input which is O(m).

Aggregating the ciphertexts and unmasking the result which is O(nm).

The total computation cost equals to O(n 2 + nm) which is lower than the one in [BIK + 17] (O(n 2 m)).

Note that the reconstruction of t out of n shares normally costs O(n 2 ) since it consists of computing the Lagrange coefficient O(n 2 ) and then applying the Lagrange formula O(n). Thus, the computation of t out of n shares for n clients should cost O(n 3 ). However, we optimize the reconstruction by computing the Lagrange coefficients only one time per FL round and use them for all the reconstructions which result in O(n 2 + n) ≡ O(n 2 ).

Storage O(n 2 + nm). The server storage consists of: t shares of b i,τ for each client b i,τ which is O(n 2 ) and t shares of Y ′ τ which is O(nm). We have implemented a prototype of the TJL scheme and our fault-tolerant secure aggregation protocol. Additionally, we have also implemented a prototype of the protocol presented in [BIK + 17]. Our implementation is done using Python programing language and is available on GitHub1 . We first benchmark our new proposed TJL secure aggregation scheme. Then, we run several experiments with our secure aggregation protocol and the one in [BIK + 17] while varying the number of clients n = {100, 300, 600, 1000}. We also use different dimensions for clients' inputs m = {10 3 , 10 4 , 0 5 , 10 6 } and different client failure rates f = {0%, 10%, 20%, 30%}. In each experiment, we run all the clients' and the server's processes and measure their execution time. We also measure the size of the data transmitted in the network. The measurements are performed using a single-threaded process on a machine with an Intel(R) Xeon(R) CPU E5-2697 v4 @ 2.30GHz processor and 32 GB of RAM.

Experimental Evaluation

Implementation Details

We use the same implementation and parameters for the building blocks of our protocol and the protocol proposed in [BIK + 17].

• Pseudo-Random Generator (PRG): We use AES encryption [DBN + 01] in the counter mode with 128 bits key size. Thus, the blinding mask seed (b i ) is 128-bit long.

• Key Agreement (KA): We use Elliptic-Curve Diffie-Hellman over the NIST P-256 curve. For the hash function, we use SHA256.

• Secret Sharing (SS): We use the finite fields F p (integers modulo p where p is prime) in the implementation of Shamir's secret sharing. To share the seed of the blinding mask (b i ) (128 bits) we set p = 2 129 -1365. To share the DH secret key (256 bits) we set p = 2 257 -2233.

• Authenticated Encryption (Enc): We use AES-GCM [START_REF] Dworkin | recommendation for block cipher modes of operation: Galois/counter mode (gcm) and gmac[END_REF] with a key size of 256 bits.

• Threshold Joye-Libert Scheme (TJL): We use 1024 bits for the public parameter N . Thus, the user keys are of size 2048 bits. For the hash function H : Z → Z * N 2 , we implement it as a Full-Domain Hash using a chain of eight SHA256 hashes. Additionally, for the secret sharing over the integers scheme ISS used by TJL.SKShare, we set the security parameter σ to 128 bits.

Benchmarks for JL and TJL schemes

We show in Table 6.2 the execution time of all the algorithms of JL and TJL schemes.

Benchmarks for FTSA and SecAgg

Running time for clients We plot the wall-clock running time for a client in both protocols (i.e., our protocol and the one in [BIK + 17]) in Figure 6.4a. Our protocol shows better running time in most of the scenarios. Additionally, our protocol scales better with respect to the increasing number of clients (i.e., our solution is ×1.5 faster with 100 clients, ×5.5 faster with 600 clients, and ×8 faster with 1000 clients). This confirms the study in Section 6.8.2. We also show the setup time for our protocol in Table 6. [START_REF] Mansouri | Verifiable Secure aggregation in The Malicious Model[END_REF]. The results show that the offline time becomes negligible after running a sufficient number of FL rounds.

Running time for the server We plot the wall-clock running time for the server in both protocols (i.e., our protocol and the one in [BIK + 17]) in Figure 6.4b. We show the Table 6.2: Benchmarks of JL and TJL schemes. The time measurements are in milliseconds such that x / y refers to x ms runtime for JL scheme and y ms runtime for TJL scheme. The current benchmarks are run with 30% user failures and 70% threshold. Gray distinguishes the algorithms that are executed only once for the setup. n = 100 n = 300 n = 600 In general, the cost is higher in our protocol since the reconstruction operation (i.e., Lagrange formula) is computed on the exponent. However, this overhead is constant in our protocol w.r.t. the number of failed clients (i.e., construction of single value Y ′ τ that represents all failed clients). Therefore, the scalability of our protocol with respect to the number of failures is better. We show the detailed running time (per protocol round) in Table A.1 in Appendix A.1.

Data transfer

To measure the data transfer, we measure the size of the data sent by the client to the server, and the data received by the client from the server. We plot the total data transfer (sent and received) per client in both protocols (i.e., our protocol and the protocol in [BIK + 17]) in Figure 6.4c. Our protocol has larger data transfer in scenarios with a low number of clients (n = 300) but is more efficient when the number of clients is increased to n = 1000. This shows that our protocol scales better with an increasing number of clients. On the other hand, our protocol involves larger data transfer when the input dimension increases. This is mainly because of the larger size of the ciphertext (two computation and communication complexity of the user in the online phase becomes constant with respect to the number of users.

The Protocol

Similar to FTSA, our optimized secure and fault-tolerant aggregation protocol is composed of an offline and an online phase. In the setup phase, the users compute their TJL secret keys similar to FTSA protocol. In addition, each user generates a masking key bk i ←$ {0, 1} 2l and shares it with the other user using the t-out-of-n secret sharing scheme. Thus, each user U i will get a share {(j, ⟨bk j ⟩ i )} ∀U j ∈U .

In the encryption step of the online phase, the users do not need to mask their input with B i,τ which is generated from secretly shared seed b i,τ . Instead, they compute the TJL.Protect of their input with the masked key and send it to the server. Next, in the construction step, the online users construct the zero-protected values of the offline users similar to FTSA protocol. In addition, they help the aggregator remove the masking keys from the ciphertexts of the online users. The details of the online phase of the new protocol are shown in Figure 6.5.

Security Analysis

Theorem 6.9.1

The protocol FTSA * achieves Aggregator Obliviousness in the passive model if the number of corrupted clients is less than threshold t (|U corr | < t) and it achieves Aggregator Obliviousness in the active model if the number of corrupted clients is

|U corr | < 2t -n.

Proof.

FTSA * uses TJL scheme which is secure under the DCR assumption if the users encrypt no more than one ciphertext for each timestamp. Encrypting with a masked key (k i + bk i ) is equivalent to masking the ciphertext of each user at each timestamp with a fresh random mask H(τ ) bk i (i.e., TJL.Protect(

k i + bk i , τ, x i,τ ) = (1 + x i,τ N )H Z * N 2 (τ ) k i H Z * N 2 (τ ) bk i ).
Similar to FTSA, removing the mask requires at least t users to collaborate where t is the threshold of the secret sharing scheme. Hence, similar to the security analysis in Section 6.7, and based on Theorems 6.7.1 and 6.7.2, FTSA * achieves Aggregator Obliviousness when (|U corr | < t) in the case of a passive adversary and it achieves Aggregator Obliviousness when |U corr | < 2t -n in the active. Corollary 6.9.1

In the passive (active) model, security is guaranteed if the minimum number of honest clients t > n 2 (t > 2n 3 ) and the protocol can recover from up to n 2 -1 ( n 3 -1) client failures.

Proof.

The proof follows the proof for Collaries 6.7.1 and 6.7.2 6.9.4 Performance Analysis Table 6.5: Complexity analysis of the online phase of FTSA * scheme and the state-of-theart protocols. The values represent the order of complexity. n is the number of clients (order of hundreds) and m is the dimension of the client's input (order of hundreds of thousands).

Communication Computation

Client Server Client Server

SecAgg [BIK + 17] m + n nm + n 2 nm + n 2 n 2 m SecAgg + [BBG + 20] m + log(n) nm + n log(n) log(n)m + log 2 (n) n log(n)m + n log 2 (n) TurboAgg [SGA21b] log(n)m n log(n)m log(n)m nm nm nm FastSecAgg [KRKR20] m + n nm + log 2 (n) log(n)m nm nm nm FTSA m + n nm + n 2 m + n 2 nm + n 2 FTSA + m + log(n) nm + n log(n) m + log 2 (n) nm + n log 2 (n) FTSA * m m m nm nm nm m m m nm nm nm
FTSA * shows a significant improvement in the performance of the user in the online phase. More specifically, the computation cost of the user is one call of the algorithm TJL.Protect and two calls to TJL.ShareProtect. Consequently, the communication cost is sending three ciphertexts. Therefore, both costs depend on the size of the user input (i.e., only O(m)). On the other hand, the server computation cost involves computing TJL.ShareCombine twice to reconstruct Y ′ τ and Ỹτ from their shares. These operations are O(nm). It also involves aggregating the ciphertexts and unmasking the result which is O(nm). Therefore the asymptotic costs of the user and the server are reduced to O(m) and O(nm) respectively which correspond to the theoretical bound since this is equivalent to the cost of federated learning without using secure aggregation. Table 6.5 summarizes the result.

Conclusions

We presented two versions of a new secure and fault-tolerant aggregation protocol (FTSA and FTSA * ). Our solutions use the additively homomorphic encryption scheme of Joye-Libert [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF] with Shamir's secret sharing to achieve fault tolerance. FTSA protocol outperforms the state-of-the-art protocols in terms of the computational cost of the federated learning clients. On the other hand, our optimized version FTSA * allows performing all secret-sharing operations during the setup phase. Hence, The online phase of FTSA * has only a constant factor of overhead compared to a base federated learning protocol (without secure aggregation). Consequently, FTSA * outperforms all the existing fault-tolerant secure aggregation protocols in terms of the asymptotic cost on both the clients and the server. We show that FTSA * indeed achieves optimal scalability.

Part III

Remote Attestation Protocols

Chapter 7

Fairness-Driven Remote-Attestation

In this chapter, we investigate remote attestation protocols when the IoT network is large, dynamic, and heterogeneous. We first study state-of-the-art solutions for collaborative remote attestation and we identify challenges due to the large size of IoT networks; We focus on two particular problems: the heterogeneity of the devices used in the network and the dynamic nature of IoT networks. To deal with these challenges, we propose FADIA, the first lightweight collaborative remote attestation protocol that is designed with fairness in mind: FADIA enables the fair distribution of attestation load/tasks to achieve better performance. We implement our solution on heterogeneous embedded devices and evaluate it in real scenarios. The evaluation shows that FADIA can (i) increase the lifetime of a network by an order of magnitude and (ii) decrease the remote attestation runtime by a factor of 1.6. Remote attestation (RA) is a technique that enables a device called prover to prove the integrity of its software configuration to another remote device called verifier.

• The prover : It is the device that needs to prove its software integrity. The device executes some internal procedure that checks its software configuration and consequently generates a cryptographic proof. The procedure is usually run inside a trusted execution environment in the device.

• The verifier : The device that verifies the integrity of the prover's software. It receives the proof from the prover and validates it. The verifier relies on a root of trust such as a trusted execution environment installed on the prover.

Root of Trust for Remote Attestation Protocols

In remote attestation protocols, the verifier in an attestation protocol relies on a root of trust existing on the prover device. Based on the kind of the root of trust, there are three types of attestations: Hardware Root of Trust [AFS97,Gro08,KSA + 09,SZJvD04] Hardware-based attestation relies on assumptions concerning the hardware that hosts the attestation code. This involves hardware components such as Trusted Platform Modules (TPM) [START_REF]Trusted platform module (tpm) summary[END_REF] and secure co-processors [START_REF] Smith | Outbound authentication for programmable secure coprocessors[END_REF]. These extra hardware components perform verification tasks such as secure booting. The high cost of these techniques limits their use for IoT devices.

Software Root of Trust [GGR09, SLP08
Hybrid Root of Trust [FNRT14, KPS + 14, EFPT12, BES + 15] More recently, hybrid approaches for the root of trust have been proposed. These approaches rely on a combination of hardware and software assumptions. They propose to design a minimal secure hardware architecture on the prover which can be used to perform integrity checks on the prover's running software. It then creates a cryptographic proof and sends it to the verifier. The verifier upon validating this proof authenticates the prover and thus trusts its software.

Collaborative Remote Attestation

Lately, to adhere to the increasing number of embedded devices in the network, collaborative remote attestation protocols are proposed. The idea of collaborative remote attestation is to allow the IoT devices to collaboratively collect attestations from each other and finally produce a single proof for the IoT platform administrators. Hence, it improves the scalability of the protocol.

In this thesis, we are interesting on studying collaborative remote attestation techniques since they are very practical in IoT networks.

Previous Work on Collaborative Remote Attestation

In this section, we present previous work on collaborative remote attestation. We first regroup them into three categories based on the type of connection topology between provers. Then, we categorize them based on the type of key management. Finally, we identify the main limitations of the previous work in the literature.

Categorization based on Connection Topology

In collaborative remote attestation, provers communicate with each other to collect the proofs. We identify three main types of collaborative remote attestation based on the topology of the connection between provers.

Remote Attestation using Tree Topology

Collaborative remote attestation such as SANA [ACI + 16], LISA [START_REF] Carpent | Lightweight swarm attestation: A tale of two lisa-s[END_REF], SEDA [ABI + 15], and SHeLA [RVW + 19] are designed for static or quasi-static networks. These approaches run on devices deployed in a static tree topology. Tree structures provide an efficient and scalable method for verifying a large number of devices. In general, there exist three roles in the tree based on the position of the nodes:

• Initiator node: This is the root node of the tree. It initiates the tree construction (attestation) process.

• Intermediate node: This corresponds to any node in the tree that has a parent node and children nodes. It forwards messages from its parent to its children and vice versa. It usually also aggregates the attestations received from the children nodes.

• Leaf node: This is any node in the tree that has no children nodes. The message forwarding stops at this node. It sends its attestation to its parent node.

Using this tree structure, provers can collaboratively attest by aggregating their proofs. Depending on the type of cryptographic tools used to generate the proof, different aggregation algorithms may be used. For example, SANA [ACI + 16] uses a combination of Boldyreva's multi-signature scheme [START_REF] Boldyreva | Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme[END_REF] and Boneh et al.'s aggregate signature scheme [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] to generate a proof. Other solutions like LISA [START_REF] Carpent | Lightweight swarm attestation: A tale of two lisa-s[END_REF] uses simple message authentication code (MAC) to generate proofs.

Remote Attestation using Mesh Topology Another line of research proposes RA schemes that use a gossip-based mechanism and run in dynamic mesh networks. Examples of such an approach are DARPA [START_REF] Ibrahim | Darpa: Device attestation resilient to physical attacks[END_REF], PADS [ACL + 18], SALAD [START_REF] Kohnhäuser | Salad: Secure and lightweight attestation of highly dynamic and disruptive networks[END_REF], and SARA [DRC + 20]. In these protocols, provers share their attestations with all their neighbors, then the received attestations are aggregated and forwarded. The process is repeated until convergence is reached about the state of all provers. Although gossip-based protocols offer high tolerance against failures and a high degree of autonomy, they suffer from high bandwidth overhead and long runtime.

Remote Attestation using Hybrid Topology Recently, Kohnhauser et al. proposed PASTA [START_REF] Kohnhäuser | A practical attestation protocol for autonomous embedded systems[END_REF], an autonomous RA protocol in which provers create multiple spanning trees in the network and generate the so-called tokens to verify the attestations of the provers participating in the tree. Each token embeds the attestations of all the nodes in the tree. Later, these tokens are distributed among all the provers in a gossip-like approach. The parallelized tree generation process in PASTA allows for a relatively low runtime for the protocol. Also, the token distribution offers autonomy (decentralization) to the RA protocol. However, PASTA does not scale well in terms of communication due to the broadcasting of large-size tokens. Also, PASTA requires provers with high storage and computation capabilities. This is because it uses asymmetric cryptography for token generation.

Categorization based on Key Management

In remote attestation protocols, two types of secret keys are defined: the communication keys which are used to establish a secure channel between provers and the attestation keys which are used for attestation, i.e., to generate a proof of the integrity of a prover's software. We identify two main types of collaborative remote attestation with regard to the underlying key management mechanism.

Remote Attestation using a Single Shared Key In such RA solutions, the network operator defines a single key shared among all provers. This key is used as both a communication key and an attestation key (e.g., PADS [ACL + 18]). Such an approach enables the efficient addition of new devices to the network at runtime. Nevertheless, solutions become inefficient if a single node is compromised (as all nodes need to update their keying material).

Remote Attestation using Pairwise Unique Keys In such RA solutions, each prover holds a unique attestation key and a pair-wise mutual communication key with each other prover. An example of this type of RA is SALADS [START_REF] Kohnhäuser | Salad: Secure and lightweight attestation of highly dynamic and disruptive networks[END_REF], PASTA [START_REF] Kohnhäuser | A practical attestation protocol for autonomous embedded systems[END_REF], and DARPA [START_REF] Ibrahim | Darpa: Device attestation resilient to physical attacks[END_REF]. This approach ensures better security guarantees and enables an efficient revocation mechanism. However, it does not scale with a high number of provers. Moreover, the addition of new devices to the network becomes costly because each newly joined device requires a key distribution mechanism to run with all existing provers.

Limitation of Previous Work

The aforementioned collaborative remote attestation solutions tackle different challenges such as scalability, security and robustness. Unfortunately, these solutions may become inefficient and sometimes even impractical for some applications of IoT networks. This is mainly because the current state-of-the-art solutions disregard two common characteristics of IoT networks: (i) heterogeneity of IoT networks and (ii) continuous increase in the size of the network (i.e., devices are added to the network gradually over time).

Heterogeneity of devices: Large-scale RA protocols involve collaborative tasks across devices. These tasks include the generation and forwarding of attestations. Existing solutions perform the distribution of this load (i.e., RA tasks) randomly or uniformly. This may imply a significant performance decrease in heterogeneous networks because it results, usually, in creating bottlenecks, resulting in a degradation of the overall performance. We define heterogeneity in the IoT network as the diversity in the (hardware and/or software) characteristics of the IoT devices. For instance in Industry 4.0 IoT applications [START_REF] Roblek | A complex view of industry 4.0[END_REF], sensor devices in the network (ex. Tmote Sky [START_REF]Tmote sky details[END_REF]) have Microcontroller Units (MCU) with low computational capabilities compared to a Raspberry Pi operating in robots.

The quality of the MCU directly affects the speed of processing the attestation messages from peer devices. Therefore, a RA collaborative protocol that does not consider this gap in the hardware capabilities between devices will end up putting either an equal attestation load on different devices or a higher load on less capable devices. The number of proofs (i.e., attestations) that a node can receive and forward should thus be depending on its capabilities. The heterogeneity of the network can also threaten the lifetime of the services. Running a RA protocol on a device consumes a significant amount of its battery due to the frequent participation in the transmission and reception of attestation messages. Thus, if sensors with lower battery levels engage in many energy-consuming operations, this can end up with battery depletion of some devices causing potential disruption in the service. To this end, we see heterogeneity as a problem that can have a strong impact on both the performance and lifetime of a collaborative RA protocol.

Dynamic nature of IoT networks: With the continuous advancement of IoT applications, IoT networks gradually increase in size (i.e., new devices are added). In collaborative remote attestation, existing devices need to agree on keys with new devices to communicate. These keys ensures secure commination between devices to transmit their attestations. The existing solutions lack scalability and add a high overhead to the runtime of the RA protocol. Based on that, we identify the need for dynamic management and distribution of the key materials as a missing requirement for a practical remote attestation protocol.

FADIA -Overview

We present our approach to solving the problems mentioned in Section 7.2.3 (namely, heterogeneity and device addition). We design a lightweight collaborative RA protocol (FADIA).

To solve the heterogeneity problem, FADIA is designed with fairness in mind. In a collaborative RA protocol, we define fairness as the ability to distribute the load of the protocol according to the capabilities of the provers. The goal is to increase the performance of the protocol and to reach a better lifetime for the network. In a fair RA

LISA α [CERT17] O(log n) O(1) LISA s [CERT17] O(1)
O( 1)

DARPA [ISTZ16] O(n) O(n) SALAD [KBK18] O(n) O(n) PADS [ACL + 18] O(n) O(n) PASTA [KBK19] O(n) O(n) FADIA O(1) O(1)
protocol, provers in FADIA can be assigned a score depending on their capabilities and behave accordingly. This score will be frequently computed and the protocol should adapt to any change. In FADIA, similar to PASTA [KBK19], a group of provers collaborate and create a spanning tree in which parent nodes collect attestations from children nodes. However, in contrast to PASTA, the choice of the position and the number of children of a prover in the tree are adaptively regulated. These are determined by the scoring function which is computed based on the hardware capabilities (e.g., CPU) of the prover and its current residual battery. We, therefore, define a score function that outputs a score value between 0 and 1: when the score is closer to 1, the prover can assign more tasks with respect to the RA protocol (for example, the node can have a higher number of children).

To cope with the dynamic nature of the network, the protocol should support the addition of new devices at runtime. We propose to rely on an exisiting Eschenauer-Gligor's (E-G) scheme [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF] for the distribution of communication keys. In FADIA, each node is pre-loaded with a random keyring (a set of communication keys) randomly selected from the key pool. Devices that share at least one key in their keyrings can directly establish a secure communication channel. Thanks to this scheme, FADIA easily addresses the trade-off between the connectivity of the provers and the security of the communication. Furthermore, the addition of a new prover to the protocol does not require any modification of the other provers.

Building Block: Eschenauer and Gligor's Scheme

We present Eschenauer and Gligor's (E-G) [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF] scheme that is used in the design of our protocol. E-G key distribution scheme follows a probabilistic approach to efficiently distribute the keys over a large number of devices. It facilitates the addition and the revocation of nodes (and the corresponding keys) in the network without substantial computation and communication overhead on the end devices. The scheme defines a main key pool as a set of p keys of size. The participating devices pick a key ring as a random subset of size r from the key pool. Devices having at least one shared key from their key rings can communicate securely. This scheme has been shown to be simple and highly scalable and is, therefore, suitable for resource-constrained devices. In this work, we utilize E-G scheme to distribute the keys to the provers. Only provers who share common keys can establish secure communication channels.

Connectivity of the Provers Connectivity between provers is defined as the average percentage of provers, a prover can connect to (i.e., communicate with). The connectivity between provers using E-G scheme is equivalent to the probability of two provers sharing at least one key in their key rings (P s ).

P s = 1 - ((p -r)!) 2 (p -2r)!p! (7.1)
For example, with a key ring of size r = 300 and a key pool of size p = 100000 we obtain a connectivity of P s ≈ 0.6.

Assumptions and Threat Model

In this section, we describe the assumptions on the network. Then we define our security model.

Network Assumptions

We consider a mesh network topology where devices acting as provers, communicate within their communication range. Additionally, all provers are connected to a more powerful device (the controller C) acting as the verifier. For example, this can be an edge router. The network may contain more than one controller such that these controllers share their information and synchronize their data on a different layer. For the sake of simplicity, in this paper, we consider a single controller that connects to all provers in the network. Both, the provers and the verifier are managed by the network operator O.

The participating provers can have heterogeneous characteristics. Moreover, they can be static or mobile within the network. New provers may be added to the network at any point in time.

Security Model

Security assumptions: We assume that provers have the minimal secure hardware features to perform RA [START_REF] Francillon | A minimalist approach to remote attestation[END_REF]. Additionally, provers are equipped with loosely synchronized real-time clocks. The minimal secure hardware can be implemented using a secure Read-Only-Memory (ROM) to store the keys and a Memory Protection Unit (MPU) that stores FADIA's attestation code. The aforementioned execution space on each prover is referenced as the Trusted Anchor (T A ). Additionally, we assume that the controller is not compromised and is fully trusted. Furthermore, similar to previous research, FADIA only considers invasive and semi-invasive physical attacks. Thus, noninvasive attacks such as side-channel attacks are out of the scope of this paper. In this context, we rely on a common assumption that for an attacker to successfully bypass T A , it needs to take the devices offline for more than some δ h time which is predefined and known to be non-negligible [CDPG + 10, CDPMM08]. This is because such attacks require expensive and complex laboratory equipment and require the full possession of the target for a significant amount of time (from hours to weeks) [START_REF] Skorobogatov | Physical Attacks and Tamper Resistance[END_REF][START_REF] Skorobogatov | Physical attacks on tamper resistance: Progress and lessons[END_REF]. This becomes even more expensive especially when devices are equipped with tamper-resistant mechanisms [RRC04, ION + 18, MGGA17]. We finally assume that the implementation of FADIA and its cryptographic components do not suffer from any security bugs.

Adversarial Model: The main objective of an Adversary is to perform malicious activities by corrupting the memory of a prover and also damaging the network communication while being undetected. We consider two types of adversaries, Software Adversary A s and Hardware Adversary A h .

• A s has full control of the execution of a prover apart from the T A . It also has full access to the prover's memory except the memory protected by the MPU. Thus, A s can launch attacks like spoofing attacks, Man-in-the-middle-attacks, replay attacks.

• A h has, in addition to A s capabilities, physical access to the devices in the network. This provides it with the ability to leak any secret or modify FADIA's code on the targeted prover. However, this is only possible after turning the prover off for more than δ h time, as stated previously. δ h is defined by C for all provers participating in the protocol.

K ic ← KDF (K s , {K ID ∀ (K ID , K ) ∈ P i .Ring} ∪ {uid}) (7.2)
K ic is used in the later phases of the protocol to provide secure communication between a P i and the controllers. Moreover, O also defines a function score() which evaluates at the runtime the required load P i should take based on its hardware capabilities and its current capacity. This function outputs a value between 0 and 1 that indicates the amount of load P i can take (0 indicating that this device should take the least load possible, and 1 indicating that it should take the maximum load that can be given to one device). The implementation of score() depends on the underlying environment and application. For example, in the case of a network of wireless devices with batteries, the function score() will evaluate the battery percentage level of a prover; For a network of devices with microcontrollers of different computational speeds, score() will categorize different types of microcontrollers into different classes, and output a higher value for more powerful classes.

Joining Phase

Once P i is initialized, it can join the network. P i sends a join request message (jreq) to the controller (C) in the network. The join message contains its unique ID (uid) and the set of key ids in its key ring. This message is authenticated using a message authentication code (MAC) computed with K ic . Based on the received uid and the key ids, C computes K ic (see equation 7.2) and authenticates P i . Upon validation, C registers P i in the table of provers currently participating in the protocol. The table of registered provers records the current state of each prover (being either healthy or unhealthy) along with the last time the prover attested. P i is first registered as "healthy". C sends back a response message jresp (authenticated using K ic ) to confirm the joining process. jresp includes (i) cid: the controller's id (ii) δ h which corresponds to the maximum time a prover can stay active without attesting in the network, (iii) α g which defines the maximum number of attestations that can be aggregated, and (iv) c max that is the maximum number of score() and uses the result to decide on its role in an attestation tree. More specifically, P i updates two parameters namely, c limit and δ c :

• c limit is the maximum number of children P i can accept in the upcoming attestation tree.

c limit ← score() × c max

• δ c (which is less than δ h /2) is the amount of time P i waits to receive a participation invitation to an attestation tree. When δ c is reached and P i did not receive any invitation, it starts the tree construction protocol.

δ c ← score() × δ h /2
Neighboring provers that share common keys and are ready to provide their attestations construct a tree. Note that if a prover does not share any key with its neighbors, it directly sends the attestation to the controller. However, such cases appear with a low probability in realistic networks. For example, if the average number of neighbors for a prover is 5, and the connectivity P s = 0.6, then the probability of a prover being isolated is (1 -P s ) 5 ≈ 0.01. The tree construction and the attestation collection processes are described next.

Tree Construction

A tree construction starts by an initiator prover (P i ) after waiting for δ c time. The latter broadcasts an invitation message (invite) to its neighbors. The invitation message includes the unique id (uid) of P i as well as a tree id (treeid) (generated from a timestamp to guarantee freshness) and the set of key ids which P i holds in its keyring. When P j receives invite, it first checks if it did not attest in the last δ h /2 time. Then it checks if it shares at least one key with P i . Let K ij denote the shared key between P i and P j , and K ID ij be its corresponding key id. P j responds with an invitation acceptance message (iaccept) containing the key id K ID ij . The message also includes the unique ids of the source and the destination, the tree id sent by P i , and a random value (r) and a Message Authentication Code (MAC) computed using the shared key K ij . P i accepts P j as a child only if it has not acquired c limit children yet and responds with a child acceptance message caccept authenticated with the shared key concatenated with the random value (r). To this end, both provers established a secure channel with the shared key K ij . Next, P j either extends the tree and thus acts as an intermediate prover, or it finishes the tree construction process thus acts as a leaf prover. A prover acts as a leaf prover in two cases: either it does not accept any children (i.e., c limit = 0) or its invite message is timed out without receiving any response from its neighbors. The details of the tree construction messages are shown in Figure 7.3. The secure channels established between parent nodes and children nodes in the tree are used next to transmit the attestation messages.

When C receives the aggregated attestation it validates the proofs. For each set, it computes the MAC according to equation 7.3 using the unique keys (K jc ) of each prover P j . For each verified aggregated proof, the status of all provers in the set is updated. More specifically, C updates the time of the last proof received from these provers by the current time. We show the attestations collection details in Figure 7.4.

Key Revocation Phase

When prover P i becomes "unhealthy", it cannot be trusted anymore. So it is required by C to revoke all the shared keys between P i and the other provers. Since C knows the ids of all the keys in the keyrings of all provers, it can find out the affected devices (i.e., the ones which share at least a key with the "unhealthy" device). C sends a revocation message (revk) to each of them. The message contains the uid of the receiving prover, and the set of key ids that should be revoked. revk is authenticated with a MAC using K ic of the corresponding prover.

revk ← cid || uid || affectedKeys() (7.4)
When a prover receives revk, it removes the affected keys from its keyring. When the size of its keyring goes under a certain threshold θ, the prover goes to the offline state and requires reinitializing to go back online.

Role of the score function

The fairness by design approach can be achieved thanks to the tuning of mainly two parameters set with the help of the score function: c limit and δ c . this allows configuring the behavior and the computation load of each prover during the attestation phase and their correct setting hence ensuring a fair distribution of the load caused by FADIA on the active devices. The first parameter c limit represents the number of children a prover can hold during one attestation round in the virtual attestation tree. The number of children has a direct impact on the amount of load put on the prover. The load involves the use of cryptographic tools (MACs) to establish a secure channel with each child and forward the attestation proofs.

The second parameter δ c is the time at which a prover waits to receive the invitation message (invite) before it decides to start its own tree and sends invite itself. It is important to mention here that when a prover finishes an attestation round, it can switch to a sleeping state since it has completed its attestation for this round. Research on wireless ad-hoc networks has studied the scheduling of the nodes sleeping state to optimize the network lifetime [START_REF] Mahfoudh | Survey of energy efficient strategies in wireless ad hoc and sensor networks[END_REF]. Inlighted by these studies we control the sleeping time of a prover based on a fair policy. In FADIA for each attestation round, a prover is first actively waiting for invitation messages, then performs the requested attestation operation in the tree and finally switches to a sleep state until the next round. Consequently, δ c is a critical parameter that influences directly the average amount of time a prover spends in the sleep state and hence optimizes its resource consumption. Research has shown that being in an active state (listening or sending) can be intensively resource-consuming compared to being in a sleep state [START_REF] Kim | Smart sensing period for efficient energy consumption in iot network[END_REF]. Therefore, δ c parameter is also used to control the amount of load on a prover in FADIA.

In FADIA, these two parameters are calculated at runtime by each prover. Their corresponding values are updated at each round of the attestation phase using the score function. We present examples of how to build this function depending on the scenario of deployment in section § 7.8.3.

Security Analysis

The main goal of an adversary is to perform malicious activities and evade detection. However, a remote attestation scheme should identify the presence of malicious actors in the network to safeguard the network's operations. We consider the system secure if an attacker cannot forge a "healthy" state of a "non-healthy" prover. The remainder of this section informally discusses the security of FADIA w.r.t. adversarial assumptions mentioned in 7.5.

Attacks Performed by A s :

• Spoofing attacks: FADIA is immune to attackers trying to spoof a prover's identity.

Since all message exchanges are protected by keys stored in an inaccessible location for software attackers and can only be accessed through T A , an attacker will not be able to produce authenticated messages without the keys from the key ring. Please note that the invite message is an exception, as this message is not authenticated. However, this does not affect the security of FADIA since attackers spoofing this message will not be able to complete the 3-way handshake, (i.e., respond with a valid caccept).

• MITM attacks: FADIA will identify this attack as it suffers the same limitations as spoofing attacks. A s using this attack technique will not be able to manipulate messages without being detected since the integrity of these messages is ensured using the keys from the key rings that are protected by T A .

• Replay attacks: FADIA prevents replay attacks since all messages are unique and cannot be used twice without being detected. Specifically, freshness is guaranteed in invite messages thanks to using a timestamp in the treeid. Similarly, iaccept and caccept includes randomness for each prover-to-prover communication. Further, attst messages are also resilient to replay attacks since they contain a counter which is incremented at each attestation round.

• DoS Attacks: Although FADIA does not include these types of attacks in its threat model, it is worth noting that FADIA can detect the effect of such attacks. This is because A s performing DoS attacks on a prover (or prover group) will prevent the attestation of these provers. The controller will, therefore, inevitably discover a missing attestation from the provers under attack. Attacks Performed by A h In addition to software adversaries, hardware adversaries have the ability to tamper with a device to extract the keys from its keyring or alter the attestation code. Under the assumption that a hardware adversary needs to take the system offline for at least a δ h duration, FADIA provides resilience against these attackers. This is because FADIA requires that within every δ h period, each prover provides evidence of its "healthiness". This helps the network owner to ensure that the provers are not taken offline and thus not corrupted. On the other hand, a hardware adversary may use leaked keys to attack other provers sharing the same key. However, the key revocation process ensures that if a prover no longer participates in the protocol, these keys are revoked. Additionally, even if an attacker leaked all the key materials from a prover, the attacker will not be able to forge legitimate proof as this forgery involves the targeted prover's K ic . The state of a "unhealthy" device will thus not be forged by A h .

Performance Analysis

In this section, we evaluate the performance of FADIA in a heterogeneous network and demonstrate the advantages originating from its fairness-driven approach by evaluating the energy consumption, the computational cost and the bandwidth. We further study its performance in a homogeneous network and show that even in this case, FADIA outperforms the relevant state-of-the-art solutions, namely PASTA [START_REF] Kohnhäuser | A practical attestation protocol for autonomous embedded systems[END_REF] and SALAD [START_REF] Kohnhäuser | Salad: Secure and lightweight attestation of highly dynamic and disruptive networks[END_REF].

7.8. can be used for the Tmote Sky. We use HMAC-SHA256 for authenticating the messages and creating the proofs. We use the SHA256 of the device's firmware as the software configuration hash (sch).

In order to conduct our study, we first evaluate the cost of one attestation round for a prover in terms of the execution time and the energy consumption of FADIA. Since one round mainly involves MAC and hash computation operations, we have obtained some benchmarks on HMAC-SHA256 and SHA-256 respectively. Results are shown in Table 7.3. As expected, Tmote Sky takes more time to generate attestation proofs. We also benchmark the throughput and the round-trip time (RTT) of the CC2420 transceiver in a real environment. The throughput on the application layer is 25.2 Kbps and the RTT is 61.4 ms.

Environment for Experimental Evaluation

We first evaluate FADIA on a heterogeneous network to measure the influence of fairness on the performance in terms of energy consumption and computational cost. To evaluate the benefits of fairness, we consider two variants of FADIA. Variant (1) with fairness activated and variant (2) without fairness. Our results show that fairness improves the lifetime of the network and the runtime of the RA protocol. We then evaluate the performance of FADIA on a homogeneous network in terms of storage, computation and communication cost. Our results show that FADIA outperforms the state-of-the-art solutions. Additionally, we evaluate the robustness of FADIA against selfish provers. We also evaluate the efficiency of the revocation phase. We perform our simulations using the Omnet++ simulator [START_REF] Varga | An overview of the omnet++ simulation environment[END_REF]. We implement FADIA on the application layer of the devices1 . For the lower layers, we use a simplified medium access control version which makes sure that no device within the communication range transmits at the same time. Provers communicate in a half-duplex fashion and store messages in queues when the medium is busy.

Evaluation in Heterogeneous Networks

Test Case 1: Optimizing the energy consumption To measure the optimization of energy consumption, we simulate FADIA on 500 Tmote Sky sensors acting as provers. sch is set as the SHA256 hash of the firmware of size 30 KB. The network and cryptographic delays are set according to the values measured in Table 7 on the status of the transceiver and the microcontroller of the prover. The transceiver can either be transmitting, listening, or OFF. Similarly, the microcontroller can either be ON or idle. For each of the following statuses, the energy is computed according to the energy measurements shown in Table 7.4. The provers move in a random waypoint model at a linear speed uniform between 1mps and 2mps in a 300m × 300m area. Each of the provers is equipped with a battery of 1000J max capacity. The initial energy level a prover starts with is chosen randomly (uniformly [100J, 1000J]). Evaluation of different random distribution functions for the initial energy are shown in appendix B.1. Note that the maximum capacity of an alkaline AA battery is around 13, 000J. But we use 1000J as the maximum capacity for the seek of the feasibility of the experiment. We run FADIA for 60, 000 seconds. For variant [START_REF] Mansouri | FADIA: fairness-driven collaborative remote attestation[END_REF] returns 0.5. We measure the consumption of energy of each prover with respect to time. Figure 7.5a shows the energy traces of the provers in both variants of FADIA. As expected, variant (2) of FADIA (i.e. fairness is not activated), shows a fast depletion of the energy of all the provers while for variant [START_REF] Mansouri | FADIA: fairness-driven collaborative remote attestation[END_REF], most of the provers remain active after 40, 000 seconds. The reason for the fast depletion of energy in the "unfair" protocol (i.e. variant 2) is that provers with low energy are treated indifferently from high energy provers. This leads to putting a significant load on these devices due to the high (i.e. unfair) number of children they need to collect attestations from. Moreover, since δ c is not adapted to the energy level of the device, provers may spend more time waiting to be invited to a tree construction process. This keeps the transceivers of these devices in the listening state for a longer time instead of switching sooner to the OFF/idle state. This brings a serious problem since the part that mostly consumes energy in sensor devices is the transceiver. This is the case for Tmote Sky as shown in Table 7.4. Notice that, when provers with low battery crash, this decreases the number of provers in the network and causes fewer tree constructions to appear, causing a domino effect and faster depletion for other devices. Differently, in the case of FADIA variant (1), the low battery provers preserve their the energy which prevents the early loss of provers.

We also look into the consumed energy of the provers at the end of the experiment (i.e., after 16.6 hrs). We group provers that had similar initial battery levels at initialization and we measure their average consumed energy level after the experiment. Figure 7.5b shows the relation between the consumed energy with respect to the initial energy. The graph shows that provers with high initial battery levels (more than 50%) consumed more energy than provers with fewer initial battery levels thus providing a longer lifetime to the network. Additionally, we measure the time taken until we detect 1st, 3rd and 5th crash of a prover (i.e., its energy is completely depleted). We observe that the lifetime of the provers in a fair protocol is an order of magnitude longer.

Test Case 2: Optimizing the runtime To measure the optimization of the runtime achieved thanks to fairness, we evaluate the runtime of FADIA on heterogeneous static tree topology. In this scenario, we use two types of devices such that 50% of provers are Tmote Sky (MSP430) devices and the other 50% are Raspberry PI 2 devices. Both types of devices use the same transceiver (CC2420). We use the throughput, network delay, and the cryptographic delays for each type of device according to the benchmarks measured in table 7.3. We measure the time taken from the start of the tree construction until the final attestation is sent from the root node to the collector. The function score() is defined such that it returns 0.05 for the MSP430 provers and 1 for Raspberry PI provers. Accordingly, the number of accepted children (c limit ) will be 1 for the less powerful provers and 20 for the powerful ones. On the contrary, we simulate FADIA variant (2) which assigns 10 children for each prover regardless of its type. Figure 7.6 shows the runtime results of both approaches with respect to a varying number of provers in the network. The results show that FADIA with fairness option can run 1.6 faster in static topologies.

Evaluation in Homogeneous Networks

Memory consumption of FADIA Each prover in FADIA stores one key ring. The storage consumption derived from the key ring is (4B + 32B) × R, where R is the size of the keyring. The prover also stores uid (4B), the controller key k ic (32B), the attestation counter cntr (4B), and other FADIA parameters (20B). The total memory consumption is 56 + 36 × R Bytes. For example, with a key ring of size 300, this results in 10.6KB of memory. It is worth noticing that the memory consumption depends only on the key ring size and is independent of the number of provers on the network. This provides very high scalability compared to most of the state-of-the-art solutions that incur a cost linear to the number of provers. Our experimental study shows that FADIA can run on 10, 000 provers while each of them consumes only 10.6 KB which is significantly low compared to PASTA with 780KB of memory usage and SALAD with 365KB. Runtime of FADIA To measure the runtime for FADIA, we have implemented the protocol in a static network defined under four common topologies: the tree, chain, ring and grid topologies. We consider the construction of a single attestation tree where all provers participate in it. The running time is evaluated by measuring the time it takes until the report is collected by the controller. For a fair comparison with the state-ofthe-art, the scenario, the types of devices, the network delays and the cryptographic benchmarks are all set as the ones used in the evaluation of PASTA protocol in [START_REF] Kohnhäuser | A practical attestation protocol for autonomous embedded systems[END_REF].

We use ESP32-PICO-D4 devices in the simulation as provers and set the size of their firmware to 50KB. The throughput of the provers on the application layer is 12.51 MB/s and the round trip time is 4.63 ms. The time a device takes to generate the proof is set according to Table B.1 in the appendix. The provers perform 10 attestation rounds and the runtime of the attestation is averaged. The position of the nodes is randomized between rounds to force reinitialization of the tree construction. We set the keyring size r = 300, and α g = inf . Figure 7.7 shows the runtime results of FADIA and PASTA.

We observe that FADIA shows a low runtime in tree topologies. It can attest 1, 000, 000 provers in less than 2 seconds in a 4-ary tree. The runtime of FADIA and PASTA are close to each other in a tree topology since most of the attestation time corresponds to network delays. Moreover, FADIA shows better performance at higher degree trees because messages are broadcasted during the construction of the attestation tree, whereas for PASTA, one-to-one tree commitment requests are sent from the prover to its neighbors. Additionally, FADIA is faster than PASTA by approximately 17 times for grid topologies and 1.3 times for ring topologies. In grid topologies, the tree construction results in an unbalanced tree. This creates a problem for PASTA since the tree construction happens in two steps. In the first step, all provers first commit to the tree. Then in the second step, all provers receive the aggregated commitment. This requires all provers to wait for the tree construction to finish before they start attesting. FADIA does not have this problem since the leaf nodes can immediately send their attestations without waiting for the tree construction to finish. On the other hand, PASTA outperforms FADIA in chain topologies with a large number of provers (i.e., > 8000). This is explained by the fact that in FADIA, every prover sends all the key ids in the keyring to its neighbors which turns to be not effective in large chain topologies. Fortunately, such topologies do not often exist in real applications.

Bandwidth consumption of FADIA We evaluate the bandwidth consumption of FADIA in a dynamic network. We consider devices moving in a random waypoint model (i.e., provers choose random destinations and move toward them) at a linear speed uniform between 1mps and 2mps. The provers move in an area of 500m × 500m. We measure the average amount of data sent and received by a prover in an attestation round (i.e., for all provers to attest). Notice that the scenario, the device type, the network delays and the cryptographic benchmarks are all set the same as the ones used in the evaluation of SALAD protocol in [START_REF] Kohnhäuser | Salad: Secure and lightweight attestation of highly dynamic and disruptive networks[END_REF]. We use Stellaris LM4F120H5QR devices in the simulation as provers and set the size of their firmware to 30KB. The throughput of the provers on the application layer is set to 35.0 kbps and the round trip time is set to 15ms. The cryptographic delays are set according to Table B.1 in the appendix. We choose the value of α g as 1, 10, and infinity. We also use different values for the keyring and pool sizes: more specifically we set r = 100, p = 10, 000 and r = 300, p = 100, 000. Both cases give the same connectivity of the graph being P s = 0.6 (see 7.4). Figure 7.8 shows the results. In particular, the results show that FADIA has highly scalable bandwidth consumption since the data consumption is nearly constant with respect to the number of provers. It also shows that the bandwidth consumption depends mostly on the size of the keyring. However, this cost always remains less than the average consumption of SALAD increases linearly with the number of provers in the network.

Evaluation with Selfish Provers

We evaluate the impact of selfish provers on the lifetime of the network (time till 1st, 3rd and 5th crash of a prover). A selfish prover is a prover that does not will to participate in the tree-generation process. It thus greedily attests individually to the controller and goes to sleep state as early as possible. Note that such extreme selfish behavior can be easily detected. We consider this extreme case to evaluate the worst-case scenario. A more careful selfish prover will still collaborate however less than it is supposed to. We consider the same energy consumption scenario in Test Case 1 (see 7.8.3). However, selfish provers are chosen with an initial battery level greater than 250J. Figure 7.5c shows the results with different percentages of selfish provers. We observe that FADIA is robust against selfishness. This is because the lifetime drops significantly only when more than 40% of the provers are selfish. With a high number of selfish provers, the performance degrades since there is a sort of race toward the collector to provide attestation. This creates too much contention between provers accessing the wireless medium leading to the attestations being delayed.

Evaluation of the Revocation Phase in FADIA

The revocation phase starts when a prover is dropped from the network. The controller detects the event during the next δ h time and sends a revocation message revk to all the affected provers. To measure its efficiency, we evaluate the following:

• (E 1 ) The number of provers affected when a device is dropped.

• (E 2 ) The number of connections affected.

• (E 3 ) The number of keys revoked for each prover.

• (E 4 ) Time taken until all affected provers receive the revocation. E 1 is estimated as the number of provers in the network multiplied by the probability of two provers being connected (n × P s ). This means that the average number of affected devices is proportionally tied to the connectivity of the provers in the network. An example of a keyring of size 300 and a key pool of size 100,000 gives P s = 0.6, thus in this example 60% of the provers are affected by the revocation process. However, this is not a problem since most of the keys revoked at the prover are not actually used. Therefore, a more important metric to look into is the average number of connections affected (i.e., connections established using a key that is revoked). This is equal to c × r/p which estimates E 2 (c is the total number of connections established at the time of the revocation). Following our example, the averaged affected connections will be only 0.003 × c thus only 0.3% of the current connections need to be re-established. Third, E 3 estimates the expected amount of decrease in the size of a keyring on each revocation process and it is equal to the following: We demonstrate this equation in Figure 7.9a. The figure shows the relation between the average number of keys revoked per prover and the connectivity of the graph with respect to different keyring sizes and key pool sizes. We can see that for r = 300 and p = 100, 000, 0.8 keys are revoked per prover on average. It thus requires 190 provers to drop for an active prover to revoke half of its keys. Finally, to evaluate E 4 , we run a simulation in which we deploy FADIA in a network of provers and we set r = 300 and p = 100, 000. During the run of the protocol, we start the revocation process at a random point in time. We measure the time it takes till all provers receive the revocation message. We also consider cases where multiple revocations start simultaneously. Results are shown in Figure 7.9b. The revocation process increases linearly with the number of provers in the network and is performed within 34 seconds for 1,000 provers. When multiple provers are dropped simultaneously, the revocation time scales linearly with the number of dropped provers.

K i=0 i-1 j=0 (K -j) × K-i-1 j=0 (P -K -j)

Conclusion on Fairness-Driven Remote-Attestation

In this chapter, we proposed FADIA, a lightweight collaborative attestation protocol that can be deployed on heterogeneous networks of IoT devices. FADIA is the first RA protocol that integrates fairness in its design and deploys a scalable key management mechanism based on E-G scheme. We show that fairness is an important feature of remote attestation protocols. It can increase the performance of the protocol by a factor of 1.6 in a network where Tmote Sky sensors and Raspbery PIs coexist. Additionally, the lifetime of the network can increase by an order of magnitude, thus achieving fewer failures. We also show that FADIA outperforms the state-of-art solutions in terms of scalability on networks of a large number of provers. Finally, we evaluated the efficiency of the key revocation in FADIA. Our results show that the key management in FADIA offers a good tradeoff between the efficiency of adding and removing provers to the network.

Chapter 8

Final Conclusion and Future Work

Conclusion

In this thesis, we have studied the design of security protocols that are suitable for IoT. We focused on two security protocols: Secure Aggregation and Remote Attestation. We observe that the existing secure aggregation protocols suffer from several limitations when used in IoT context. Namely, the existing SA protocols do not consider malicious users. We argued that this type of solution does not fit IoT use cases since the devices may be compromised. Moreover, we identified that existing SA protocols do not cope with the dropouts of users. This poses a limitation for these solutions due to their large scale where failures of some devices are inevitable. On the other hand, we observe that existing remote attestation protocols are also not suitable for IoT. The major challenges facing the efficient design of RA protocols are the heterogeneity of IoT devices and the dynamic nature of the IoT network. Therefore, this thesis proposed solutions that fix the limitations of the existing work for secure aggregation and remote attestation.

For secure aggregation protocols, we proposed VSA as a new secure aggregation protocol that considers a stronger threat model than existing SA protocols. VSA preserves the privacy of the users' input and guarantees the correct computations of the aggregation result even when the aggregator and few users are acting maliciously. To design VSA, we built over an existing work (PUDA [LE ÖM15]) which considers only a malicious aggregator and uses user-generated tags to verify the aggregation result. To cover the case of malicious users, we integrated a newly designed tagging protocol into PUDA. Our tagging protocol (which is secure in the malicious model) involves new entities called taggers that issue the tags. The tagging protocol guarantees that only honest users receive valid tags for their inputs. Therefore, thanks to the tagging protocol, VSA ensures that neither the malicious users nor the malicious aggregator can produce an incorrect aggregation result.

Additionally, we proposed FTSA as a new secure and fault-tolerant aggregation protocol dedicated to federated learning application. FTSA allows a robust computation of the aggregation result even when some users drop during the aggregation process. To build our new solution, we improved the Joye-Libert secure aggregation scheme (JL [START_REF] Joye | A scalable scheme for privacy-preserving aggregation of time-series data[END_REF]) and proposed a threshold variant of it (TJL). Our new TJL uses an Integer Secret Sharing scheme (ISS see Section 2.3.1) and it allows a threshold number of users to protect a zero-value on behalf of other users. FTSA leverages TJL scheme to recover the aggregation result by enabling online users to submit protected zero-value on behalf of the offline ones. We deployed FTSA in the context of federated learning and compared it with the state-of-the-art. Our evaluation showed that FTSA can scale better than all existing solutions and it achieves the theoretical limit in terms of scalability with respect to both the number of users and the size of the machine-learning models.

Last and not least, we proposed FADIA as a new collaborative remote attestation protocol with fairness integrated into its design. FADIA enables the fair distribution of attestation load/tasks to achieve better performance. We show that fairness is an important feature for remote attestation protocols. Fairness can increase the performance of the protocol by a factor of 1.6 in a network where Tmote Sky sensors and Raspbery PIs coexist. The lifetime of the network can increase by an order of magnitude, thus achieving fewer failures. We also show that FADIA outperforms the state-of-art-solutions in terms of scalability.

Future Work

In this thesis, we studied secure aggregation and remote attestation protocols. Possible future research directions to investigate for each of the solutions can be listed below:

• The verifiable secure aggregation protocol (VSA) proposed in this thesis is secure under static corruptions. To achieve security under adaptive corruptions we need to improve the design of our protocol to cover adversaries that may corrupt honest users during the execution of the protocol. In the current design, we build our tagging protocol over an OT protocol [START_REF] Chou | The simplest protocol for oblivious transfer[END_REF] which is secure in the static corruption model.

To replace this protocol with an OT protocol secure under adaptive corruptions, we need a technique to still be able to compute the tags from the OT messages as done in the current design.

• The verifiable secure aggregation protocol (VSA) proposed in this thesis verifies the users' inputs by checking that they are less than an upper bound. In some applications, it might be required to check a more complex condition on the inputs. Fortunately, our solution uses garbled circuit to implement this condition which can be generalized to a circuit that checks any predicate. It is interesting to study what predicates are useful for secure aggregation and their implementations.

• The fault-tolerant secure aggregation protocol (FTSA) proposed in this thesis presents a method to compute protected inputs on behalf of offline users. To achieve fault tolerance in the case of verifiable secure aggregation solutions, it is possible to use the same approach to compute the tags on behalf of offline users. However, we need some distributed zero-knowledge proof techniques to prove that the computed ciphertext is an actual protection of zero-value.

• In this thesis, we studied secure aggregation as a solution to preserve the privacy of clients in federated learning. However, as discussed in Chapter 5, secure aggregation should be used with differential privacy to achieve better privacy guarantees. Thus, studying the suitability of differential privacy techniques with secure aggregation is an interesting area of research that complements our work.

• The collaborative remote attestation protocol (FADIA) proposed in this thesis improves the performance of the RA by optimizing the management of the attestation between provers. Research work on the trusted execution environment which runs the attestation code and the integrity-checking algorithm can also lead to a significant improvement of RA protocols for IoT.

  PRG(m, R, b) → B: is a pseudo-random generator that extends seed b ∈ {0, 1} λ to vector B ∈ Z m R (vector of m elements and each element is in Z R ). Definition 2.3.8: Security Given the two distribution D 1 : {A} such that A ←$ Z m R and D 2 : {B} such that B ← PRG(b) where b ←$ {0, 1} λ and λ is a large security parameter, it holds that D 1 c ≈ D 2 .

Figure 2 . 1 :

 21 Figure 2.1: Ideal functionality of CRS

Figure 2 . 2 :

 22 Figure 2.2: Ideal functionality of random secret sharing

Figure 2 . 3 :

 23 Figure 2.3: Ideal functionality of oblivious transfer protocol.

Figure 2 . 6 :

 26 Figure 2.6: Ideal functionality for zero-knowledge protocol.

Figure 3 . 1 :

 31 Figure 3.1: An illustration of secure aggregation between n users (U 1 , ..., U n ) and one aggregator A. A trusted party T P is used to setup up the parties.

Figure 3 . 2 :•

 32 Figure 3.2: The main operations and communication between parties in Masking-based SA.

Figure 3 . 3 :

 33 Figure 3.3: The main operations and the communication between parties in AHE-based SA.

Figure 3 . 4 :

 34 Figure 3.4: The main operations and the communication between parties in FE-based SA.

Figure 3 . 5 :

 35 Figure 3.5: The main operations and communication between parties in MPC-based SA.

  Most of the existing work focus either on the malicious aggregator model [LE ÖM15, TLB + 21, HKKH21] or the malicious users model [KOB21, CGB17, BLV + 21].

Figure 4 . 1 :

 41 Figure 4.1: PUDA protocol. The aggregator is malicious and users are honest.

  4.5.1Let P r[A AO ] denote the probability that the adversary A outputs b * = b. Then, VSA is said to ensure Aggregator Obliviousness if for any poly-bounded adversary A the probability P r[A AO ] ≤ 1 2 + µ(λ), where µ(λ) is a negligible function and λ is the security parameter.

Figure 4 . 2 :

 42 Figure 4.2: Ideal functionality for a Distributed Tagging Protocol.

2Figure 4 . 3 :

 43 Figure 4.3: Our verifiable secure aggregation protocol. All parties can be malicious and may collude except a threshold number taggers.

3 .

 3 During the Challenge Phase: B outputs what A outputs.

Figure 4 . 5 :

 45 Figure 4.5: Ideal functionality for a Tagging Protocol.

Figure 4 .

 4 Figure 4.6: Distributed Tagging Protocol in F G TAG -hybrid model.

Theorem 4 .9. 2

 42 Protocol Π GTAG UC-realizes the functionality F G TAG in the F R ZK -hybrid model under static corruption and under the Inv-DDH assumption in G.

Case 1 :

 1 A corrupts the user U 1. S first chooses θ = 2 ℓ -1 (largest bound possible). It garbles the circuit similar to an honest tagger F, {l b

Figure 4 .

 4 Figure 4.7: Tagging Protocol in F R ZK -hybrid model. Black text is the GC part and Blue text is the modifications. Recall that timestamp τ =sid represents the session id.

  and E ′ =E, and the relation R Tag holds, S sends (sid,True) to A, otherwise send (sid,False) to A and (sid, abort) to F G TAG .

  and E ′ ̸ =E, or the relation R Tag does not hold, send (sid, abort) to F G TAG . Otherwise, S chooses θ = 2 ℓ -1 and then sends the message (sid, input, k = (a, b), θ) to F G TAG .

  Figure 5.1: One federated learning round with three FL clients and one server.

  Figure 5.2: A secure aggregation protocol integrated into federated learning. The secure aggregation protocol ensures that the aggregators do not learn anything about the clients' locally trained ML models except their aggregate.

Figure 5 . 3 :

 53 Figure 5.3: Summary of existing FL solutions that use crypto-based secure aggregation grouped by the type of secure aggregation used and the specific challenge they tackle. Bordered boxes indicate that the solution presents a technique that can be deployed in other types of SA protocols (eg., [XLL + 20] is implemented on masking-based SA but can be also used for AHE-based SA). Hatched boxes indicate that the scheme cannot achieve the security requirements since they do not support collusions (this is discussed in Section 5.5). Different colors represent research groups of the authors.

  To deal with the floating point challenge while preserving good accuracy, researchers propose to use different quantization techniques. Elkordy et al. [EA20] and Bonawitz et al. [BSK + 19] propose to use auto-tuned quantization. This technique allows adapting the quantization level of the model vector based on the requirements. More specifically, for some elements of the trained model that do not have a large impact on its accuracy, this technique reduces the quantization level which consequently reuced the communication cost. Auto-quantization is integrated with FT-Masking [BIK + 17]. Alternatively, in [BT20], Beguier et al. propose a quantization technique called TopBinary quantization. This technique is essentially a combination of top-k sparsification [SCJ18] with 1-bit quantization [BWAA18]. We observe that these quantization techniques is that they can be used for all categories of secure aggregation protocols. Scalable Secure Aggregation To tackle challenge C 4 , scalability of SA started to gain researchers' attention thanks to the new large-scale applications of FL. Bonawitz et al. [BEG + 19] set up a general framework to scale a secure aggregation framework to millions of devices. The authors propose to simply run multiple instances of the scheme, one for each subgroup of clients. Each subgroup computes intermediate aggregates which are combined later. The same intuition of grouping clients is followed up by Bell et al. [BBG + 20] and by So et al. [SGA21b]. Bell et al. observe that the FT-Masking scheme in [BIK

Figure 5 . 4 : 1

 541 Figure 5.4: New Components of Secure Aggregation

Figure 6 . 1 :

 61 Figure 6.1: Demonstration of an execution of TJL scheme with four users (n = 4) and a reconstruction threshold t = 2.

Figure 6 . 3 :

 63 Figure 6.3: Detailed description of the online phase of FTSA

2 = n+|Ucorr| 2 shares

 22 and |U corr | shares of b i,τ . Additionally, for the remaining U \ U corr honest clients, the adversary's best strategy is to set U i as online for half of them and set it as offline for the other half. It thus receives shares of Y ′ τ of U i from n-|Ucorr| 2 honest clients and shares of b i,τ from the other n-|Ucorr| 2 honest clients. Hence, in total, the adversary can learn a maximum number of |U corr | + n-|Ucorr| of Y ′ τ and b i,τ of the same client.

Figure 6 . 4 :

 64 Figure 6.4: The wall-clock running time (a,b) and the total data transfer sent and received (c). The measurements are performed using a single-threaded python implementation of our solution and the solution in [BIK + 17] (only the online phase time is shown). When varying the number of clients, we fix the input dimension to m = 100K and when varying the dimension we fix the number of clients to n = 300. Bars represent the average value based on 10 runs and the error margins represent the standard deviation.

Figure 7 . 1 :

 71 Figure 7.1: Illustration of an remote attestation execution between a prover and verifier .

. 3 .Figure 7 . 5 :

 375 Figure 7.5: Evaluation of the energy consumption. (a) the residual energy over time. w/ (left side) and w/o (right side) activating fairness. (b) the average consumed energy w.r.t. initial energy after 16.6 hours of running FADIA with fairness activated. The green-colored area represents the residual energy and the orange-colored area represents the consumed energy at the end of the experiment. (c) the time taken until 1st, 3rd, and 5th crash (energy depletion at a prover) with different percentages of selfish provers in the network. Dotted lines represent the results when fairness is not activated.

Figure 7 . 6 :

 76 Figure 7.6: Runtime of FADIA with (in green) and without (in orange) fairness integrated in dynamic network.

Figure 7

 7 Figure 7.7: Runtime of FADIA and PASTA with a different number of provers in tree, grid, chain, and ring topologies.

  Figure 7.8: Average amount of data sent by a prover during one round of attestation in FADIA and SALAD protocols.

  Figure 7.9: Revocation efficiency. (a) shows the number of revoked keys per prover with respect to different key ring sizes. (b) shows the average amount of time taken till the revocation process is completed with respect to a variable number of provers in the network.

Table 2 .

 2

1: Common Notations

  al. [SCR + 11]. We state this security requirement in Definition 3.2.1. The second requirement is Aggregator Unforgeability and it was initially proposed by Leontiadis et al. [LE ÖM15] and improved later in several other works. We state this security requirement in Definition 3.2.2. This security notion ensures that an adversary (by corrupting the aggregator) cannot learn more than what could be learned from the sum of the users' inputs. If the adversary corrupts some users, the notion only requires that the adversary gets no extra information about the values of the honest users beyond their sum.

	Definition 3.2.1
	Aggregator Obliviousness: Definition 3.2.2

Shi-Chan-Rieffel-Chow-Song Scheme (SCRCS) SCRCS scheme [SCR + 11] is the first AHE scheme used for secure aggregation. It guarantees Aggregator Obliviousness based on Decisional Diffie Hellman (DDH) assumption. The three algorithms

  (AHE.Setup, AHE.Enc, and AHE.Agg) are defined as follows:• AHE.Setup(λ) → (pp, {k i } i∈[n] , k 0 ): Given security parameter λ, it chooses generator g ∈ Gwhere G is a cyclic group of prime order p for which DDH holds. Additionally, it defines the hash function H G (see Section 2.4.3). It also generates n random secrets k 1 , ..., k n ∈ Z p and k 0 = -n 1 k i . It outputs the public parameters pp = (G, g, H G ), the secrets keys of each user {k i } i∈[n]

τ mod N SA.Setup (offline) SA.Protect SA.Agg

	Setup	Enc	DKGen
	...
			Dec

  MIFE.Dec(pp, dk τ , c τ , y τ ) → IP (x τ , y τ ) : It takes vector c τ = [c 1,τ , .., c n,τ ], vector y τ , and decryption key dk τ generated from y τ . It decrypts c τ such that the result is the inner product of x τ = [x 1,τ , .., x n,τ ] and y τ .MIFE schemes for inner product can be used to construct a secure aggregation protocol [XBZ + 19,WPX + 20]. In the SA.Setup phase, T P runs MIFE.Setup(λ) and distributes the keys to the users. In the SA.Protect phase, U i executes MIFE.Enc(pp, k i , x i,τ ) and sends the ciphertext c i,τ to the aggregator. Finally, in the SA.Agg phase, the aggregator first sends vector y τ = [1, ..., 1] to T P which executes MIFE.DKGen(pp, msk, y τ ) and sends decryption key dk τ of timestamp τ to the aggregator. The aggregator then executes MIFE.Dec(pp, dk τ , [c 1,τ , .., c n,τ ], y τ ) and retrieves the inner product n i=1 x i,τ y[i] =

	SA.Setup (offline)	SA.Protect	SA.Agg
		Share	Recon
		...
	n 1 x i,τ .
	Construction based on one-time pad An efficient FE-based secure aggregation can be
	built using one-time pad encryption and a pseudo-random generator, only. The MIFE
	scheme from [ACF + 18b] defines the four algorithms (MIFE.Setup, MIFE.Enc, MIFE.DKGen,
	and MIFE.Dec) as follows:
	• MIFE.Setup(λ) → (pp, msk, {k i } i∈[n] ) : Given security parameter λ, it chooses
	prime p and a pseudo-random generator PRG : (Z p , Z) → Z p as the public parameter
	then chooses n user keys at random k i ← Z p ∀i ∈ [n]. Finally it sets the master key
	msk = {k i } i∈[n] .
	• MIFE.Enc(pp, k i , x i,τ ) → c i,τ : It first computes k i,τ ← PRG(k i , τ ) then c i,τ ←
	x i,τ + k i,τ mod p
	• MIFE.DKGen(pp, msk, y τ ) → dk τ :
	dk τ ←	y i,τ PRG(k i , τ ) mod p
	∀k i ∈msk
	• MIFE.Dec(pp, dk τ , c τ , y τ ) → IP (x τ , y τ ) :
	IP (c τ , y τ ) -dk τ mod p

Table 3 .

 3 1: Table comparing the baseline constructions of the different categories of secure aggregation. T P stands for trusted third party. SC stands for pre-established secure

channels. Dynamic users property shows whether the aggregation can be performed with a subset of the users, only. Comp. stands for computation cost on users. Comm. stands for communication cost between users and aggregators. n and m represent the number of users and the size of the user's input, respectively.

  Type III Forgery: VSA.Verify(vk, sum τ * , Υ τ * ) = 1 and A made queries with timestamp τ * , however the sum sum τ * > ∀U i ∈U \Ucorr x i,τ * + |U corr |θ min . AU III ] denote the probability that the adversary A outputs a tuple that satisfies Type I, II, and III Forgery respectively. Then, VSA is said to ensure Aggregate Unforgeability if for any poly-bounded adversary A the probability P r[A AU ] = P r[A AU I ] + P r[A AU II ] + P r[A AU III ] ≤ µ(λ), where µ(λ) is a negligible function and λ is the security parameter. Definition 4.5.2 features stronger security guarantees than PUDA. First, it captures the Type I and II Forgeries that represent a corrupted aggregator forcing an incorrect sum, but this time, even when a corrupted aggregator colludes with corrupted users. Second, it captures a new type of forgery Type III Forgery that represents corrupted users adding invalid inputs to the sum.

	Definition 4.5.2
	Let P r[A AU I ], P r[A AU II ], and P r[A

•

  When (sid, input) is received from U and all T

j , set tk ← (a, b) such that a ← SSS.Recon({(j, ⟨a⟩ j )} ∀j|T j ∈T h , Z p ) and b ← SSS.Recon({(j, ⟨b⟩ j )} ∀j|T j ∈T h , Z p ). Finally, check if x ≤ min{θ j } ∀j|T j ∈T h . If yes, compute σ ← PUDA.Tag(tk, x, sid a ). If no, set σ ←⊥. Send (sid, output, σ) to U and halt.

a The session id (sid) is the current timestamp (sid=τ )

  4.8.1 For any ϵ > 0 and poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them where P r[A AO ] ≤ 1 2 + ϵ there exists a poly-bounded adversary B that statically corrupt U corr ⊂ U and/or A such that P r[B AO PUDA ] ≥ 1 2 + ϵ. Notice that this reduction is only true when the adversary does not corrupt t or more taggers (|T corr | < t). To prove this reduction, we construct the adversary B using A. Let us denote the oracles that B has access to by O PUDA Setup , O PUDA Corrupt , O PUDA EncTag , and O PUDA It then queries O PUDA Corrupt with each user identifier i of the corrupted users U i ∈ U corr which returns {(ek i , tk i )} ∀U i ∈Ucorr . B samples uniformly at random a ′ ←$ Z p and b

	Proof.

AO

defined in

[LE ÖM15

]. B proceeds as follows:

1. During the Setup and Corruption Phase: Given that the corrupted parties in U corr ∪ T corr ∪ {A}, when A chooses the security parameter λ and the threshold t, B queries O PUDA Setup which returns pp, ak, and vk.

  Challenge Phase: When A queries O AO with some parameters, B queries O PUDA AO with the same parameters then gives the result to A and outputs what it outputs.In this reduction, the difference between A's simulated view (by B) and A's real view (when it plays the real game) is only the tagging keys' shares of the corrupted taggers. Since A does not see a sufficient number of shares (because |T corr | < t), the shares from both views are indistinguishable (see Security definition of Shamir's secret sharing in section 2.3.1). Therefore, if A outputs b * = b (wins VSA AO game) with a probability 1 2 + ϵ, B will also output b * = b (win PUDA AO game) with the same probability. This proves the lemma.For any ϵ > 0 and poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them where P r[A AU I ] + P r[A AU II ] ≤ ϵ there exists a poly-bounded adversary B that statically corrupt A such that P r[B AU PUDA ] ≥ ϵ. Notice that this reduction is only true when the adversary does not corrupt t or more taggers (|T corr | < t). To prove this reduction, we construct the adversary B using A. Denote the oracles that B has access to by O PUDA Setup and O PUDA EncTag defined in [LE ÖM15]. Notice that B does not have access to oracle O PUDA Corrupt since in PUDA the aggregator is not allowed to collude with the users. However, B should provide A with the encryption keys of the corrupted users. It turns out that B can simply generate a random encryption key for each user and use that key to produce ciphertexts instead of using O PUDA It then samples the user encryption keys uniformly at random for all users rk i ←$ Z p such that

	Lemma 4.8.2
	Proof.

EncTag (B needs O PUDA EncTag to only produce the tags). In more detail, B proceeds as follows: 1. During the Setup and Corruption Phase: Given the corrupted parties are U corr ∪ T corr ∪ {A}, B queries O PUDA Setup which returns pp, ak, and vk. i∈[n] rk i = -ak. It also samples a ′ ←$ Z p and b ′ i ←$ Z p uniformly at random for each i ∈ [n]. Then it computes SSS.Share(a ′ , t, m, Z p ) and SSS.Share(b ′ i , t, m, Z p ) for each i ∈ [n]. It sets TK j

  ak thus, they are statistically indistinguishable.We conclude that the simulated view of A (by B) and the real view of A are statistically indistinguishable. Hence, if A succeeds in producing a Type I or II Forgery with probability ϵ then B succeeds with the same probability. This proves the lemma.For any poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them, VSA achieves Aggregator Obliviousness under the decisional Diffie-Hellman (DDH) assumption in G 1 in the random oracle model and F t,G 1 For any poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them, VSA scheme achieves Aggregate Unforgeability against a Type II Forgery under the LEOM assumption in the random oracle model and F t,G 1 DTAG -hybrid model. Since PUDA ensures aggregate unforgeability against Type II Forgery under the BCDH assumption in the random oracle model, and since our AU game reduces to AU PUDA game (see Lemma 4.8.2), we can conclude directly that our scheme also ensures aggregate unforgeability against Type II Forgery under the LEOM assumption in the random oracle model and F t,G 1 DTAG -hybrid model.

	Corollary 4.8.3
	Proof.
	Corollary 4.8.1
	Proof.
	Since PUDA ensures aggregate unforgeability against Type I Forgery under the BCDH
	assumption in the random oracle model, and since our AU game reduces to AU PUDA
	game (see Lemma 4.8.2), we can conclude directly that our scheme also ensures
	aggregate unforgeability against Type I Forgery under the BCDH assumption in the
	random oracle model and F t,G 1 DTAG -hybrid model.

DTAG -hybrid model.

Proof.

Since PUDA ensures aggregator obliviousness under the DDH assumption in G 1 in the random oracle model, and since our AO game reduces to AO PUDA game (see Lemma 4.8.1), we can conclude directly that our scheme also ensures aggregator obliviousness under the decisional Diffie-Hellman (DDH) assumption in G 1 in the random oracle model and F t,G 1 DTAG -hybrid model. Corollary 4.8.2 For any poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them, VSA scheme achieves Aggregate Unforgeability against a Type I Forgery under the BCDH assumption in the random oracle model and F t,G 1 DTAG -hybrid model. Theorem 4.8.1 For any poly-bounded adversary A that statically corrupts U corr ⊂ U, A, or T corr ⊂ T s.t. |T | < t (t is the SSS threshold ), or any combination of them, VSA scheme achieves Aggregate Unforgeability against a Type III Forgery under the LEOM assumption in the random oracle model and F t,G 1 DTAG -hybrid model. Proof. Let us assume that sum τ * > ∀U i ∈U \Ucorr x i,τ * + |U corr |θ min . This gives us that ∀U i ∈Ucorr x i,τ * > |U corr |θ min . Notice that in this case the probability that VSA.Verify(vk, sum τ * , Υ

  TAG that runs between one user and one tagger only. The ideal functionality F G TAG is shown in Figure4.5. Notice that F G TAG is very similar to F t,G DTAG (with one tagger) except that the adversary in F G TAG is allowed to perform a selective failure attack (i.e., choose to abort the protocol on certain inputs from the honest user). Given the functionality, F G TAG , the protocol Π t,G DTAG is defined in the F G TAG -hybrid model as shown in Figure4.6.

	User	Tagger	User	Taggers
					...
		(	)	(	)
	if	:	if	:	...
	Figure 4.4: Overview of the tagging and distributed tagging functionalities
	with ideal functionality F G
	Theorem 4.9.1
	Protocol Π t,G
	t,G DTAG ≡ VSA.Tag that realizes the DTAG . To build this protocol, we first propose a tagging protocol Π G functionality F t,G TAG

DTAG UC-realizes the functionality F t,G DTAG in the F G TAG -hybrid model under static corruption if the number of corrupted taggers |T corr | < t and |T corr

  G TAG UC-realizes the functionality F G TAG in the F R ZK -hybrid model under the Inv-DDH assumption in G if A statically corrupts U . Case 2: A corrupts the tagger T 1. When A sends the message (sid,γ, A = g α , F ), S chooses x=1 (smallest input possible) and proceeds similarly to an honest user to compute {B i } ∀i∈[ℓ] , {P i } ∀i∈[ℓ] , and Q. S sends (sid,{B i , P i } ∀i∈[ℓ] , Q) to A. 2. S sends the message (sid,prove,({(B i , P i )} i∈[ℓ] , (H(sid), Q)), r) to F

	R ℓ+1 DL ZK	and
	waits for A to sends (sid,({(B ′ i

  al. [SSV + 21] that replaces the standard masking with a Learning With Error masking and uses a packed and verifiable version of Shamir's secret sharing. Also, Yang et al. propose LightSecAgg [YSH + 21] which replaces the Shamir's secret sharing scheme with a secret sharing scheme based on Maximal Distance Separable (MDS) code [RL89]. The work of Yang et al. reduces the computation time at the server. Another approach is proposed by Swanand et al. [KRKR20] that uses Fast Fourier Transform (FFT) for secret sharing. Communication Efficient Secure Aggregation Researchers propose some techniques to bound the communication overhead incurred by SA (see C 2 ). For AHE-based SA, batch encryption has been leveraged by Liu et al. [LCV19], Phong et al. [PAH + 18], and Yang et al. [ZLX

  21]. For masking-based and AHE-based SA, Zhang et al. [ZFW + 20] and Xu et al. (Veri-fyNet) [XLL

  So et al. propose TurboAgg[START_REF] So | Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning[END_REF] which uses additive secret sharing instead of Shamir's secret sharing. To achieve robustness against dropouts, Lagrange coding[START_REF] Yu | Lagrange coded computing: Optimal design for resiliency, security and privacy[END_REF] is used. The main drawback of the scheme is that it divides the clients into groups and each client in a group needs to communicate with every other client in the next group. Therefore, the communication cost of TurboAgg is relatively high. Additionally, the protocol can fail to recover the aggregate value when some clients drop with a non-negligible probability.

	6.3.4 FastSecAgg

Kadhe et al. propose FastSecAgg [KRKR20] which uses FastShare instead of Shamir's secret sharing. FastShare is a new cryptographic primitive proposed by the same authors.

Table 6 .

 6 3: Wall-clock running time per client in the online phase for one FL round with different % of client failures. The number of clients varies n = {100, 300, 600, 1000} and the dimension is fixed to m = 100K.

	TP	Setup		12 / 10 11 / 15 13 / 13
	User	SkShare ShareProtect Protect	-/ 2 -/ 7 4 / 4	-/ 23 -/ 14 4 / 4	-/ 149 -/ 26 4 / 4
	Agg	ShareCombine Agg	-/ 88 4 / 8	-/ 946 -/ 4220 5 / 21 7 / 42
	# Clients	0%	% Failures 10% 20%	30%
		100	9.8 sec 20.9 sec 20.8 sec 20.8 sec
		300	10.9 sec 28.1 sec 27.9 sec 26.6 sec
		600	10.5 sec 35.5 sec 35.6 sec 35.8 sec
		1000	10.7 sec 51.6 sec 51.2 sec 52.1 sec
	running time with different failure rates of clients (with 0% failure rate the runtime is
	negligible since there is no need for a recovery phase which is the most costly operation).

  , SPvK04, LMP11, SLS + 05, KJ03] Softwarebased attestation relies on assumptions concerning the software implementation of the attestation code. An example of software-based attestations is Pioneer [SLS + 05]. Pioneer computes a checksum of device memory using a function that includes side effects in its computation, such that any emulation of this function incurs a timing overhead sufficiently long to detect cheating. Software-based attestation is useful only if the verifier and the prover are directly connected (without passing through intermediate hops)[START_REF] Castelluccia | On the difficulty of software-based attestation of embedded devices[END_REF], thus impractical as a remote attestation technique.

Table 7 .

 7 1: Comparison between previous work on collaborative remote attestation and FADIA. The big O notation represents the complexity of the cost on a prover with respect to n (number of provers in the network).

		Scalability				Supported Features
	Communi-	cation Cost	Storage	cost	Mobility	Detects	hw attacks	Autono-	mous	Adding	Devices	Fairness
	SEDA [ABI + 15] O(1)	O(1)
	SENA [ACI + 16] O(1)	O(1)

  In line with other RA schemes [ABI + 15,ACI + 16,KBK19,ACL + 18] we do not consider Distributed Denial of Service (DDoS) attacks. Nevertheless, in Section 7.7 we mention possible ways to detect DDoS attacks in FADIA.

	(Joining prover)		(Controller)
	joinReq():
		handleJoinReq	:
	authSend	If	KDF MAC	Then:
		registerProver
		authSend
	startAttesting():	Else:
	...	ignoreRequest()
	Figure 7.2: FADIA's joining phase
	derivation function (KDF) and a secret key (K s ) known only by O and the controller.
	More formally,
	Definition 7.5.1: Security
	FADIA is considered secure if an adversary (under the aforementioned assumptions)
	cannot forge a "healthy" state of a compromised prover.

Table 7 .

 7 3: Benchmarks and energy consumption measurements of cryptographic functionalities of FADIA when implemented on Tmote Sky and Raspberry PI 2 devices.

			HMAC-SHA256		SHA256
			Time (ms) Energy (mJ) Time (ms) Energy (mJ)
		32 B	0.068	-	0.025	-
	PI 2	4 KB 8 KB	1.075 2.083	--	1.049 2.032	--
		32 KB	8.131	-	8.079	-
		32 B	63.28	0.3384	15.54	0.0862
	SKY	4 KB	1035	5.5908	988	5.3388
		8 KB	1998	10.7892	1960	10.6128

  1 Implementation of FADIA on Tmote Sky and Raspberry PI 2 GHz and is compliant with IEEE 802.15.4 standards. We do not follow a certain security architecture for implementing FADIA on the devices. However, FADIA can be implemented based on any security architecture. Previous research has shown that achieving a security architecture on sensor devices is indeed possible [EFPT12, BES + 15, DRT17, NBM+ 17]. In our implementation, and without loss of generality, an ARM TEE can be used for the Raspberry PI, and TYTAN [BES+ 15]

	The CC2420 chip operates on 2.4
	To illustrate heterogeneity, we implement FADIA on two types of devices: Tmote
	Sky [Cor16] and Raspberry PI 2. The Tmote Sky which represents a resource-constrained
	device is equipped with an 16-bits 8 MHz msp430 MCU, 10 KB of RAM, and 48 KB of
	non-volatile memory. On the other hand, the Raspberry PI 2 is more powerful as it is
	equipped with a 900M Hz quad-core ARM Cortex-A7 CPU, 1 GB of RAM, and 32 GB of
	non-volatile memory. Both types of devices are equipped with CC2420 RF transceivers.

Table 7 .

 7 of FADIA we implement the score() to return the current battery level of a device. Alternatively, for variant (2) score() always 4: Energy consumption of Tmote Sky devices while in different states. MCU ON represents a state where the microcontroller performing computations. TX and RX represents the CC2420 state while transmitting or receiving respectively. IDLE represents and idle state where the transceiver is off and the MCU is in low power mode. Data taken from Tmote Sky datasheet[START_REF]Tmote sky details[END_REF].

	STATE	Energy Consumption
	MCU ON	0.0054 J
	TX	0.0585 J
	RX	0.0654 J
	IDLE	0.00016 J

Table A .

 A 2: Data transfer per client for our protocol. The dimension is fixed to m = 10000.

	# Clients	Failures	Registration KeySetup Encryption Aggregation
			sent	0.13 KB	32.84 KB	62.47 KB	1.96 KB
		0%	rcvd	-KB	45.73 KB	-KB	5.46 KB
	100		total sent	0.13 KB 0.13 KB	78.57 KB 32.84 KB	62.47 KB 62.46 KB	7.42 KB 58.81 KB
		30%	rcvd	-KB	45.73 KB	-KB	3.81 KB
			total	0.13 KB	78.57 KB	62.46 KB	62.62 KB
			sent	0.13 KB	135.95 KB 79.00 KB	5.86 KB
		0%	rcvd	-KB	174.62 KB	-KB	16.50 KB
	300		total sent	0.13 KB 0.13 KB	310.57 KB 79.00 KB 135.95 KB 79.00 KB	22.36 KB 67.09 KB
		30%	rcvd	-KB	174.62 KB	-KB	11.53 KB
			total	0.13 KB	310.57 KB 79.00 KB	78.62 KB
			sent	0.13 KB	400.79 KB 97.30 KB	11.72 KB
		0%	rcvd	-KB	478.13 KB	-KB	33.05 KB
	600		total sent	0.13 KB 0.13 KB	878.92 KB 97.30 KB 400.78 KB 97.30 KB	44.77 KB 72.96 KB
		30%	rcvd	-KB	478.13 KB	-KB	23.12 KB
			total	0.13 KB	878.91 KB 97.30 KB	96.08 KB

Baseline secure aggregation protocols correspond to the basic constructions from the corresponding cryptographic tool.

For the formal definitions, please refer to the original paper.

This does not affect the security proof as it gives in a general sense more power to the adversary

If at least one client failed, constructing the protected zero-value Y ′ τ from its t shares which is O(nm).

https://github.com/MohamadMansouri/fault-tolerant-secure-agg

The C++ implementation of FADIA for Omnet++ can be found at https://github.com/ MohamadMansouri/FADIA

Acknowledgements

Acknowledgments v

Acknowledgements vi

List of Publications

We have presented the following publications during this PhD study. Most of them have already been presented through different venues enumerated below: category and shows the relation between the solutions.

Fault-tolerant Secure Aggregation

To tackle the problem of client failures (see C 1 ), a fault-tolerant secure aggregation protocol should be used. MPC-based SA, more specifically, Shamir's SS scheme [START_REF] Shamir | How to share a secret[END_REF] is fault-tolerant by design. It is used in [START_REF] Dong | Eastfly: Efficient and secure ternary federated learning[END_REF][START_REF] Kadhe | Fastsecagg: Scalable secure aggregation for privacypreserving federated learning[END_REF] where the FL server role is distributed among nothing. To secret share the keys, we use integer secret sharing ISS (see Section 2.3.1).

Let U = {U 1 , ..., U n } be the set of all users and U on ⊂ U be the set of online users, the threshold-variant Joye-Libert secure aggregation scheme, denoted as TJL, consists of the following PPT algorithms:

): Given some security parameter λ, this algorithm calls the original JL.Setup(λ) and outputs the server key, one secret key per user and the public parameters pp = (N, H Z * N 2 , I) where I = [-2 l , 2 l ] and l corresponds to the bit-size of the modulus N . Additionally, it sets the security parameter of the ISS scheme to σ.

• TJL.Protect(pp, k i , τ, x i,τ ) → y i,τ : This algorithm calls JL.Protect(pp, k i , τ, x i,τ ) and hence outputs cipher y i,τ .

• TJL.Agg(pp, k 0 , τ, {y i,τ } U i ∈Uon , y ′ τ ) → X τ : On input public parameters pp, the aggregation key k 0 , the ciphertexts of online users, and the ciphertext of the zerovalue corresponding to the failed users for timestamp τ , this algorithm computes:

To decrypt the final result, the algorithm proceeds as follows:

Definition 6.5.1: Correctness

Given the set of users U and the set of online user U on ⊂ U, the correctness of TJL scheme is defined as follows:

∀λ, ∀σ, ∀t, ∀τ, ∀x i,τ , ∀τ, ∀U shares s.t.

FTSA -Setup Phase

• Setup -Registration: Trusted Dealer:

-Choose security parameters λ, σ and runs KA.Param(λ) → (G, g, q) = pp KA and TJL.Setup(λ, σ) → ((N, H Z * N 2 , I), ⊥, ⊥). It sets the public parameters pp = (pp KA , pp TJL , G G , t, n, m, R, F) such that t is the secret sharing threshold, n is the number of clients, Z m R is the space from which inputs are sampled, G G is the hash function for key-derivation (see Section 2.4.3), and F is the field for SSS scheme. It sends them to the server and to all the clients. User u (pp):

-Receive the public parameters from the trusted dealer.

-Generate key pairs (c

) to the server (through the private authenticated channel) and move to next round.

Server(pp):

-Receives public parameters pp from the trusted dealer.

-Collect all public keys from the users (denote with U the set of registered users). Abort if |U| < t otherwise move to the next round.

-Broadcast to all users the list {Ui, (c

User u:

-Receive the public keys of all registered users U -For each registered user Uj ∈ U \{Ui}, compute channel keys ci,j ← KA.agree(pp KA , c SK i

-For each registered user Uj ∈ U \ {Ui}, compute ki,j ← KA.agree(pp KA , s SK i , s P K j , G G ) (set ki,i = 0). Then compute the TJL secret key ki ← U j ∈U δi,j • ki,j where δi,j = 1 when i > j, and δi,j = -1 when i < j.

-Generate t-out-of-n shares of the TJL secret key: {(j, ⟨ki⟩j)} ∀U j ∈U ← TJL.SKShare(pp TJL , ki, t, n).

-For each registered user Uj ∈ U \ {Ui}, encrypt its corresponding shares: ϵi,j ← Encc i,j (Ui || Uj || ⟨ki⟩j). -If any of the above operations fails, abort.

-Send all the encrypted shares {ϵi,j} ∀U j ∈U to the server (each implicitly containing addressing information Ui, Uj as metadata). -Store all messages received and values generated in the setup phase, and move to the online phase.

Server:

-Collect from each user Ui its encrypted shares {(Ui, Uj, ϵi,j)} ∀U j ∈U .

-Forward to each user Uj ∈ U its corresponding encrypted shares: {(Ui, Uj, ϵi,j)} ∀U i ∈U and move to the online phase. when i > j, and δ i,j = -1 when i < j. The correctness of the protocol is preserved since:

Note that this distributed method allows the distribution of the JL user keys but it still relies on a trusted third party to generate the public parameters. There exist techniques to distribute the computation of the public RSA modulus N ( [BF01, NS11, VAS19] in the passive setting and [CDK + 22] in the active setting). In this work, we assume the existence of a trusted offline third party that distributes the public parameters.

Protocol steps During Registration, clients register by sending their public keys to the aggregator who further broadcasts them to all clients. Notice that each client generates two public keys, one used to create secret communication channels among clients and the other used to compute the TJL secret key. Later, in the Key Setup step, each client U i computes mutual channel keys c i,j and its TJL key k i . It also creates secret shares of the TJL keys using TJL.SKShare and sends them to the corresponding clients (via the server through the authenticated channels). The specifications of the setup phase are given in Figure 6.2.

The Online Phase

The online phase consists of two communication rounds. In the first communication round, (i.e., Encryption step), the clients protect their inputs and send them to the aggregator. In the second communication round (i.e., Aggregation step), the clients and the aggregator construct the ciphertext of the failed clients.

Blinding inputs to ensure privacy One problem with the TJL scheme is that it guarantees privacy under the assumption that only one ciphertext of each user is computed for each timestamp. However, this assumption may break even in the honest-but-curious model. Let us assume the case where a client sends its protected input with some delay. The delay may cause the aggregator to request the online clients to construct the protected zero-value of the assumed failed client. In this case, two ciphertexts for the same timestamp are collected breaking the security assumption of the JL scheme. To deal with this problem, the client masks its input before encrypting it. The goal of the mask is to protect any leakage in case two ciphertexts of the same period are obtained. To remove these masks from the aggregated value, each client secretly shares its mask with all other clients. If the client survives the federated learning round, the online clients help construct its blinding mask. Otherwise, the clients construct the ciphertext of the zero-value using the TJL scheme.

Input vector encoding

The TJL scheme is originally designed to work with integers. In federated learning applications, FL clients send a vector of parameters instead of a single value. We, therefore, propose a dedicated encoding solution to encode a vector into a long integer. Each element of the initial vector V is firstly expanded by log 2 (n) bits of During the Aggregation step:

4. If at least one client failed, sending the share of the protected zero-value

During the total, the complexity is O(n + m) which is the same as in [BIK + 17].

Computation The computation cost consists of:

During the Encryption step:

1. Generating t out of n shares of b i,τ which is O(n 2 ).

2. Encrypting the client's message X i,τ which is O(m).

During the Aggregation step:

3. Encrypting the zero-value using the secret shares which is O(m).

Therefore, the total complexity is O(n 2 +m) which is lower than in [BIK + 17] (O(n 2 +nm)). The higher complexity in [BIK + 17] is due to the one-to-one key agreement on the shared masking seeds then extending each of them to the dimension of the client's input which adds an extra O(nm).

Storage The client must store the keys and shares of all clients as well as the data vector which results in a storage overhead of O(n + m) which is the same as the one in [BIK + 17].

Scalability Analysis of The Online Phase at the Server

Communication The server's communication cost is n times the client's communication cost. Thus, a complexity of O(n 2 + nm) which is the same as the one in [BIK + 17].

Computation The computation cost consists of: During the Encryption step, the server's computation cost is not significant since the server only forwards messages.

During the Aggregation step: Summary In summary, the major improvement of our protocol over SecAgg [BIK + 17] is in the running time at the client. Our protocol reduces the overhead on the client's processor up to 8 times when running in large networks. For the server running time, the improvement is only achieved in networks with significantly high failure rates (∼ 30%). Finally, the data transfer is better in our protocol in the case of a large number of clients but worse in the case of huge input dimensions.

6.9 FTSA * : An Optimized Fault-Tolerant SA

We present an optimized version of our protocol FTSA presented in Section 6.6. The optimization can be considered as a major change in the way how the TJL scheme is used to achieve fault-tolerant secure aggregation. We first discuss the main idea of this modification and its consequences on the protocol. Second, we present the new version of our protocol (we call it FTSA * ). Finally, we present the new performance results of the protocol.

The Idea

The main limitation of FTSA is that it requires masking the user input X i,τ with random mask B i,τ before applying the TJL.Protect algorithm. The masks are secretly shared with all users which results in a quadratic complexity in terms of computation and communication. The reason for masking the input (X i,τ + B i,τ ) is to prevent a malicious aggregator to leak the user input. This attack is performed by a malicious aggregator claiming that an actually online user is dropped. It allows the aggregator to obtain two ciphertexts (for the same timestamp) produced by the same user key (the first ciphertext is received from the online user and the second is the zero-protected value computed using the shares of the key). Masking guarantees that the user input is protected when such an attack happens.

We propose a different solution to mitigate this attack. Our solution is to mask the encryption key of the user instead of masking the message itself. The advantage of this approach is that it is performed in the offline phase when the keys are created. Hence, the sharing of the masking key is also performed in the offline phase. Consequently, the Secure Aggregation Protocol -Online Phase

• Online -Encryption (step τ ):

User u:

-Protect the private input Xi,τ ∈ Z m R with the masked key (ki + bki) using TJL scheme: Yi,τ ← TJL.Protect(pp TJL , ki + bki, τ, Xi,τ ).

-Send the protected input Yi,τ to the server . Server: -Collect from each user its protected input Yi,τ (or time out).

- Secret key shared between P i and the controller K s

Secret key shared between

Secret key (and it corresponding key id) shared between P i and P j sch

The hash of the software configuration on a prover

FADIA -Complete Specifications

In this section, we describe the design of FADIA. The protocol is composed of four different phases: the initialization, joining, attestation and revocation phases. The first initialization phase consists of an offline setup phase where the keying material is installed at all involved provers. During the joining phase, a prover identifies itself to the controller. The prover further starts the attestation phase. During the attestation phase (which is the core phase of FADIA), the active prover periodically participates in virtual attestation trees to send its attestation report and forward others'. The active prover keeps running this phase until it is dropped from the network (either intentionally because it is detected as malicious or incidentally because it left the network). On such an event, the revocation phase starts whereby the dropped prover becomes offline and its keys are revoked. In the following, we describe each phase in more detail.

Initialization Phase

Provers, before participating in FADIA, are considered offline. In order for a prover P i to enter the protocol, it has first to be set by the network operator O. O defines a key pool (O.P ool) according to [START_REF] Eschenauer | A key-management scheme for distributed sensor networks[END_REF], (see § 7.4). This key pool is stored in a safe location (offline). The key pool contains p symmetric keys together with their key ids {( K ID , K )}. P i randomly receives a key ring of size r from the key pool:

O also assigns a unique id (uid) for P i and a cryptographic hash of the current software configuration (sch). P i then obtains a unique key K ic (the attestation key) derived from the chosen keyring ids and the prover's unique id. This key is computed by O using a key children a prover can have. After P i is registered, C regularly checks its status and if P i does not attest in δ h time, its status becomes "unhealthy". Figure 7.2 provides the specification of the joining phase.

Attestation Phase

Provers start running this phase immediately after completing the joining process. P i enters a new attestation period every δ h /2 time. (δ h /2 is chosen to guarantee that two consequent attestations are always received within no longer than δ h time.) At each attestation period, a P i starts by performing an integrity check on its software configuration. The check is performed against the software configuration hash (sch) stored in the prover. The method of this check and the format of sch is out of the scope of this paper. This can be a simple technique based on computing the hash of the firmware or more complex techniques such as the ones proposed in [AAD + 16, DZN + 17, ZDA + 17, CTR18]. If the integrity check fails, then P i quits the attestation phase and will be eventually dropped from the protocol. After succeeding in the integrity check, P i participates in the construction of a tree in which it will attest. First, P i generates a unique proof of its attestation using the function generateP roof (). It further evaluates

Attestations collection

The leaf nodes send attestation messages (attst) to their parents. The attestation message of P i contains the generated proof which is computed as follows:

where cntr is a counter that is incremented each time P i attests. Parent nodes aggregate the attestation messages from their children using the function aggregateAttestation().

Similarly, the new attestation message is sent to the parent and processed. This is repeated until the initiator prover receives all the aggregated attestation messages. It then sends the final attestation message to the controller. An attestation message is composed of multiple sets of prover ids. The number of provers in a set is controlled by the parameter α g . Each set is linked with a single proof which is the XOR of all proofs provided by the provers in that set. The algorithm that describes aggregateAttestation() is depicted in Algorithm 1.

The granularity of the aggregation of the attestation is parameterized by α g . If α g is 0, then none of the proofs are XORed, and thus, all individual proofs are transmitted to the controller. If α g is larger than the number of provers participating in the tree, all proofs are XORed forming a single proof for all provers.

Appendices