Rémi Géraud-Stewart

Chapter 1 -Introduction be able to quickly consult, ideally from the software reference, how secure the use case is and how to correctly implement it.

This thesis modestly adds its contribution to the research effort in that domain: improve on the comprehension of existing data structures, and propose new use cases of cryptography with a special attention to provable security. The goal being set, our main axes of research, that we present in this manuscript, are the following:

• Study existing data structures, their security properties, and, if applicable, how they behave in an adversarial environment.

• Allow algorithms to be executed in the cloud (i.e. to be distributed), while maintaining the privacy of the data exchanged. This includes quantifying the data leaked to each participant to the protocol, as well as ensuring that an external observer cannot gain significant information from the data exchanges.

Publications

We now present our contributions. While some of our publications are presented in this manuscript, we also took the decision of not presenting all our results here, both for the sake of brevity and of coherence.

Chapter 1 -Introduction on both blockchains. It confirms that having interoperability is only possible by creating a '2-in-1' blockchain containing both ledgers.

"Schlak, pof".

Je ne saurais dire de quand me date le goût des maths, mais il est certain que cette flamme a été avivée tôt chez moi par les cours énergiques de Madame Farchi, et pour cela, merci. J'adresse également mes plus vifs remerciements à mes directeurs de thèse, David Naccache et Pascal Lafourcade, tous deux plus motivés et motivants l'un que l'autre, et toujours disponibles pour discuter sécurité, cryptographie ou n'importe quel autre sujet à des horaires parfois raisonnables et parfois franchement absurdes, mais toujours dans la bonne humeur. Merci de m'avoir encadré, de m'avoir initié à la recherche, et de m'avoir fait trouver la voie, sans pour autant que j'y perde la tête.

David, merci de m'avoir pris sous ton aile dès le stage de fin d'études, et de ne jamais hésiter à me pousser hors de ma zone de confort. Merci de toujours vouloir le meilleur pour moi, merci pour ton humour toujours présent. Pascal, merci de m'avoir fait une place dans cette inconnue qu'était l'Auvergne. Merci également d'avoir toujours eu confiance en moi, de toujours discuter de nouvelles idées et de m'avoir enduré et remotivé pendant mes périodes de doute. Également merci d'avoir relu cette thèse.

Thank you to Michel Abdalla, Gildas Avoine, Pascal Paillier, Bart Preneel, Mariana Raykova, Moti Yung, for having accepted to be part of this jury. Thank you especially for Gildas Avoine and Moti Yung for being thesis reporters. I am honoured to present this work to you.

Je tiens également à remercier tous mes coauteurs, avec qui les échanges ont toujours été enrichissants, productifs, et m'ont chacun aidé à grandir tant scientifiquement qu'humainement. Camille, Cheng-Kang, Claudia, David, Hsiao-Ying, Marta, Mirko, Pascal, Pierre, Radu, Rose, Rémi, Yao, thank you all guys for the opportunity and experience. Publishing with you was always a pleasure, with its share of surprises, rebuttal by reviewer #3, all-nigthers, unrelated but fascinating side discussions and unsolvable puzzles that we loved to share anyways. i Merci au premier confinement, qui aura probablement représenté les 56 jours les plus productifs de ma thèse. Merci au second confinement, qui aura probablement représenté les 46 jours les moins productifs de ma thèse.

Il paraît que l'on ne connaît véritablement un sujet que lorsqu'on est capable de l'enseigner. J'ai eu la chance de perfectionner mon savoir dans plusieurs domaines, grâce à des interventions à l'université de Clermont, que ce soit en fac ou à l'IUT, à l'ISIMA, et plus récemment à Dauphine. Merci à mes étudiants pour leur attention et leurs questions, et pour m'avoir fait réviser mes connaissances en C, assembleur, stéganographie et autres machines de Turing, sans oublier des petites excursions dans le code pénal ou la théorie des multivers. Merci aux questions qu'ils m'ont posées, aux retours qu'ils m'ont faits et l'ingéniosité dont ils ont su faire preuve. Merci aux enseignants, Alexandre, Aurélie, David, Olivier, Michelle, Pascal, de m'avoir fait confiance, puis de m'avoir laissé donner mes propres cours. Merci également à Pint of Science et au journal des Centraliens de m'avoir offert une tribune pour y parler de sujets qui me tiennent à coeur.

Un grand merci également à tous les doctorants de la F203, que ce soit la team crypto avec Matthieu puis Léo, ou la team machine learning qu'on aime bien quand même, avec Ala, Alexandre, Amal, Kergann, et également Oliver. Merci pour toutes les discussions, les rigolades, les parties d'échecs, de badminton et de Tux kart endiablées, et tous les autres souvenirs.

Merci également à la dream team PhD qui, malgré vents et marées, a réussi à traverser l'enfer et maintenir le cap. Aurélie, Claudia, Farah, Mirko, Rose, Sami, Tom, le chemin fut plus qu'éprouvant mais le dénouement est là, ou du moins le pire est passé. Merci à Olivier d'avoir fait ce qu'il fallait pour que cette thèse aille à son terme à un moment critique. Merci aussi à Aboubakar, Arthus, Geoffrey, Pierre, Tim, vous rencontrer et travailler avec vous a été un plaisir, et à la prochaine ! Bien sûr, pour tous ces moments passés ensemble, un grand merci à mes amis, ceux de Paris, ceux de Clermont et ceux d'ailleurs, pour les discussions et trolls à n'en plus finir, les bières post-escalade (ou les escalades pré-bière, c'est selon), les escapades dans l'arrière-pays, les soirées jeux, les soirées tout court, les anniversaires, les réveillons et les sorties à la recherche de LA voie à grimper, ou tout simplement pour m'accueillir dans leur centre de bien-être et de rééducation™. Merci pour les souvenirs, pour les bonnes marrades, les moments passés ensemble, merci d'être vous.

Merci à ma famille et particulièrement à mes parents, qui durant ces trois années m'ont soutenu, encouragé, motivé, aidé à franchir les passages à vide et les doutes, qui ont toujours été un soutien pour moi et qui ont écouté avec patience (ou du moins fait semblant) toutes mes explications passionnées. Merci de toujours être là pour moi. Y por supuesto, gracias a ti Clau. Gracias por compartir tu vida conmigo y ser la luz de mi dia a dia. Ni en el mejor de mis sueños.

Introduction

Goal and Contributions

The first use of cryptography was for military purposes. The goal was simply to provide confidentiality to messages exchanged on what would later be labelled as insecure channels. Yet, over the last century, the need for confidentiality has often been seen as insufficient, and cryptography itself as a valuable tool, but a tool that required good properties of all the tools it interacted with. We often describe cryptography as an armoured door, preventing attackers from invading your home. However, while the armoured door itself is secure, it relies on hinges, doorframes etc., which also need to be studied for the security of the home. Furthermore, once the armoured door has been designed, it can be used in many different use cases, let it be for a vault, a simple house, the mailbox... Each new use comes with a list of requirements and properties that need to be studied. Hence, there is today a need to clearly understand how secure each software used is, and how to use them securely. As a matter of fact, software developers cannot spend days reading academic papers to assess the security of the solution they are implementing. Rather, they need to

Security in Data Streams for Duplicate Detection

The results obtained in this section are presented in Part I. Initially, the study of duplicates was related to a new authenticated encryption method we were studying.

In this protocol, we identified an attack, which we thwarted with the use of noncesunique elements, generated by the sender. However, this defence mechanism implied that the receiver had to keep track of the nonces, to avoid reuse. While a database is an obvious solution, we looked instead for smaller structures, as our cryptographic protocol was aimed at IoT devices, with little storage and computing power.

Even though in the end the authenticated encryption appeared non viable (notably because of intrinsic properties of adversarial resistance of duplicate filters exposed in this thesis), the work on duplicate filter is still of scientific interest.

• Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data

This contribution presents the Quotient Hash Table (QHT) a new data structure for duplicate detection in unbounded streams. QHTs stem from a corrected analysis of streaming quotient filters (SQFs), resulting in a 33% reduction in memory usage for equal performance. With the same memory amount, QHT reduce by up to 7.7 points of percentage the error rate (about 13% more efficient) when compared to SQF. We also introduce an optimised version of our new data structure dubbed Queued QHT with Duplicates (QQHTD).

We provide a new and thorough analysis of both algorithms, with results of interest to other existing constructions, and we correct a slight mistake that 1.2 -Publications was made in a previous version of this paper. We also introduce a novel (non tight) lower bound on the error rate, thus helping to determine how close to optimality a filter is. These theoretical results are confronted with detailed benchmarks, and matched against the performance of other filters from the literature, proving the efficiency of QHTs, both on an entire stream or on a sliding window. Finally, we discuss the effect of adversarial inputs for hashbased duplicate filters similar to QHT.

This work is joint with Rémi Géraud-Stewart and David Naccache. The version presented in this thesis is an extended version of a work presented at the 34th ACM/SIGAPP Symposium On Applied Computing (SAC 2019), and published as [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF].

• Approaching Optimal Duplicate Detection in a Sliding Window

Iterating on the previous work, we focus on the duplicate detection problem over a sliding window. In this work, we formalize the sliding window setting introduced by [SZ08; Yoo10], and show that a perfect (zero error) solution can be used up to a maximal window size w max . Above this threshold we show that some existing duplicate detection filters (designed for the non-windowed setting) perform better that those targeting the windowed problem. Finally, we introduce a "queuing construction" that improves on the performance of some duplicate detection filters in the windowed setting.

We also analyse the security of our filters in an adversarial setting.

This work is joint with Rémi Géraud-Stewart and David Naccache. It has been presented at the 26th International Computing and Combinatorics Conference (COCOON 2020), and published as [START_REF] Géraud-Stewart | Approaching Optimal Duplicate Detection in a Sliding Window[END_REF].

Applied Security on Blockchain

• About Blockchain Interoperability A blockchain is designed to be a self-sufficient decentralised ledger: a peer verifying the validity of past transactions only needs to download the blockchain (the ledger) and nothing else. However, it might be of interest to make two different blockchains interoperable, i.e., to allow one to transmit information from one blockchain to another blockchain. In this work, we give a formalisation of this problem, and we prove that blockchain interoperability is impossible according to a strong definition of a blockchain. Under a weaker definition of blockchain, we demonstrate that two blockchains are interoperable is equivalent to creating a '2-in-1' blockchain containing both ledgers, thus limiting the theoretical interest of making interoperable blockchains in the first place. We also observe that all practical existing interoperable blockchain frameworks work indeed by exchanging already created tokens between two blockchains and not by offering the possibility to transfer tokens from one blockchain to another one, which implies a modification of the balance of total created tokens

Security of a Cryptographic Protocol

These contributions are a bit more theoretical, as they spawn from a new field of research, aiming to distribute and securize existing machine learning protocols. This line of work was a collaboration with the INSA Val de Loire.

• Secure Best Arm Identification in Multi-Armed Bandits

The stochastic multi-armed bandit is a classical decision making model, where an agent repeatedly chooses an action (pull a bandit arm) and the environment responds with a stochastic outcome (reward) coming from an unknown distribution associated with the chosen action.

A popular objective for the agent is that of identifying the arm with the maximum expected reward, also known as the best-arm identification problem.

We address the inherent privacy concerns that occur in a best-arm identification problem when outsourcing the data and computations to a honest-butcurious cloud.

Our main contribution is a distributed protocol that computes the best arm while guaranteeing that (i) no cloud node can learn at the same time information about the rewards and about the arms ranking, and (ii) by analyzing the messages communicated between the different cloud nodes, no information can be learned about the rewards or about the ranking. In other words, the two properties ensure that the protocol has no security single point of failure. We rely on the partially homomorphic property of the well-known Paillier's cryptosystem as a building block in our protocol.

We prove the correctness of our protocol and we present proof-of-concept experiments suggesting its practical feasibility. This work is joint with Radu Ciucanu, Pascal Lafourcade and Marta Soare. It has been presented at the 15th International Conference on Information Security Practice and Experience (ISPEC 2019) and published as [START_REF] Ciucanu | Secure Best Arm Identification in Multi-armed Bandits[END_REF].

• Secure Outsourcing of Multi-Armed Bandits

We consider the problem of cumulative reward maximization in multi-armed bandits. We address the security concerns that occur when data and computations are outsourced to an honest-but-curious cloud i.e., that executes tasks dutifully, but tries to gain as much information as possible. We are motivated by situations where data used in bandit algorithms is sensitive and has to be protected e.g., commercial or personal data. We rely on cryptographic schemes and propose UCB-DS, a distributed secure protocol based on 1.2 -Publications the UCB algorithm, which yields the same cumulative reward as UCB while satisfying desirable security properties that we formally prove. In particular, cloud nodes cannot learn the sum of rewards for more than an arm or the cumulative reward. Moreover, by analysing messages exchanged among cloud nodes, external observers cannot learn the cumulative reward or the sum of rewards produced by some arm. We show that the overhead due to cryptographic primitives is linear in the size of the input.

Our implementation confirms the linear-time behaviour and the practical feasibility of our protocol, on both synthetic and real-world data.

This work is joint with Radu Ciucanu, Pascal Lafourcade and Marta Soare.

It has been presented at the 19th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom 2020), and published as [START_REF] Ciucanu | Secure Outsourcing of Multi-armed Bandits[END_REF].

Other Publications

Other publications have been made throughout the last three years, on various topics of security, sometimes theoretical, sometimes practical.

• Keyed Non-Parametric Hypothesis Tests

The recent popularity of machine learning calls for a deeper understanding of AI security. Amongst the numerous AI threats published so far, poisoning attacks currently attract considerable attention. In a poisoning attack the opponent partially tampers the dataset used for learning to mislead the classifier during the testing phase.

This work proposes a new protection strategy against poisoning attacks. The technique relies on a new primitive called keyed non-parametric hypothesis tests allowing to evaluate under adversarial conditions the training input's conformance with a previously learned distribution D. To do so we use a secret key κ unknown to the opponent.

Keyed non-parametric hypothesis tests differs from classical tests in that the secrecy of κ prevents the opponent from misleading the keyed test into concluding that a (significantly) tampered dataset belongs to D.

This work is joint with Yao Cheng, Cheng-Kang Chu, Hsiao-Ying Lin and David Naccache, and has been presented at the the 13th Network and System Security (NSS 2019), and published as [START_REF] Cheng | Keyed Non-parametric Hypothesis Tests[END_REF].

• PlasticCoin: an ERC20 Implementation on Hyperledger Fabric for Circular Economy and Plastic Reuse

Cryptocurrencies have gained popularity in the last few years, thanks to the democratization of Bitcoin. However, most of these currencies have a very general purpose, namely of allowing people to pay their products with an

Chapter 1 -Introduction electronic, decentralised currency. Moreover, the lack of trust of these opennetwork blockchains comes at a significant economic cost. In this work, we present PlasticCoin, a cryptocurrency empowering plastic reuse in a circular economical model, that anyone can join, and that respects the ERC20 specifications on a consortium blockchain. We also explore the economical ecosystem revolving around PlasticCoin, and also introduce a way to print tickets that can temporarily hold the role of physical banknotes. Finally, we show that our system is flexible, and it can be adapted to many other business purposes.

This work is joint with Mirko Koscina and Pierre Cluchet. It has been presented at the Workshop On Social Innovation And Web Intelligence, hosted by the Web Intelligence conference (SIWEB@WI 2019), and has been published as [START_REF] Koscina | Plas-ticCoin: an ERC20 Implementation on Hyperledger Fabric for Circular Economy and Plastic Reuse[END_REF].

• Get-your-ID: Decentralized Proof of Identity

In most systems without a centralised authority, users are free to create as many accounts as they please, without any harmful effect on the system. However, in the case of e-voting, for instance, proof of identity is crucial, as sybil identities can be used to breach the intended role of the system. We explore the conditions under which a decentralised proof of identity system can exist. We also propose such a scheme, called Get-your-ID (GYID), and prove its security. Our system allows a user to generate and revoke keys, via an endorsement mechanism, and we prove that under some conditions which we discuss, no user can have more than one active key. We then show how voting protocols can be adapted on top of our system, thus ensuring that no user is able to cast a valid vote more than once.

This work is joint with Pascal Lafourcade. It has been presented at the 12th International Symposium on Foundations and Practices of Security (FPS 2019), and has been published as [START_REF] Lafourcade | Get-your-ID: Decentralized Proof of Identity[END_REF].

• A silver bullet? A Comparison of Accountants and Developers Mental Models in the Raise of Blockchain

This contribution is quite different from the others, as it is a preliminary research on an interdisciplinary research between requirement engineering and security. This exploratory work intends to drive preliminary insights on the different mental models accountants and blockchain developers have on the implementation of blockchain for accounting. Based on the question of whether blockchain applications for accounting could be revolutionary, this work employs a ground theory methodology based on semi-structured interviews and concept analysis to highlight the different approaches to transparency and trust between the selected groups, the challenges of blockchain and the potential effects of this technology in accounting. Although deeper studies are needed, the conclusions highlight the socio-technical nature of accounting; the relevance and changes of the concepts of trust and transparency when marrying both disciplines; and the real relevance of this technology for the processes 1.2 -Publications of auditing and accounting.

This work is joint with Rose Esmander, Pascal Lafourcade, Claudia Negri Ribalta. It has been presented at the 3rd Interdisciplinary Workshop on Privacy and Trust (iPAT 2020), held in conjunction with the 15th International Conference on Availability, Reliability and Security (ARES 2020), and published as [START_REF] Esmander | A silver bullet?: a comparison of accountants and developers mental models in the raise of blockchain[END_REF]. An extended version of this work has been published in a selected papers edition of ARES, as [START_REF] Negri Ribalta | Blockchain Mirage or Silver Bullet? A Requirementsdriven Comparative Analysis of Business and Developers' Perceptions in the Accountancy Domain[END_REF].

• A Blockchain-based Marketplace Platform for Circular Economy

Over the recent years, there has been an intense research on blockchain and its applications in real-life scenarios, both from academic and industrial research. This work proposes an architecture for a blockchain-based marketplace platform. We have implemented and tested our design, which allows user to do simple marketplace transactions as well as more complicated features, such as auctions à la eBay. We explore the functionalities and the implementation details of our solution, while showing how we ensure respect with GDPR.

This work is joint with Mirko Koscina and Claudia Negri Ribalta, and has been accepted at the 36th ACM/SIGAPP Symposium On Applied Computing (SAC 2021), and has been published as [START_REF] Koscina | A blockchain-based marketplace platform for circular economy[END_REF].

Duplicate detection

In this section, we expose the formalism and the definitions related to duplicate detection. Duplicate detection relates to the problem, when given a stream of elements, to detect for each new element whether it occurred previously in the stream or not.

Chapter 2 -Technical Introduction

Duplicate Detection Problem

Definition 2.1.1 (Duplicate detection problem). Let E = (e 1 , . . . , e n , . . . ) be a (possibly infinite) sequence of elements e i ∈ Γ where Γ is some alphabet of size |Γ|.

An element e i from E is a duplicate if ∃e j ∈ E, j < i such as e j = e i . Otherwise, e i is unseen. Note that by definition e 1 is always unseen.

The approximate duplicate detection problem is the question of finding with the best probability, for each new element of the stream, whether it is a duplicate in a stream E. This problem is equivalent to a dynamic formulation of the approximate membership problem [START_REF] Dietzfelbinger | Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)[END_REF], which focuses on finding a duplicate in a fixed dataset. We recall the following classical result: Theorem 2.1.1. Assume that each e i is sampled uniformly at random from Γ. Then perfect detection requires |Γ| memory bits.

Proof. A perfect duplicate algorithm must be able to store all finite substreams of any stream E = (e 1 , . . . , e n , . . . ), i.e., must be able to store any subset of Γ, which we denote by P(Γ). Given that there are |P(Γ)| = 2 |Γ| of them, according to information theory any such filter requires at least log

2 (|P(Γ)|) = log 2 (2 |Γ| ) = |Γ| bits of storage.
Because of this result, perfect duplicate detection is often out of reach when |Γ| is big -however probabilistic solutions are often sufficient for many applications. Such algorithms make errors: false positives (claiming a duplicate where there isn't) and false negative (missing a duplicate). We mostly consider cases when the amount of memory M is such that M ≪ |Γ|.

On a side note, it is clear that the input distribution plays a central role regarding how efficiently the duplicate detection problem can be solved. For instance, some deterministic streams may be expressed very compactly (such as the output of a PRNG with known seed) making the duplicate detection problem relatively easy. Information-theoretically, if the source has |Γ| bits of entropy then the situation is equivalent to having an |Γ|-bits, uniformly distributed, input.

Filters

As the problem of duplicate detection has been set, we now need to define the structures that will try to solve this problem. Definition 2.1.2 (Duplicate Detection Filter (DDF)). Let Γ be an alphabet, let M represent the set of states that can be represented using M bits of memory. A duplicate detection filter F (or DDF) over the memory M is a tuple F = (S, Detect, Insert), where:

• S ∈ M is the current state • Detect : Γ × M → {DUPLICATE, UNSEEN} 2.1 -Duplicate detection • Insert : Γ × M → M
Here DUPLICATE corresponds to a guess, given the current filter state, that the provided element is duplicate, and UNSEEN that it is unseen. Insert corresponds to an update of the filter's memory state after observing a new element.

In practice, Detect and Insert are often merged into a single algorithm Stream ← Insert • Detect: when a new stream element arrives, we first detect whether it is a duplicate or not, and then add it in our memory. Furthermore, for a stream E, we define the value FPR n as the FPR of E over the n first elements, and same for FNR n . Similarly, the asymptotic FPR (resp. FNR) is defined as

FPR ∞ = lim n→∞ FPR n (resp. FNR ∞ = lim n→∞ FNR n ).
Note that, at several occasions, we will focus on the probability of false positive (resp. false negative) after n insertions, noted FP n (resp. FN n ), as these probabilities are most of the time easier to derive. The derivation of, e.g., the FPR from the FP probability is trivial:

FPR m = 1 m m i=1 FP i .
An open research question is whether there exist filters whose FNR and FPR can be kept low when M is bounded.

Duplicate Detection on a Sliding Window

As we will see, the DDP is often more interesting to study on a sliding window.

Let us consider a sliding window of size w ∈ N, a stream E = (e 1 , . . . , e n , . . . ) from an alphabet Γ. Definition 2.1.5 (Duplicate detection problem on a sliding window (wDDP)). The element e i of E is said to be unseen in the sliding window, and we note e i / ∈ w E if all w previous elements from E are different from e i . More formally, ∀i ≤ n, e i is unseen if and only if ∀k ∈ {1, . . . , min(w, i -1)}, e i-k ̸ = e i . If this is not the case, e i is said to be a duplicate within the sliding window, and we note e i ∈ w E.

We similarly redefine the notion of false positives and negatives, as well as the false positive rate and false negative rate, over a sliding window. The FPR (resp. FNR) of a filter on a sliding window of size w is noted FPR w (resp. FNR w ).

While the goal of this work is to work as much as possible with this definition of false positives on a sliding window, we sometimes use the error rate following Definition 2.1.3, as the related formulae are much easier to use for practical considerations.

Chapter 2 -Technical Introduction

Adversarial Resistance to Duplicate Detection

In this section, we consider a scenario in which an adversary tries to fool the filter. Namely, the adversary will try to trigger false positives and false negatives. Motivations for doing so include fooling the system, for instance in the case of fraudulent clicks transactions [START_REF] Metwally | Duplicate Detection in Click Streams[END_REF], a sophisticated DoS relying on cache misses [START_REF] Fan | Summary Cache: A Scalable Wide-area Web Cache Sharing Protocol[END_REF], and so on.

To create a realistic adversary model, we assume like in [START_REF] Carcillo | SCARFF: a Scalable Framework for Streaming Credit Card Fraud Detection with Spark[END_REF] that the adversary does not have access to the filter's internal memory. Nonetheless, after every insertion she knows whether the inserted element was detected as a duplicate or not. Thus, the attacker is able to carry an adaptive attack, by choosing the next element to send to the filter as a function of all previous insertions. The adaptative advantage allows the attacker to establish strategies that may perform better than random, hence giving an advantage to the attacker in her endeavour, whatever this endeavour might be.

We do not make assumption on the adversary memory: she is able to remember all previous queries she made.

In this adversarial game, the attacker can send an arbitrary stream to the filter, and is allowed to get the result of Stream for every element. Then, at her convenience, the attacker goes into the second phase of the game, in which she has two possible actions:

• Send an unseen element that will be a false positive with high probability (false positive attack);

• Send a duplicate element that will be a false negative with high probability (false negative attack).

Given these premises, we give a formal definition of an adversarial game, adapted to our context. Definition 2.1.6 (n-false positive/negative adversarial game). An adversary A feeds data to a duplicate filter F, and for each inserted element, A knows whether F answers DUPLICATE or UNSEEN, but has not access to F's internal state M. The game has two distinct parts.

• In the first part, A can feed up to n elements to F and learns F's response for each insertion. A can decide to switch to the second part before sending n elements.

• In the second part, A sends a unique element e ⋆ .

A wins the n-false positive adversarial game (resp. n-false negative adversarial game) if and only if e ⋆ is a false positive (resp. a false negative).

Variants of these games over a sliding window of size w are immediate. Note that other works (notably [START_REF] Naor | Bloom Filters in Adversarial Environments[END_REF]) have also investigated the adversarial context of some duplicate filters, in this case, of the Bloom Filter. However, they relied on a different definition of adversarial attacks, in which the attacker had access to an oracle, emulating the filter's state (which does not evolve), and then emits a challenge e ⋆ . While their definition of an adversarial attack is more fit in the context of a fixed Bloom Filter (the context [START_REF] Naor | Bloom Filters in Adversarial Environments[END_REF] authors investigate), we argue that our definition is more fit in a streaming context. Definition 2.1.7 (Adversarial False Positive Resistance). We say that a duplicate filter F is (p, n)-resistant to adversarial false positives if no polynomial-time probabilistic (PPT) adversary A can win the n-false positive adversarial game with probability greater than p.

Note that if F is (p, n)-resistant, then it is (p, m)-resistant for all m < n.
We define similarly the notion of being resistant to adversarial false negatives. Finally, both definitions also make sense in a sliding window context.

Primer on Multi-Armed Bandits

The problem of best arm identification in multi-armed bandits [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] has been initially formulated in the domain of real numbers. We slightly revisit the initial formulation of the problem in order to manipulate integers. The reason behind this adaptation is that later on in our thesis, we rely on public key cryptography tools to add security guarantees to a state-of-the-art best arm identification algorithm.

Problem exposure

Input. The input is twofold:

• Number of arms K. Each arm i ∈ {1, . . . , K} is associated to a reward value x(i) and a reward function r that returns a random integer in an interval [x(i)ϵ, x(i) + ϵ] according to a uniform probability distribution. Whereas each arm i is associated to its specific value x(i), the value of ϵ is common to all arms. The intervals associated to different arms may be overlapping, which makes the setting non-trivial. The best arm i * is arg max i∈{1,...,K}

x(i).

• Budget N . The budget represents how many arm pulls (and implicit reward observations) the user is allowed to do.

Note that for designing a budget-allocation strategy between the arms, only the number of arms K and the budget N are known. There is no initial information about the reward associated to each arm.

Output. The estimated best arm i * α that can be learned after making N arm pulls (and subsequent reward observations) according to some allocation strategy α, which defines how the budget is divided between the K arms. The challenge is to design a budget-allocation strategy α that makes the best possible use of the budget. In other words, when selecting the arms to be pulled according to α, the observed rewards allow to acquire as much useful information as possible for identifying i * .

Chapter 2 -Technical Introduction Performance Measure. We call simple regret R N the difference between the value of the (true) best arm i * and the arm i * α estimated as being the best arm by an allocation strategy α after N arm pulls. Thus, we compare the gap between the value of the identification made by strategy α and that of an oracle strategy that knows the values of the arms beforehand. Formally, the performance of strategy α after using a budget

N is R N (α) = x(i * ) -x( i * α ).
Example. We have 3 arms with associated reward values in intervals [3,23], [25,45], and [40,60]. This means that x(1)=13, x(2) = 35, x(3) = 50, and ϵ=10. Assuming a budget of 3, the user may choose to spend one pull for each arm and observe rewards of (for instance) 23, 44, and 41, respectively. Hence, the user could wrongly think that arm 2 is the best, thus getting a regret of 50 -35 = 15.

Obviously, increasing the budget would increase the number of pulls that can be done, hence it would increase the chances of correctly identifying the best arm. This can be easily done in the presence of an infinite budget, but the challenge is to identify the best arm using as few pulls as possible, or in other words, to maximize the probability of correctly identifying the best arm while having a limited budget.

Successive Rejects (SR) [ABM10]

The algorithm takes as input the number of arms K and the budget N . Initially, all K arms are candidates. SR divides the budget in K -1 phases. At the end of each phase, a decision is made. The phases' lengths are fixed such that the available budget is not exceeded and the probability of wrongly identifying the best arm is minimized.

More precisely, at each phase j ∈ {1, . . . , K -1}, each still candidate arm in A j is pulled n j times according to the fixed allocation (cf. Algorithm 1). At the end of each phase, the algorithm rejects the arm with the lowest sum of observed rewards, that is the arm estimated to be the worst. If there is a tie, SR randomly selects the arm to reject among the worst arms. Then, at the next phase, the remaining arms are again uniformly pulled according to the fixed allocation. Thus, the worst arm is pulled n 1 times, the second worst is pulled n 2 + n 1 times, and so on, with the best and the second-best arm being pulled n K-1 + . . . + n 1 times. The estimated best arm is the unique arm remaining after phase K -1.

We consider the sums of observed rewards per arm when deciding which arm to reject instead of empirical means as in the original version [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] as a simplification. Indeed, each candidate arm is pulled the same number of times in each phase, hence the ranking of the arms is identical regardless of whether we look at sums or means.

Example.

Let there be a multi-armed bandit with 4 arms and x(1) > x(2) > x(3) > x(4), with budget N = 500 pulls. We have log(4) =

sum[i] ← 0 4: log(K) ← 1 2 + K i=2 1 i 5: n 0 ← 0 6: for j from 1 to K -1 do ◃ Successive rejects 7: n j ← 1 log(K) N -K K+1-j -j-1 l=0 n l 8:
for all i ∈ A j do 9:

loop n j times 10:

r ← random integer from [x(i) -ϵ, x(i) + ϵ] 11: sum[i] ← sum[i] + r 12: A j+1 ← A i \ arg min i∈A j sum[i] 13: return A K Phase 2: each arm 1, 2, 3 is pulled n 2 =⌈ 12 19 500-4 4+1-2 ⌉-n 1 =26 times Phase 3: each arm 1, 2 is pulled n 3 =⌈ 12 19 500-4 4+1-3 ⌉-(n 1 + n 2 )=52 times.
In other words, arm 4 is pulled 79 times, arm 3 is pulled 79+26=105 times, each arm 1, 2 is pulled 79+26+52=157 times, totalling 79 + 105 + 2 × 157 = 498 pulls.

A Variation: Upper Confidence Bound (UCB)

Instead of identifying the best arm, one can be interested into exploring similar questions. One of these questions is the maximisation of the cumulative reward, in which the player will try and maximise their gains while playing on a limited budget. Of course, the asymptotic result will be the same, as the playing whishing to optimize their gains will choose the best arm, however when the rewards functions are unkown the behaviour might be completely different.

UCB is a class of algorithms commonly used when facing the exploration-exploitation dilemma. Each bandit arm is associated with a distribution whose mean is a priori unknown to the learning agent. When pulling an arm, the learning agent observes an independent reward drawn from the distribution of the chosen arm. The goal of the agent is to maximize the sum of observed rewards. To guide the choice of the learner, arm scores have been proposed [START_REF] Agrawal | Sample Mean Based Index Policies with O(log(n)) Regret for the Multi-Armed Bandit Problem[END_REF] to construct upper confidence bounds (UCB) based on the empirical mean of arm-specific rewards and the number of arm pulls. In the UCB class of algorithms, an important breakthrough was the introduction of algorithms with a finite-time analysis [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF]. Specifically, in the UCB1 algorithm [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF] that we present in Algorithm 2, the score B i can be interpreted as the largest statistically plausible mean value of arm i, given the Chapter 2 -Technical Introduction Algorithm 2 UCB Algorithm [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF] Input: Budget N , number of arms K Unknown environment: µ 1 , . . . , µ K that are the expected values of K Bernoulli distributions associated to the K arms i.e., ∀1 ≤ i ≤ K the probability of 1 is µ i and the probability of 0 is 1-µ i . The learning agent has access only to the output of a reward function pull(.), where pull(i) randomly returns 0 or 1 according to the associated Bernoulli distribution.

Output: Sum of observed rewards for all arms

B i ← s i n i + 2 ln(K) n i
◃ First term for exploitation and the second for exploration ◃ Exploration-exploitation phase: pull one selected arm at each round t 7:

for K + 1 ≤ t ≤ N do ◃ Only a budget of N -K is left 8: i m ← arg max 1≤i≤K (B i ) ◃ i m is the arm with maximum B value 9:
r ← pull(i m ) ◃ Pull arm i m and update the corresponding variables 10:

s im ← s im + r 11: n im ← n im + 1 12: for 1 ≤ i ≤ K do ◃ Update B
B i ← s i n i + 2 ln(t) n i
◃ B i is an upper confidence bound on µ i return s 1 + . . . + s K ◃ Return sum of observed rewards for all arms observed rewards. After each observation, the scores for all arms are updated. As shown in the pseudo-code in Algorithm 2, the UCB algorithm follows the principle of optimism in the face of uncertainty and chooses to pull next the arm with the largest updated B i score. This principle suggests to follow what seems to be the best arm, based on the optimistically constructed scores. The same principle is employed in various sequential decision making problems (see [START_REF] Munos | From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning[END_REF] for a survey). Note that an arm i might have the largest score due to its empirical mean (the exploitation term) and/or to the uncertainty one has about the true arm value (the exploration term), directly dependent on how many rewards from arm i were observed.

-Cryptography

Cryptography

Asymmetric cryptography

Definition 2.3.1 (PKE). Let λ be a security parameter. A public-key encryption (PKE) scheme is defined by (G, E, D):

• G(1 λ ) returns a public/private key pair (pk, sk).

• E(pk, m) returns a ciphertext c.

• D(sk, c) returns with overwhelming probability the plaintext m, for c = E(pk, m).

Definition 2.3.2 (Paillier encryption scheme). We denote by Z n , the ring of integers modulo n and by Z × n the set of invertible elements of Z n . The Paillier cryptosystem is a public key encryption scheme where:

• G(1 λ ) generates two prime numbers p and q according to λ, sets n = p • q and Λ = lcm(p -1, q -1) (i.e., the least common multiple), generates the group

(Z * n 2 , •), randomly picks g ∈ Z * n 2 such that M = (L(g Λ mod n 2 )) -1 mod n exists, with L(x) = (x -1)/n. It sets sk = (Λ, M ), pk = (n, g), and returns (sk, pk). • E(pk, m) randomly picks r ∈ Z * n , computes c = g m • r n mod n 2
, and outputs c.

• D(sk, c) computes m = L(c Λ mod n 2 ) • M mod n,
and outputs m.

Partially Homomorphic Scheme

Paillier's cryptosystem is a partial homomorphic encryption scheme. Let m 1 and m 2 be two plaintexts in Z n . The product of the two associated ciphertexts with the public key pk = (n, g),

denoted c 1 = E(pk, m 1 ) = g m 1 • r n 1 mod n 2 and c 2 = E(pk, m 2 ) = g m 2 • r n 2 mod n 2
, is the encryption of the sum of m 1 and m 2 , i.e., E(pk, m 1 ) • E(pk, m 2 ) = E(pk, m 1 + m 2 mod n). Indeed, we have:

E(pk, m 1 ) • E(pk, m 2 ) = c 1 • c 2 mod n 2 = (g m 1 • r n 1 ) • (g m 2 • r n 2 ) mod n 2 = (g m 1 +m 2 • (r 1 • r 2 ) n ) mod n 2 = E(pk, m 1 + m 2 ) .
We also remark that:

E(pk, m 1 ) • E(pk, m 2 ) -1 = E(pk, m 1 -m 2 ).

AES-CBC symmetric encryption

AES [START_REF]Advanced Encryption Standard[END_REF] is a NIST standard for symmetric encryption that encrypts messages of 128 bits. AES is used as a block cipher, for instance using CBC mode (Cipher Block Chaining).

Chapter 2 -Technical Introduction Definition 2.3.3. AES-CBC The AES-CBC cryptosystem is a symmetric encryption scheme defined by a triple of polynomial-time algorithms (KeyGen, Enc, Dec) and a security parameter λ such that:

• KeyGen(1 λ ) generates Key, a uniformly random symmetric key of 128, 192 or 256 bits, according to λ.

• Enc(Key, m, IV ) splits m in blocks of 128 bits m 0 , . . . , m n (padding bits may be added if m n is smaller than 128 bits). Enc computes c 0 = E(Key, m 0 ⊕ IV ), where E is the AES encryption [START_REF]Advanced Encryption Standard[END_REF] and IV is a random 128-bits number. By x ⊕ y we denote the standard bit-wise xor operation between two bit strings x and y. Then, Enc computes

c i = E(Key, c i-1 ⊕ m i ) for 1 ≤ i ≤ n and returns the tuple ((c 0 , . . . , c n ), IV ).
• Dec(Key, c, IV ) splits c in blocks of 128 bits c 0 , . . . , c n and computes m 0 = D(Key, c 0 ) ⊕ IV , where D is the AES decryption [START_REF]Advanced Encryption Standard[END_REF]. Similarly, Dec computes m i = D(Key, c i ) ⊕ c i-1 for 1 ≤ i ≤ n and returns m 0 , . . . , m n .

IND-CPA

We first recall the notion of negligible function in order to define the IND-CPA security notion. The adversary, knowing m 0 , m 1 and c, is allowed to perform any number of polynomial computations or encryptions of any messages, using the encryption oracle, in order to output a guess b ′ of the encrypted message in c chosen by the challenger.

Definition 2.3.4. A function

γ : N → R is negligible in λ, and is noted negl(λ), if ∀c > 0, ∃λ 0 , ∀λ > λ 0 , γ(λ) < λ -c .

We now define how a probabilistic polynomial-time (PPT) adversary

Intuitively, Π is IND-CPA secure if there is no PPT adversary who can guess b with a probability significantly better than Π is IND-CPA secure if α -1 2 = negl(λ).

-Cryptography

Both cryptographic schemes mentioned earlier in this section are IND-CPA: We provide a new and thorough analysis of both algorithms, with results of interest to other existing constructions, and we correct a slight mistake that was made in a previous version of this work.

We also introduce a novel (non tight) lower bound on the error rate, thus helping to determine how close to optimality a filter is.

These theoretical results are confronted with detailed benchmarks, and matched against the performance of other filters from the literature, proving the efficiency of QHTs, both on an entire stream or on a sliding window.

Finally we discuss the effect of adversarial inputs for hash-based duplicate filters similar to QHT.

This work is joint with Rémi Géraud-Stewart and David Naccache. This is an extended version of a work presented at the 34th ACM/SIGAPP Symposium On Applied Computing, SAC 2019, and published as [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF].

Introduction and preliminaries

Amongst other possible attacks on a protocol, there exists a very simple one, called 'replay attack'. In this scenario, an attacker intercepts a valid transaction on the network, and then sends the exact same message, pretending to be a valid user [START_REF] Denning | Timestamps in key distribution protocols[END_REF]. Similarly, oracle attacks are models in which the attacker can deduce information about a hidden information, by for instance repeatedly sending invalid data, until the oracle accepts the input. Such attacks have been carried on SSL, IPSEC [START_REF] Vaudenay | Security Flaws Induced by CBC Padding -Applications to SSL, IPSEC, WTLS[END_REF], and have even led to password interception over SSL/TLS channels [START_REF] Canvel | Password Interception in a SSL/TLS Channel[END_REF].

One solution for blocking these attacks consists in the use of a nonce, a unique, cryptographically random, number. The nonce guarantees the 'freshness' of the message, as the receiver discards all messages using previous nonces. In this chapter,

-Related Work

we discuss about how one can store nonces, and detect duplicates, especially when available memory is low.

This problem has been studied in the literature as the approximate membership problem [START_REF] Dietzfelbinger | Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)[END_REF], or the duplicate detection problem [START_REF] Elmagarmid | Duplicate Record Detection: A Survey[END_REF], while the first paper on the topic was written by Bloom [START_REF] Burton | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF].

Note that the duplicate detection problem is not only useful in security, but also in many other fields. For instance, the same problem arises naturally in many applications: backup systems [START_REF] Fu | Design Tradeoffs for Data Deduplication Performance in Backup Workloads[END_REF] or Web caches [START_REF] Fan | Summary Cache: A Scalable Wide-area Web Cache Sharing Protocol[END_REF], search engine databases or click counting in web advertisement [START_REF] Metwally | Duplicate Detection in Click Streams[END_REF], retrieval algorithms [START_REF] Borg | A Replicated Study on Duplicate Detection: Using Apache Lucene to Search Among Android Defects[END_REF], data stream management systems [START_REF] Babcock | Load shedding for aggregation queries over data streams[END_REF]. In each of these usecases, duplicate detection can lead to increased performance (a cache able to detect if a page is indeed cached), increased efficiency (a backup system will not backup twice the same file, a web crawler won't scan twice the same page), or increased security (duplicate clicks can be interpreted as fraud).

In many cases, it is generally not possible to store the whole stream in memory, therefore practical solutions to this problem must somehow trade off memory for accuracy. The special case of finding one single duplicate in a given -fixed-dataset has a known optimal solution [JST10; KNP+17], but to the best of our knowledge no such results exists for detecting all (or most) duplicates in an unbounded stream.

Related Work

Hash-based Filters

Filters rely on hashing to efficiently answer the duplicate detection problem. These filters are often a variation over the well-known Bloom filters, introduced in [START_REF] Burton | Space/Time Trade-offs in Hash Coding with Allowable Errors[END_REF]. A Bloom filter uses an array T of M bits (usually M being a power of 2), initially all set to 0. k hash functions h i , over the range [0, M -1), are also needed. Insertion of an element e is made by setting all T [h i (e)] to 1. Detection of an element f is the logical AND of all cells T [h i (f )]: if the AND value is 0 (i.e., if at least one bit T [h i (f )] is equal to 0), then emit UNSEEN, otherwise emit DUPLICATE. An illustration is depicted in Figure 3.1.

It is easy to see that this approach has an FNR of 0. However, as the stream grows, the FPR gets worse, and in the limit of an infinite stream the FPR is 1. Many variants have been proposed in the literature to compensate for this effect [START_REF] Tarkoma | Theory and Practice of Bloom Filters for Distributed Systems[END_REF], mostly by allowing deletion [CM03; CM05], but doing so increases the FNR.

Alternatively, other filters prefer to store fingerprints: this is the rationale behind several recent constructions, such as [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF][START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF].

The data structures most interesting to our question are the following:

• Stable Bloom Filters (SBF) [START_REF] Deng | Approximately detecting duplicates for streaming data using stable bloom filters[END_REF] • Streaming Quotient Filter (SQF) [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF] • Cuckoo Filter [FAK+14]

x h 1 h 2 h 3 y h 1 h 3 h 2 Figure 3
.1: Illustration of a Bloom filter with 10 cells and 3 hash functions. The element x is added to the filter, so the 3 corresponding bits of index h i (x) (not necessarily distinct) are set to 1. When querying for y, the filter returns UNSEEN as one of the hashes h i (y) points to a null bit.

• Block Decaying Bloom Filter (b_DBF) [START_REF] Shen | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows[END_REF] • A2 Filter [START_REF] Yoon | Aging Bloom Filter with Two Active Buffers for Dynamic Sets[END_REF] Cuckoo filters [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF] requires a minimal adaptation for unbounded streams: in the original paper, failure is emitted after some number of relocations; we just discard the failure. Theoretical analysis of this new structure is not addressed in this chapter.

Structures from [CLJ+17; GWC+10] are not considered in this chapter, as they require an unbounded amount of memory.

Note that, for analysis purposes, all these papers consider hash functions as pseudo-random functions. We make the same assumption.

Streaming Quotient Filter

One construction which we must describe at length is the Streaming Quotient Filter (SQFs) [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF]. Given an element e, a certain fingerprint1 s(e) is stored in an array, at row h(e) and a certain column amongst k. This array constitutes the filter's state.

The filter's construction uses integers q, k, r, r ′ < r and a hash function h : {0, 1} * → {0, 1} q+r . The filter's state is an array of 2 q rows and k columns, each holding a σ-bit element (with σ = r ′ + ⌈log 2 (r + 1)⌉), or the special empty symbol ⊥. The filter's state is initially ⊥ in every cell.

Then, [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF] describes Stream(e) as follows:

• Compute h(e). Its q most significant bits define h q (e), and the r least significant bits define h r (e).

-Contributions and Organisation

• Let ω(h r (e)) be the Hamming weight of h r (e), and let h r ′ (e) be r ′ bits deterministically chosen from h r (e), e.g., the r ′ least significant bits of h r (e). Let s(e) ← h r ′ (e)∥ω(h r (e)) where ∥ denotes concatenation.

• If s(e) is already stored in the row numbered h q (e), emit DUPLICATE.

• Otherwise, store s(e) in one empty cell of that row. If no empty cell exists in the row, store s(e) in one random cell of the row, replacing any fingerprint previously stored there. Emit UNSEEN.

For instance, let us take q = 5, r = 4, r ′ = 2. Take some element e, assume that h(e) = 101110100, we get h q (e) = 10111, h r (e) = 0100. Taking the r ′ least significant bits for h r ′ (e), we get h r ′ (e) = 00. We also have ω(h r (e)) = 001, so e's fingerprint is 00001 and will be stored in the row numbered 23 (as 23 = 0b10111).

0 1 0 0 1 1 0 0 0 0 0 x h 1 h 2 h 3 y h 1 h 3 h 2 Figure 3
.2: Illustration of the SQF. For an unseen element e, its fingerprint s(e n ) = h r ′ (e n )∥ω(h r (e n )) is inserted in the row T [h q (e n )], in an empty cell. In this example, h q (e n ) = 2 q -1. If there is no such empty cell in T [h q (e n )], the fingerprint is stored in a random cell of the row.

Contributions and Organisation

In this chapter, we introduce a new structure, the QHT (Quotient Hash Tables), which stems from an improvement of an existing filter, the SQF [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF].

We first explore in Section 3.4 the limitations of the 'naive' duplicate detection problem, and formulate some lower bounds on filter saturation in the case of an infinite sliding window.

Then, we analyse the SQF design before correcting its errors, thus creating the QHT, in Section 3.5, and provide a correction of SQF error rate. We also provide a formal description of the QHT false positive and false negative rates in Section 3.6, which match the predictions made by Theorem 3.4.1 from Section 3.4.1.

We then compare QHT to the literature. In Section 3.6.3, we show that for the same efficiency, a QHT requires 33% less memory than an SQF in optimal settings. Chapter 3 -Quotient Hash Tables In Section 3.7 we introduce heuristic improvements to QHT, describing a structure we call QQHTD.

Then, we run extensive benchmarks of QHT and other existing filters in Section 3.8. We experimentally prove that QHTs perform faster than any other filter, and in every situation, is either the best or the second best ranking filter.

Finally, in Section 3.9, we explore the behaviour of QHTs in an adversarial setting.

Redefining the Problem of Duplicate Detection

While the problem defined in Section 2.1.1 is quite simple and intuitive, we show with Theorem 3.4.1 that this 'naive' definition of duplicates is unfit for duplicate filters. Instead, it is better to use a narrower definition, with the introduction of a sliding window.

Filter Saturation

In order to prove the claim that filters saturate, we interest ourselves to the asymptotic error rates of a filter. Theorem 3.4.1. Let FNR ∞ and FPR ∞ be the asymptotic false negative and false positive rates of any filter (i.e., the FNR and FPR on a stream of size going to infinity).

If |Γ| ≫ M , then FNR ∞ + FPR ∞ = 1, which characterises random filters (i.e., filters answering randomly to any query).

Proof. First note that random filters always verify the relation FNR + FPR = 1: given that a random filter will return DUPLICATE with a probability of p, an unseen element will be classified as DUPLICATE with probability p, and a duplicate will be classified as UNSEEN with probability 1p, hence the result. Now, on infinite streams, filters are saturated with information. Given that a filter can only store at most one element per bit (cf. Section 2.1.1), a filter of size M can remember at most M distinct elements. However, after f M insertions (with f ≫ 1), and assuming that |Γ| ≫ M , the filter remembers at most a proportion

1 f ≪ 1 of stream elements.
It can be seen that the error rate of a filter can be modelised as FPR + FNR = ER = µ(η), where µ is a function µ : [0, 1] → [0, 2], and η is the proportion (in terms of bits of information) of the stream that the filter has in memory2 . Moreover, we have µ(0) = 1 as a filter knowing nothing about the stream cannot answer better than random.

Hence, in our situation of a saturated filter, assuming the function µ is continuous at 0, the filter knows at most 1 f of the stream, hence the asymptotic error rate will be

ER ∞ = FPR ∞ + FNR ∞ = lim f →∞ µ( 1 f ) = 1.

-Redefining the Problem of Duplicate Detection

Interpretation. The interpretation of these results could suggest that streaming filters are useless: they need more memory than a random filter, despite being asymptotically equivalent. However, this is only true because of our hypotheses and definitions: we define a false negative to be a duplicate element claimed as unseen by the filter. However, after some amount of time, it is often acceptable that the element may be considered as unseen again: for instance a nonce is theoretically unique, but in practice after a reasonable amount of time nonce reuse is not a vulnerability. For this reason, adapting false positive and false negative to sliding windows may be relevant here. Moreover, we assumed that all elements of the stream had the same probability of occurrence. In practice, this hypothesis is not always correct, and as we will later see in Section 3.8 (page 48), filters operating on real data perform significantly better than random filters, and resist better to saturation. Note that, despite the limitations of the problem defined in Definition 2.1.1, it is the most common definition used in duplicate detection related papers [DNB13; DD06; Yoo10].

Finally, while Definition 2.1.1 does not offer a satisfying problem for real-life applications, the asymptotic relation FPR ∞ + FNR ∞ = 1 offers a good opportunity to verify the validity of the FPR and FNR formulae.

Lower Bound on Saturation

We see that all filters inevitably saturate before becoming as inefficient as a random filter. Hence, it is natural to ask oneself what the optimal limit is, i.e., what the slowest convergence to saturation is. We provide the following result, which we found after the publication of our paper [GLPN19]: Theorem 3.4.2. Let E = (e 1 , . . . , e n ) be a stream of elements uniformly selected from an alphabet of size |Γ|. For any duplicate filter of size M , and any sliding window size w, the error probability EP w n (defined by EP w n = FP w + FN w ) is such that

EP n ≥ 1 - 1 -1 -1 |Γ| M 1 -1 -1 |Γ| min(n,w)
for any n > M .

Especially, for any filter of size M , the asymptotic error probability

EP w ∞ is such that EP w ∞ ≥ 1 - 1-1-1 |Γ| M 1-1-1 |Γ| w ≈ |Γ|≫w>M 1 -M w .
Proof. Let's first prove the theorem for w = ∞. In order to prove this result, note that a perfect filter, as noted in Theorem 2.1.1, must use at least 1 bit to store one element (and the bound is not tight for usual amounts of memory). Since the filter has M bits of memory, we conclude that a perfect filter can store at most M elements in memory. Assume that such a filter exists. Because the stream is random, we can assume without loss of generality that the filter stores the M last elements of the stream: any other strategy cannot yield a lower error rate, given the stream is random.

Chapter 3 -Quotient Hash Tables

Let us derive the error rate of such a filter. If an element is already stored in the filter, then the optimal filter will necessarily answer DUPLICATE. On the other hand, if the element is not in memory, a perfect filter will answer DUPLICATE with some frequency f , corresponding to probability p = 1

f . An unseen element, by definition, will be unseen in the M last elements of the stream, and hence will not be in the filter's memory, the filter will return UNSEEN with probability 1p. For this reason, this optimal filter has a false positive probability of p.

On the other hand, a duplicate element e n will be classified as UNSEEN if and only if it was not seen in the last M elements of the stream, and the filter answers UNSEEN. Let C be the event "There is a duplicate of e n in the M previous elements of the stream", and let D be the event "There is at least one duplicate in the stream (e 1 , . . . , e n )". Note that

P [C ∩ D] = P [C] as C ⊂ D.
We have that e n will trigger a false negative with probability

P n = (1 -P [C|D])(1 -p) = 1 - P [C ∩ D] P [D] (1 -p) = 1 - P [C] P [D] (1 -p) = 1 - 1 -P [ C] 1 -P [ D] (1 -p) P n =   1 - 1 -1 -1 |Γ| M 1 -1 -1 |Γ| n    (1 -p)
Hence, the error probability of the perfect filter is EP n = P n + p, which can be rewritten as EP n = 1 -

1-1-1 |Γ| M 1-1-1 |Γ| n (1 -p) + p = 1 - 1-1-1 |Γ| M 1-1-1 |Γ| n (1 -p), which is minimized when p = 0.
Given that, by definition, a perfect filter has the lowest error rate of any filter, we get the desired result.

The adaptation of the proof for any w is immediate.

Note, as highlighted in the proof, that this bound is not tight, and that better bounds may exist. Also note that this bound only applies when the stream is random: when patterns are found in the stream, information theory informs that data may be stored more efficiently.

Finally, we observe, for |Γ| ≫ M , that the lower bound on the asymptotic error rate of a perfect filter on an infinite sliding window becomes ER ∞ 1e M |Γ| ≈ 1, which is another proof of Theorem 3.4.1.

3.5 -Revisiting SQF: Quotient Hash Table

Revisiting SQF: Quotient Hash Table

SQF is introduced and analysed in [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF]. However, several crucial mistakes were made in that analysis. We focus here on four of them that directly impact the claim of SQF near-optimality. 2. In their FP derivation, the authors neglected the terms of order > 1 in geometric sums, which led to very large approximations, especially when the sum is infinite;

3. Similarly, their asymptotic analysis of the FN fundamentally relies on the fact that the last term of a geometric sum converges to zero, from which the authors claim the whole sum is close to zero;

4. Cells in the filter's state are not independent: in particular, in every row, nonempty cells hold different values (by design). This affects the computation of the error rates.

Correcting these errors (see Sections 3.6.1 and 3.6.2 below, pages 36 and 40 respectively), and using the same approximation than [DNB13] used3 , 2r r ≈ 4 r √ πr , we derive a correct value of the SQF asymptotic FPR and FNR:

FPR ∞ ≈ k 2 r ′ √ πr FNR ∞ ≈ 1 - k 2 r ′ √ πr
that disagree with [DNB13] -most significantly, neither the FPR nor the FNR decrease to 0, contrarily to what was claimed. Interestingly, the suggested parameters (r = 2, k = 4, r ′ = r/2 = 1) indeed achieve an FNR of 0 as the authors claim -but also an FPR of 1. With these values, only 4 distinct fingerprints exist, and they can all be stored in the 4 cells there exist per row. When the filter is full, any duplicate will be reported as such, hence a FNR of 0. But every new element will also be reported as duplicate, hence a FPR of 1.

Further more, there is redundancy between the Hamming weight ω(h r (e)) of h r (e) and the reduced remainder h r ′ (e). For instance, if h r ′ (e) contains at least one bit set to 1, we know that ω(h r (e)) ̸ = 0. Intuitively this means SQF is wasteful, and we could expect to avoid collisions in the filter's state by using a better adjusted encoding: this intuition happens to be correct as we show below (see Section 3.6.3, page 44).

Chapter 3 -Quotient Hash Tables

Full-size Hashing, Memory Adjustments

Our first and main observation is that SQF's fingerprint scheme (a hash and a Hamming weight of part of the hash) can be fruitfully replaced by a single hash function of the same size. Not only does this simplify the theoretical analysis, it also provides a much more efficient use of the available space, as the Hamming weight contains information already contained in the hash.

As a reminder, for an element e, an SQF computes a hash h(e) = h q (e)∥h r e of q + r bits, and from h r (e) retrieves r ′ bits, thus forming h r ′ (e). Then the SQF stores the fingerprint h e r ′ ∥ω(h r (e)) with ω(h r (e)) be the Hamming weight of h r (e). Hence, we see that both h e r ′ and ω(h r (e)) contain bits of information about h r (e), which leads to redundancy and lack of compactness in the information stored.

Hence, instead of storing h e r ′ ∥ω(h r (e)), we suggest to simply store a hash h ′ e of the same size. As we will see later on, this improvement also significantly simplifies the error rate analysis.

Our second improvement to SQF is to use more flexible hash functions, that give much more flexibility in adjusting the total memory M of the filter. As said previously, SQF uses tables of size 2 q , where q is a fixed parameter. This parameter lacks flexibility, as it requires that SQF's memory is a multiple of 2 q . If we allow for a hash function with image on an arbitrary range [0, N ] for any N (and not [0, 2 q -1]), we allow our structure to be more resilient to any amount of memory we can have. While this improvement does not lead to a change in cases where the available memory is optimally designed, it however allows for more flexibility for users.

Combining these two effects, we obtain our new structure, which we call the Quotient Hash Table (QHT). We give its pseudocode in Algorithm 3.

The QHT takes three arguments N, s, k. From this we create a table of N rows with k cells each. Each cell has a capacity of s bits, i.e., there are S = 2 s possible fingerprints in our system. The storage of a new element is similar to the one in SQF.

Empty Cells

SQF and QHT as described above make essential use of the "empty" cells in T . The need for this feature is present for all fingerprint-based structures including Cuckoo filters [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF]. Other constructions, not relying on fingerprints, do not face this issue, including SBF [START_REF] Deng | Approximately detecting duplicates for streaming data using stable bloom filters[END_REF] and b_DBF [START_REF] Shen | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows[END_REF]: in these schemes, 0 always codes for absence. However, a low-level implementation cannot rely on the availability of such a special value. Our options are to initialise all cells to 0 and either:

1. treat 0 as a fingerprint; 2. if an element has a fingerprint of 0, reassign its fingerprint to 1;

3. while an element has a fingerprint 0, compute a new fingerprint based on some deterministic scheme.

3.5 -Revisiting SQF: Quotient Hash Table Algorithm 3 QHT Setup and Stream

1: function Setup(M, s, k) ◃ M > sk and 0 < k ≤ 2 s 2: Let N ← ⌊M/(k • s)⌋ 3:
Choose a hash function h over [0, N -1]

4:

Choose a hash function f over [0, 2 s -1]

5:

Let T be a N × k array with s-bit cells, initialized to ⊥

1: function Stream(e) 2:
for each cell b i in row T [h(e)] do 3:

if b i = f (e) then 4:
return DUPLICATE

5:

Let b ∅ be the first empty cell in row T [h(e)]

6:

if b ∅ does not exist then 7: b ∅ $ ← T [h(e)] 8: Store f (e) in cell b ∅ 9:
return UNSEEN

The first option is at a risk of a high false positive rate, even for small streams: when a new element, whose fingerprint is 0, should be stored in an empty cell, it is instead dismissed as a duplicate. More specifically, before the filter is completely filled, a new element has probability at least 1 S to be false positive, where S is the number of distinct possible fingerprints, which leads to a high number of false positive at the beginning of any stream.

The second option is a bit faster than the third: the third option needs, on average, S S-1 = 1 + 1 S-1 hash computations for each insertion, whereas the second option only needs 1. On the other hand, the third option has better statistical properties, making the analysis simpler. While not specified in their paper [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF], the second solution was chosen in the official Cuckoo filter implementation4 . On the opposite, we retain the slower, but easier to analyse option of re-fingerprinting.

Semi-sorting

The technique of semi-sorting was introduced in [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF] to shave some extra storage. The idea is as follows: treating empty cells as cells containing "0" fingerprint, for each row, sort the cells by their fingerprints, and then encode the result. Given that, for s = 4 and k = 4, only 3,876 possible sorted states exist, and as such a sorted state can be stored using only 12 bits, as opposed to the 16 bits required to store four 4-bit fingerprints.

The same optimization can be used for QHT. In practice, [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF] recommend its use when using 4 cells of 4 bits each.

Comparison with Hash Tables

As our structure QHT relies on hashes, the natural question is to know whether our structure is more efficient than a hash table. The most notable difference is that we do not store the element in its entirety, but rather its hash compaction, as described in [START_REF] Wolper | Reliable hashing without collision detection[END_REF]. Moreover, it can be seen that a hash map is indeed a QHT, wherein the number of rows is equal to 1. QHT being a superset of hash maps, we have the guarantee that we cannot perform worse. Other implementations of hash tables, such as Hashmaps in Java, are closer to our structure. However, we have a fixed number of cells per row, which is not the case in an Hashmap.

In a nutshell, one can say that a QHT is a hash map of fixed size using hash compaction techniques.

Error Rate Analysis

False Positive Rate

Consider a QHT with N rows, k cells per row, and s-bits fingerprints. For simplicity, further assume that no cell is empty (which is true after some time), and that the stream is sampled uniformly at random from Γ. We want to derive the probability of triggering a false positive. FPR Intuition. We first give an intuitive, and simple, estimation of the false positive rate. Even though not rigorous, and lacking interesting data about saturation as we discuss later, it helps confirming that the results obtained in the next section are indeed correct.

Let us consider an element e which has never been seen. e is assigned to row h q (e), and we want to know the probability that its fingerprint f (e) is already stored in one of the cells of the row, resulting in a false positive. In this section, we assume that the stream being uniform, the fingerprints stored in the row h q (e) are all equiprobable (with probability 1 S , where in our case S = 2 s ), so the probability of finding s(e) in one row is simply k S . Hence, we get an estimate that the FPR will be approximately k S . Despite being simple and elegant, this approach does not give much hindsight about how fast this limit is reached. FPR Derivation. We now derive an exact value for the FPR of a QHT.

Theorem 3.6.1. For a QHT of N rows, k cells per row and S possible fingerprints and assuming N S ≪ |Γ|, and for a sliding window of size w ≪ |Γ|, the FPR after m insertions on a sliding window of size w is

FPR w m = k S   1 - (N k -1) 1 -1 -1 N k m m  

-Error Rate Analysis

Proof. We instead prove the following lemma, from which the proof of the theorem becomes trivial (the theorem can be deduced from the lemma with a simple arithmetic mean, given that

FPR m = 1 m m i=1 FP i ):
Lemma 3.6.1. For a QHT of N rows, k cells per row and S possible fingerprints and assuming N S ≪ |Γ|, with a sliding window of size w, the probability FP m that an unseen element inserted after m other elements triggers a false positive on a sliding window of size w (with w ≪ |Γ|) is

FP w m = k S 1 -1 - 1 N k m
An element e is a false positive if and only if e has not been encountered in the current sliding window, but Detect(e) = DUPLICATE. This event can be triggered by two possibilities:

• The presence, in the filter, of another element e ′ with a hash and fingerprint colliding with those of e. This is called a false duplicate.

• The presence, in the filter, of the same element e, but which was inserted more than w epochs before.

These two elements are referred to as false collisioners: they create a collision when there should not be one. If a false collisioner is still in the filter when e arrives, we refer to the event as a hard collision.

Our first remark is that the only false collisioner that may create a hard collision with e is the latest false collisioner inserted before e arrives: let us assume that e 1 , e 2 are false collisioners, and that e 1 arrives before e 2 . When we insert e 2 in the filter, e 1 is either still in the filter or has been evicted.

• If e 1 has been evicted, then e 1 will not hardly collide with e.

• If e 1 is still in the filter, then e 2 will be claimed as a duplicate and dismissed.

However, if we look at the table T storing all fingerprints, dismissing e 2 is strictly equivalent to replacing e 1 by e 2 . Consequently, every false collisioner is erased by any new false collisioner, and only the latest false collisioner can cause a hard collision. As a result, we will only focus on the probability that the latest false collisioner (before e arrives) causes a hard collision.

Probability of non-eviction of the latest false collisioner until e arrives.

Let us assume that the latest false collisioner appears at position i of the stream E = {e 1 , e 2 , . . . , e m , e}, in other words, e i is the latest false collisioner in the stream before e.

Now, e i has to remain in the filter until e arrives, even though new elements are added. Let us suppose that element e j , i < j ≤ m, evicts e i from the filter. For e i to be evicted, the following conditions must be true:

Chapter 3 -Quotient Hash Tables • h(e j ) = h(e i )
• s(e j ) is different from all the other fingerprints stored in the row T [h(e j )]

(knowing that one of the cells contains s(e i ))

• s(e j ) is inserted into the cell in which s(e i ) is stored Since we know that e i is the latest false collisioner, we cannot simultaneously have h(e j ) = h(e i ) and s(e j ) = s(e i ). As such, the first two conditions are not independent. Let P hs be the probability that these two conditions are satisfied. Given that e i is the latest false collisioner, there are only N S -1 possibilities for the couple (h(e j ), s(e j )). Moreover, among these N S-1 states, only S-1 verify the first condition, and among these S -1 states, only S -k verify the second condition. Finally, P hs = S-k N S-1 . If we assign the latest event to the probability P selection , we immediately get P selection = 1 k . Finally, the probability P ¬evict of e i not being evicted by e j is P ¬evict = 1 -P hs P selection and:

P ¬evict = 1 -S-k k(N S-1)
Now, e i has to avoid eviction by every element before e arrives, i.e., by all elements e i+1 , . . . , e m , which happens with probability P (hc

) i = (P ¬evict ) m-i .
At that point, we know the probability that a hard collision happens when the latest false collisioner has been inserted at position i.

Probability of the last false collisioner to be at position j. The probability of any element e ′ being a false collisioner depends on the position of e ′ in the stream. Let j be the position of e ′ in the stream E = {e 1 , e 2 , . . . , e m , e}: e j = e ′ .

• If mj ≥ w, then e ′ is a false collisioner and can be either a false duplicate (i.e., e ′ ̸ = e but h(e ′ ) = h(e) and s(e ′ ) = s(e)) or equal to e.

• If mj < w, then e ′ can only be a false duplicate.

In the former case, e ′ is a false duplicate or equal to e. Let P fc be the probability of this to happen. We immediately get P fc = 1 N S . In the latter case, let P fd be the probability of e ′ to be a false duplicate. Since we know e ′ ̸ = e, we have

P fd = |Γ| N S -1 |Γ| = 1 N S - 1 |Γ| (amongst |Γ| elements, there
are |Γ| N S who have the same hash h and the same fingerprint s than e, including e, hence the result).

Finally, the probability that e j is the latest false positive is equal to (1 -P fd ) m-j P fd for j > mw, and (1 -P fd ) w (1 -P fc ) m-w-j P fc otherwise.

Summing up the probabilities. Thus, for m > w, the probability FP w m that a false positive happens on the sliding window of size w after m elements are inserted is

3.6 -Error Rate Analysis FP w m = m j=1
(e j is the latest false collision × e j is not evicted until e arrives)

= m-w j=1 (1 -P fd ) w (1 -P fc ) m-w-j P fc × P (hc) j + m j=m-w+1 (1 -P fd ) m-j P fd × P (hc) j = (1 -P fd ) w (1 -P fc ) w P fc m-w j=1 (1 -P fc ) m-j × P (hc) j + P fd m j=m-w+1
(1 -P fd ) m-j × P (hc) j

We have P (hc

) j = 1 -S-k k(N S-1) m-j , P fd = 1 N S -1 |Γ| and P fc = 1 N S , so FP w m = 1 + N S |Γ|(N S -1) w 1 N S 1 - 1 kN w 1 -1 -1 kN m-w 1 -1 -1 kN + 1 N S - 1 |Γ| 1 -1 -1 kN + 1 |Γ| 1 -S-k k(N S-1) w 1 kN -1 |Γ| 1 -S-k k(N S-1) = 1 + N S |Γ|(N S -1) w k S 1 - 1 kN w 1 -1 - 1 kN m-w + 1 N S - 1 |Γ| 1 -1 -1 kN w 1 + 1 |Γ|(1-1/(kN )) 1 -S-k k(N S-1) w 1 kN -1 |Γ| 1 -S-k k(N S-1)
Assuming |Γ| ≫ N S and |Γ| ≫ w, we have

FP w m ≈ k S 1 - 1 kN w -1 - 1 kN m + 1 N S 1 -1 -1 kN w 1 kN ≈ k S 1 -1 - 1 kN m
Note that this derivation is only valid for m > w. Otherwise, we obtain the same result, but in a different way:

FP w m≤w = m j=1 (1 -P fd ) m-j P fd × P (hc) j = 1 N S - 1 |Γ| 1 -1 -1 kN m 1 + 1 |Γ|(1-1/(kN )) 1 -S-k k(N S-1) m 1 kN -1 |Γ| 1 -S-k k(N S-1)
Chapter 3 -Quotient Hash Tables Neglecting all the terms in 1 |Γ| ,

FP w m≤w ≈ k S 1 -1 - 1 kN m Which concludes the proof.
One observation is that the FPR converges to k S . Furthermore, thanks to the expression of FP m , we can see that the more rows there are (i.e., the bigger N is), the slower the FPR reaches its asymptotic (saturated) value.

Finally and more importantly, the FPR w does not depend on w on a first approximation. This is due to the fact that QHT was mostly designed for the cases where w is infinite, and as such w plays no role in the algorithm, and little difference in probabilities when an element is or is not in the sliding window. As such, QHT might be less efficient than other structures on streams with small sliding windows, but still remains a competitive candidate (see Section 3.8.6 below, page 53).

Application to SQF One should be tempted to directly apply this result to an SQF. However, as pointed out earlier, in an SQF fingerprints are correlated and therefore not equiprobable. For instance, consider the SQF with the parameters r = 3, r ′ = 1. Only the hash h r 1 = 000 will lead to the fingerprint 000, whereas both hashes h r 2 = 001 and h r 3 = 010 will lead to the fingerprint 001. However, for an optimal SQF, fingerprints are equiprobable so the analysis above holds for optimal SQFs. In the general case, the authors of [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF] have approximated the probability of fingerprint collision in an SQF with 1 2r ′ √ πr . Replacing 1 S with this probability in our analysis, we get an approximate asymptotic FPR of k 2 r ′ √ πr for SQFs, as announced in Section 3.5.

False Negative Rate

Theorem 3.6.2. For a QHT of N rows, k cells per row, and S different fingerprints, assuming |Γ| ≫ N , then as the number of insertions goes to infinity, FNR ∞ = 1-k S .

In the following proof, we also show that the false negative rate over a sliding window FNR w is directly linked to the sliding window size, as it depends on a summation of w terms. The exact derivation is however left for future work.

Proof. Assume that e is a duplicate, we denote by e i the latest element in the stream such that e i = e. Following the same reasoning as for the FPR, e i will trigger a false negative if and only if e i is removed from the filter before e arrives, and if any false duplicate of e, inserted between the removal of e i and e, is deleted before e arrives.

Let us assume that e i is deleted at time j (this happens with probability P Del i,j ) by something else than a false duplicate. Using similar arguments than in the previous section, we have

P Del i,j = 1 -S-k k(N S-1) j-i-1 S-k k(N S-1)
: the probability of the ith element is deleted by the jth element is equal to the probability of non-deletion by 40 3.6 -Error Rate Analysis

j -i -1 elements ( 1 -S-k k(N S-1)
j-i-1 ) followed by the probability of deletion at the next step ( S-k k(N S-1) ) The probability that all false duplicates, inserted after time j, are deleted before e arrives is 1

-FP n-j . Let a = S-k k(N S-1) , b = k S and c = 1 -1 N k
, and denote by FN i,m the probability, in a stream E = (e 1 , . . . , e m , e) where the latest duplicate of e is inserted at i, that e i is deleted before e arrives and no false positive persists until e,

FN i,m = m j=i+1 P Del i,j (1 -FP m-j ) = m j=i+1 (1 -a) j-i-1 a 1 -b 1 -c m-j FN i,m = a (1 -b) m j=i+1 (1 -a) j-i-1 + ab m j=i+1 (1 -a) j-i-1 c m-j Given that 1 -a ̸ = c (because 1 -a -c = 1 -S-k k(N S-1) -1 + 1 N k = N k-1 N k(N S-1) ̸ = 0 unless N = k = 1
which would not be an interesting filter), we get:

FN i,m = (1 -b) 1 -(1 -a) m-i + ab (1 -a) m-i -c m-i 1 -a -c
The probability FN m of e to be a false negative is then

m i=1 P dup,i • FN i,m
, where P dup,i is the probability that the latest duplicate already seen is e i . In a previous version of this work, we wrongly stated that P dup,i was equal to the value

P ′ dup,i = |Γ|-1 |Γ| m-i 1
|Γ| : this would be true if there was no assumption on the stream, but here we know for a fact that there is already a duplicate somewhere in the stream. Hence, we must not derive P ′ dup,i = P [e i is the latest duplicate], but rather P dup,i = P [e i is the latest duplicate | there is at least one duplicate].

For simplicity, we note by D the event 'there is at least one duplicate'. Observe that D can also be written ∃k ≤ m, e k = e. We also remark that the event 'e i is the latest duplicate' (of e) can be rewritten as (e i = e) ∩ ( j>i (e j ̸ = e)). Hence,

P dup,i = P   (e i = e) ∩   j>i (e j ̸ = e)
P dup,i = P ′ dup,i 1 -P D
Where D is the event 'There is no duplicate' and has a probability

P D = |Γ|-1 |Γ| m . Hence, P dup,i = |Γ|-1 |Γ| m-i 1 |Γ| 1 1- |Γ|-1 |Γ| m .
We obtain the probability FN m that the (m + 1) th element e of the stream will be a false negative:

FN m = m i=1 P dup,i • FN i,m FN m = m i=1 |Γ| -1 |Γ| m-i 1 |Γ| (1 -b) 1 -(1 -a) m-i + ab (1 -a) m-i -c m-i 1 -a -c
For a stream of n elements, the false negative rate FNR n is defined as the average error probability:

FNR n = 1 n n m=1
FN m . For a stream of n elements on a sliding window of size w, the false negative rate FNR w n over the sliding window is defined as the average over the last w elements:

FNR w n = 1 w n m=n-w+1 FN m .
Hence,

FNR n = 1 n n m=1 m i=1 |Γ| -1 |Γ| m-i 1 |Γ| 1 1 -|Γ|-1 |Γ| m (1 -b) × 1 -(1 -a) m-i +ab (1 -a) m-i -c m-i 1 -a -c
Expanding and summing the geometric sums,

-Error Rate Analysis

FNR n = 1 n|Γ| n m=1 1 1 -|Γ|-1 |Γ| m (1 -b) m i=1 |Γ| -1 |Γ| m-i -(1 -b) m i=1 |Γ| -1 |Γ| • (1 -a) m-i + ab 1 -a -c m i=1 |Γ| -1 |Γ| (1 -a) m-i + ab 1 -a -c m i=1 |Γ| -1 |Γ| c m-i FNR n = 1 n n m=1 1 -b - 1 -b 1 -(1 -1/|Γ|) m 1 -((1 -1/|Γ|)(1 -a)) m |Γ| -(1 -a)(|Γ| -1) + 1 1 -(1 -1/|Γ|) m ab 1 -a -c 1 -((1 -1/|Γ|)(1 -a)) m |Γ| -(1 -a)(|Γ| -1) - 1 1 -(1 -1/|Γ|) m ab 1 -a -c 1 -((1 -1/|Γ|)c) m |Γ| -c(|Γ| -1)
We can see that the sum can be rewritten as FNR n = 1 -b+

3 i=1 k i 1 n n m=1 1 -α m i 1 -β m i ,
where k i , α i , β i are various values. To the best of our knowledge, there is no simpler form of the expression

1 n n m=1 1 -α m 1 -β m . However, given that FNR ∞ = lim n→∞ FNR n ,
and because in our case the terms α and β are < 1, we know that lim

m→∞ 1 -α m 1 -β m = 1,
Cesàro's summation tells us that lim

n→∞ 1 n n m=1 1 -α m 1 -β m = 1
as well, so we get the final result:

FNR ∞ = 1 -b - 1 -b |Γ| -(|Γ| -1)(1 -a) + ab (1 -a -c)(|Γ| -(|Γ| -1)(1 -a)) - ab (1 -a -c)(|Γ| -(|Γ| -1)c)
Finally, assuming |Γ| ≫ N k (or even |Γ| ≫ N ), i.e., that there are more distinct elements in the stream that what the filter is able to store, we get the limit rate of

1 -b, which is FNR ∞ ≈ 1 -k S .
A not obvious consequence of the above expression for FNR is that when N increases, which corresponds to using more memory, it is possible to achieve an arbitrary small error false negative rate. The proof is straightforward but tedious, as it requires the substitution of a, b, c by their full expression, before taking the limit. However, a formal computing software such as Mathematica outputted without any problem. Thus, the formal proof was omitted for the sake of simplicity. Another Chapter 3 -Quotient Hash Tables reason for omitting the proof is that the result implies that we have an infinitely growing memory. However, since the beginning we assume memory to be a limited ressource. Moreover, at some point in the infinite growth, one obtains a filter with more bits of memory than the cardinality of stream elements, thus making void the need of any QHT as one can instead use the optimal solution (see Theorem 2.1.1).

Note that FNR ∞ + FPR ∞ = 1, as was predicted by Theorem 3.4.2. The value of FNR ∞ also gives (using the same corrections as for the FPR in Section 3.6.1) the FNR formula for the SQF.

Comparing QHT to SQF

Let us compare the memory required for a QHT to reach the same error rates than an SQF.

Given that both FPR and FNR depend only on k, N and S, imposing the equality on these parameters ensures that both filters have exactly the same FPR and FNR.

Note that S is not a user-chosen parameter, but rather a consequence of other parameters.

Theorem 3.6.3. For exactly the same FPR and FNR, a QHT requires exactly 33% fewer memory than an SQF.

Proof. The proof is made through the following paragraphs.

Deriving S from filters parameters. For a QHT, S is derived from the number of bits of the fingerprint s, with the straightforward relation5 : S = 2 s . For an SQF, however, the relation is more complicated.

When r and r ′ are fixed, for any element e, let h r (e) be decomposed as h r (e) = h r ′ (e)∥f , where h r ′ (e) is the r ′ -bits word used in the fingerprint, h being the rr ′ remaining bits of h r (e). For ω(•) the Hamming weight function, we have s(e) = h r ′ ∥ω(h r (e)). Yet ω(h r (e)) = ω(h r ′ (e)) + ω(f ). We know that ω(h r ′ (e)) is entirely dependent on h r ′ (e), which is already used in the fingerprint. Thus, if we fix h r ′ (e), there are only rr ′ + 1 possible values for ω(f ) and thus for ω(h r (e)). Given that h r ′ (e) can have 2 r ′ different values, we get that S SQF = 2 r ′ • (rr ′ + 1).

Comparing required memory.

For QHTs, we have the relation M QHT = N QHT k QHT s. For SQF, the formula is rather M SQF = N SQF k SQF (r ′ + ⌈log 2 (r + 1)⌉) (because fingerprints occupy r ′ + ⌈log 2 (r + 1)⌉ bits), with r and r ′ being parameters in SQF's settings.

-Error Rate Analysis

Given that N QHT = N SQF and k QHT = k SQF , the ratio

M QHT M SQF is: M QHT M SQF = N QHT k QHT s N SQF k SQF (r ′ + ⌈log 2 (r + 1)⌉) = s r ′ + ⌈log 2 (r + 1)⌉ Given that s = ⌈log 2 (S QHT )⌉ = ⌈log 2 (S SQF )⌉ = ⌈log 2 (2 r ′ • (r -r ′ + 1))⌉, we have M QHT M SQF = ⌈log 2 (2 r ′ (r -r ′ + 1))⌉ r ′ + ⌈log 2 (r + 1)⌉ = r ′ + ⌈log 2 (r -r ′ + 1)⌉ r ′ + ⌈log 2 (r + 1)⌉
Using the recommended settings in [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF] (r = 2, r ′ = 1) the ratio becomes

M QHT M SQF = 2 3 , which concludes the proof.
This result proves that a QHT is always superior to its predecessor SQF, by quite a high margin in terms of memory requirements.

Parameter Tuning

We now precise how to optimise our filter parameters. In the case where w = ∞, we are able to give a full proof, whereas in the general case, we rely on experimental observations. For w = ∞. As noted in Section 3.6.2, no matter the choice of the parameters we have FNR ∞ + FPR ∞ = 1: any particular parameters choice will be a trade off between good FPR and good FNR performance, at least asymptotically. However, when the stream is small enough, one may choose parameters that will maximally delay saturation. Theorem 3.6.4. For a desired asymptotic FPR corresponding to some ratio k S , the configuration leading to the slowest convergence to saturation is the one with the lowest S value.

Proof. We know that M = N k log 2 (S), so plugging this into the FP formula gives

FP m = k S 1 -1 - 1 kN m = k S 1 -1 - log 2 (S) M m
Which means that, for fixed M and k S (i.e., for a fixed memory amount and a fixed asymptotic FPR), log 2 (S) must be as small as possible in order to keep the FP low for as long as possible. Since the FP is as low as possible, the FPR (i.e., the average of all previous FPs) is also as low as possible.

For instance, assume that we want an asymptotic FPR of 25%. The potential values for the couple (k, S) are (1, 4), (2, 8), (4,16) and so on (leading respectively to s = 2, 3, 4). Because of the above relation, we know that setting k = 1, s = 2 will yield the best saturation resistance for the FPR.

Note however that this result does not guarantee a slowest convergence of the FNR. However, experiments show that it is the case indeed.

We compared several QHT of approximately 2 16 bits, with the same ratio k S , but each with a different value for S. We took streams of 100 000 elements (well under saturation value for this amount of memory), from an alphabet of 2 20 elements. Each element of the stream was uniformly randomly selected, leading to a stream with about 4.6% of duplicate elements. We averaged the results on 10 runs.

We observe in Table 3.1 that filters with a small value of S do indeed perform better than filters with a bigger value of S, which concludes the experiment. For arbitrary w. In this case, we were not able to extract a mathematical formula for optimizing the error rate. Instead, we benchmarked several QHTs of 1Mb, with k = 1, and different values of S. We analyzed their efficiency, depending on the sliding window size (ranging from 100 elements to 10M elements), on a stream of 150M random elements of 2 26 bits each. Results are given in Table 3.2. We indeed observe that, for big sliding windows, it is preferable to select a small value of S, whereas for small to very small sliding windows, big values of S are more efficient. However, in this kind of situation, where the sliding window is very small, probabilistic structures might not be useful, as it is probably easier to store all elements in memory. Hence, we conclude that, for all practical applications, one must chose an S as small as possible. Note that S = 2 1 is discouraged, as this only allows for 2 possible fingerprints per row. Given that one fingerprint is used to implement the 'empty' feature (see Section 3.5.2), S = 2 2 is the minimum value one can use in QHTs.

S = 4 S = 8 S =

Further Improvements: QQHTD

Keeping Track of Duplicates

In Algorithm 3, we do not insert anything if the element is detected as a duplicate. However, following [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF]'s example, we can insert it anyway, resulting in a structure we call QHT with Duplicates, or QHTD. We briefly discuss its properties. As we showed previously, the asymptotic FPR of a QHT is k S , which was expected: each row stores k distinct fingerprints, the probability that one of them matches the fingerprint of a unique element is logically k S . Similarly, in QHTD each row stores k fingerprints, not necessarily distinct. The probability that at least one of these fingerprints is the same than the one of an unseen element is FPR

∞,QHTD = 1 -1 -1 S k . Given the results of Section 3.4.1, the asymptotic FNR ∞,QHTD of QHTD is 1 -1 S k .

Queuing cells for a Better Sliding Window

One caveat of the QHT (and QHTD) is the fact that at any insertion, any element of the row is equally likely to be evicted: if this allows an easy FPR and FNR derivation, it makes it functioning a bit counter intuitive. As a matter of fact, one would expect a filter to first forget about the oldest elements before forgetting about the newest ones. Indeed, this behaviour matches the need of a filter operating on a sliding window, without taking into account oldest elements.

The solution we provide for QHT is to order the cells of a given row in a FIFO queue, which means that instead of selecting a random cell in the row for insertion, one will append the fingerprint to the end of the queue, and pop the first element (so that the size of the queue remains constant). Combined with QHTD improvement, this yields Algorithm 4.

Note that classical queues (i.e., doubly chained lists) are not suited for our use, as chains require extra storage bits for pointers. Thus, for our QQHTD we create an array of k elements, in which we manually move every element at each "pop". When k is small (typically less than 5, which it usually is), the time overhead is not significant. Quotient of e: h(e); Fingerprint of e: f (e). return result Finally, note that a QQHTD with one cell par row is equivalent to its QHT counterpart. However, with more cells per row, QQHTDs offer a noticeable improvement over QHTs on real data streams (see Table 3.3).

Benchmarks

Comparison of QHT and QQHTD

In this section, we explore the difference between a QHT and a QQHTD with the same parameters, on the same stream. Note that, for k = 1, QHT and QQHTD are the same structure. We took filters of 65,536 bits each, on streams of 100,000 elements each. One stream issued from our 'real' dataset (10.32% of duplicates), the other a random uniform stream on an alphabet of 2 20 elements (4.62% of duplicates). The stream parameters were chosen so that the error rates would be between 20% and 80%: a small error rate indicates that the filter is almost empty, and an high error rate would indicate saturation. Results are given in Table 3. 3.

We observe that QQHTD offer a small advantage on artifical data, but a significant advantage on real datasets. Thus, while the theoretical gain of the QQHTD improvement seem hard to quantify, they are justified in practice, at least on some streams.

Stream (dup. %)

Filter

k = 2 S = 8 k = 4 S = 16 k = 8 S = 32 k = 16 S =

Comparison of QHT to Other Filters

We first compare QHT to other structures, in the most common setting used in other papers (i.e., on an infinite sliding window). We used filters of size ranging from 10 kb to 8 Mb. We used a real stream of URLs visited by a crawling robot, extracted with [START_REF] Tange | GNU Parallel -The Command-Line Power Tool[END_REF] from the April 2018 Com-monCrawl's dump [START_REF] Nagel | Crawl Archive Now Available[END_REF], which contained 150,000,000 elements. We also used 2 artificial streams of the same length, for which the elements where randomly generated from an alphabet of 2 24 and 2 27 elements respectively, leading to a duplicate rate of about 88% and 38% respectively. The source code of the benchmark is available online 6 , and a standalone library for immediate use has also been developped 7 .

The filters, with their parameters chosen so their asymptotic FPR was as close as possible to the arbitrary value of 25%, are:

• QHT, 1 cell per row, 3 bits per fingerprint. This specific QHT is equivalent to a QQHT or a QQHTD with the same parameters, so we do not include the latter in the benchmark.

• SQF from [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF], 1 cell per row, r = 2 and r ′ = 1

• Cuckoo Filter from [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF], cells containing 1 element of 3 bits each

• Stable Bloom Filter (SBF) from [START_REF] Deng | Approximately detecting duplicates for streaming data using stable bloom filters[END_REF], 2 bits per cell, 2 hash functions, targeted FPR of 0.028

• A2 Filter from [START_REF] Yoon | Aging Bloom Filter with Two Active Buffers for Dynamic Sets[END_REF], targeted FPR of 0.1 on the sliding window.

• Block-Decaying Bloom Filter (b_DBF) from [START_REF] Shen | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows[END_REF], sliding window of 6000 elements.

Results, averaged on 5 runs, are given in Table 3.4, and summarised in Table 3.5. Note that, for better readability, the error rates have been multiplied by 100 in the table. Further more, we recall that the error rate, being defined as ER = FPR + FNR, is bounded by 0 below and 2 above, 1 being the error rate of a random filter. A filter can have worse results than random; for instance a filter which is always wrong has an error rate of 2.

As we can see in Table 3.5, QHT (or QQHTD) are extremely competitive and resist very well to saturation; they also appear to be the most competitive on the real stream. For instance, we observe that QHT can offer an error rate of up to 7.7 points lower than SQF, thus offering a 13% advantage, for the same amount of memory.

Moreover, we observe that b_DBF are efficient, but reach very quickly their saturation. A more detailed analysis of their FPR (see Table 3

Speed Comparison

We also benchmarked the speed of every filter on real-time detection, on a laptop with Intel i7. We used the same filters as in the previous subsection, with a memory of 1 Mb, on a stream of 150,000,000 elements. We averaged, on these filters, the time needed for Insert • Detect to execute for each element. Results are shown in Table 3.6. We observe that safe for SQF, QHT is 6 times as fast as any other filter, and 10 times as fast as b_DBF. Even SQF is 50% slower than QHT. Even with additional features, QQHTD are also faster than SQF by a large magin, because fingerprint derivation is more costly in the latter. As a conclusion, we observe that QQHTD are most suited filters for high-speed analysis.

Filter

Saturation Resistance

Another interesting point is the study of how long a filter resists to saturation on a given stream. As we know from Section 3.4.1, a filter will necessarily reach a saturation state in which it will not be more efficient than a random filter. Yet the number of insertions before this saturation is highly dependent on the filter, and a good filter will reach saturation as late as possible.

We ran a simulation of the same filters as previously, on data streams of respectively 1 000, 10 000, 100 000, 1 000 000, 10 000 000, 50 000 000, 100 000 000 and 150 000 000 elements each. One stream was extracted from our real dataset (about 10% duplicates on 150 000 000 elements), the other one is an artificial streams, with elements of 26 bits each (about 8% duplicates on 150 000 000 elements). The results are plotted in Figure 3.3.

Even though A2 filters performs slightly better on small random streams, we see that QHT are extremely competitive on real streams, as the error rate grows much slower than for other filters. Similarly, b_DBF, at their peak performance, perform as well as QHT on real streams (while being noticeably bad on artificial streams). However, b_DBF parameter tuning is quite hard and unintuitive, and to the best of our knowledge there is no easy way of finding the optimum for a given stream. Furthermore, b_DBF are 10 times as slow than QHT (see Section 3.8.3), for the same performance, in the best case.

On artificial filters, we observe that the conversion between unsaturated and saturated states happen after around one million insertions. This is related with the fact that the filters are 1 Mb big: according to information theory, a filter of 1 Mb cannot remember more than one million elements in the general case. Hence, for any filter, there it is reasonable to assume that after one million insertions, the performances are degrading as the filter starts forgetting about previous elements.

-Benchmarks

From this reasoning, we conclude that while QHT can store about 1 element per bit, some other filters, such as the SBF, cannot and thus have a limited efficiency.

Memory Impact

We also looked at the dual experiment, which is the impact of the filter memory on its efficiency on a given data stream. We consider this experiment to be dual of the previous one, as we saw there is a direct correlation between the memory size, the stream size and the error rate. Hence, we expect to see curves with a similar aspect as in the previous section. This prediction is validated by experience. Because we wanted to observe the 'saturation curve', we slightly changed the parameters from the previous benchmark:

• the filters are the same as in Section 3.8.2,

• we used streams of 10 000 000 elements only,

• the two streams consist of an extract of our real stream (6.88 % duplicates on the first 10 000 000 elements), and an artificial stream of elements of 26 bits (7.09% duplicates)

Note that, for practical purposes, b_DBF filters were only considered in the memory range of 10kb to 30Mb: when there is too little memory, the filter cannot operate. Where there is too much memory, the filter requires counters of more than 64 bits, which we did not implement in our benchmarks. The results are shown in Figure 3.4.

As we can see, the saturation happens when filter has fewer than 10Mb in memory, which is also the number of elements of the random stream. However, on real streams the saturation is much slower, and full saturation is not reached, even when the filters are very small.

On can also observe that there seems to be an inverse relationship between stream size and memory size. This observation is backed by the fact that we know that after m insertions, the probability of a false positive is

FP m = k S 1 -1 -1 N k m .
As seen in Section 3.6.4, we also have

FP m = k S 1 -1 -log 2 (S)
M m , and because

log 2 (S) ≪ M in all practical cases, FP m ≈ k S 1 -e -m log 2 (S)

M

. By consequence, the probability of a false positive is related to the ratio m M , a ratio between the size of the stream m and the memory size M , hence the inverse relationship. Note however that such a relationship might be much harder to derive from the false negative probability (if it exists), but practical results allow us to think that the same inverse relationship is also present.

Influence of the Sliding Window

We use the same filters as in Section 3.8.2, with the addition of another QHT (named QHT8 in the legends), with k = 1 cell per row, and 8 bits per fingerprint, with 1 Chapter 3 -Quotient Hash Tables 10

-Adversarial Resistance

Mb memory, on two streams of 150 million elements: one stream with real data, one stream with random elements from an alphabet of 2 26 elements.

We compare the filters error rate on different sizes of sliding windows 100, 1 000, 10 000, 100 000, 1 000 000, 10 000 000 and 100 000 000 elements.

Note that, even though included in this benchmark for the sake of completeness, sliding windows of small size (say, < 10 000 or 100 000) should not be taken into account for real-life implementation: if one really needs to find duplicates on such a small sliding window, the best solution is simply to implement a queue: the resulting structure remain time-competitive for small sizes, and offers an error rate of exactly 0.

Results are plotted in Figure 3.5. We observe that, even though b_DBF have a slight advantage on real data for real-life sliding window sizes, there is no guarantee that there will always perform as good, as their performance on the random dataset is very low. On the other hand, QHTs are better than any other structure, safe b_DBF, and are at least as competitive than b_DBF on a real case, and much better in a random dataset.

Furthermore, even though of no practical uses, QHTs can be tuned to be extremely performant on small sliding windows as well, thus offering some resilience to the user if they happen to use a probabilistic filter when it is not needed.

From this benchmark, we can make two observations. The first one is that, for all filters, there appears to have an optimum sliding window size. The second one is that b_DBF appears to be more performant than QHT in several instances. However, it appears this happens just on a small memory window: if we do the same benchmark with a different filter size, we obtain different results.

Adversarial Resistance

Now, despite the good performances of QQHTD on normal streams, one may not always assume that the stream is "normal": there may be an attacker trying to fool the filter. For instance if the filter must detect duplicates in order to avoid an attack (nonce requirements), then the question of adversarial resistance is primordial. Theorem 3.9.1. No filter F can resist a false negative attack on an infinite sliding window. More specifically, for any 0 < p < 1, there exists n ∈ N such that A wins the n-false negative game for F, with probability greater than p.

Proof. We craft false negatives in Ω(M ) steps (M being the filter's memory size). Let us remind that no structure can remember more than one element per memory bit. For this reason, the structure can remember at most M different elements. Consequently, if the attacker generates a stream of random unseen elements, then on average each element will stay for M insertions in the filter's memory. More generally, after hM insertions (for some rational h ≥ 1), an element is forgotten with probability at least

P forgot = 1 -(1 -1 M ) hM ≃ 1 -e -h
. Thus an attacker simply generates Ω(M ) unique elements before sending the first element again. M can even be estimated via saturation (see Section 3.4.1). Given that CPU time is

Sliding window size

-Conclusion

cheaper than memory requirements, the attacker keeps her advantage over any filter of any size. Theorem 3.9.2. Assuming finite sliding window size w, and assuming the existence of one-way hash functions and permutations, QHT are (1-( 1-S-k N Sk ) w-1 , w)-resistant to false negative attacks.

Proof. Following [START_REF] Naor | Bloom Filters in Adversarial Environments[END_REF] we replace all hash functions by one-way hash functions, and apply a (secret) one-way permutation on incoming elements, then classically store the results in the filter. Because of the permutation, the attacker gains no advantage in adaptively choosing the elements, thus loosing her advantage of adaptively choosing the elements. Her only advantage left is to choose when the last duplicate element of her challenge e ⋆ has been inserted. It is obvious that the optimal strategy for A is to send a stream e ⋆ , e 2 , . . . , e w in the phase 1, before activating phase 2 on e ⋆ , with e i being all unique elements, different than e ⋆ . Of course, A can switch to phase 2 as soon as she detects that she will be victorious.

In this context, A wins the game if and only if e ⋆ is evicted by one of the w -1 next elements. An element evicts e ⋆ with probability 1 N S-k S 1 k , so A wins the game with probability 1 -( 1 -S-k N Sk ) w-1 , hence the result.

Theorem 3.9.3. Assuming the existence of one-way functions, a QHT is

( k S (1- 1 -1 kN w
, n)-false positive resistant for any n < w.

Proof. Similarly to the false negative proof, assuming the existence of one-way functions, the adversary has no better strategy than randomly trying new elements. The probability that a random unseen element (over the sliding window) triggers a false positive is FP w m , which is bounded above by k S 1 -1 -1 kN w .

Conclusion

This chapter introduces a new duplicate detection filter, QHT, and its variant QQHTD. QHTs achieve a better utilization of the available space, and as such are more efficient than existing filters. Especially, QHT is always performing better than the filter it is inspired from, SQF. Moreover, QQHTD have more efficiency for detecting duplicates in a real dataset. These results apply equally when we are considering duplicates in a sliding window or in general. We showed that, for an infinite stream with an infinite number of unseen elements, the number of rows is less important than the fingerprint space, and the number of cells per row. Moreover, we proved that all filters, having reached saturation, are not more efficient than random filters, and as such, a benchmarking of stream filters should only focus on the pre-saturation state, with small streams. We also gave a lower bound on the optimal error rate, thus allowing one to determine how close a structure is to optimality.

Introduction

Throughout this chapter, we are interested in the wDDP, i.e., the problem of duplicate detection over a sliding window w (see Definition 2.1.5).

Note that for w = ∞, the problem becomes finding whether an element is a duplicate amongst all previous stream elements. For simplicity in the notation, when we refer to ∞DDP we instead write DDP.

Instances of the wDDP abound in computer science, with applications to file system indexation, database queries, network load balancing, network management [START_REF] Demaine | Frequency Estimation of Internet Packet Streams with Limited Space[END_REF], in credit card fraud detection [START_REF] Carcillo | SCARFF: a Scalable Framework for Streaming Credit Card Fraud Detection with Spark[END_REF], phone calls data mining [CFP+00], etc. A discussion about algorithms on large data streams can be found in [START_REF] Golab | Issues in Data Stream Management[END_REF].

Perfect detection is however not always reachable and it might be more practical to work on a further relaxation of the problem, allowing for errors. As such, the problem then becomes to detect duplicates, with a minimal amount of errors. Given that there are two types of error, a compromise between false positives and false negatives must be done.

-Contributions and Related Work

Approximate duplicate detection has many real-life use cases, and can sometimes play a critical role, for instance in cryptographic schemes where all security and secrecy fall apart as soon as a random nonce is used twice, such as the ElGamal [START_REF] El | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF] or ECDSA signatures. Other uses include improvements over caches [START_REF] Kleanthous | CATCH: A Mechanism for Dynamically Detecting Cache-Content-Duplication and its Application to Instruction Caches[END_REF], duplicate clicks [START_REF] Metwally | Duplicate Detection in Click Streams[END_REF] and others. Please note that approximate detection is a different problem than detection of approximate duplicates [START_REF] Monge | An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records[END_REF], in which the goal is to find elements similar but not necessarily equal to the target.

As said before, when the window size in wDDP grows infinitely large, it becomes the following problem: find whether e ⋆ ∈ E n . Unfortunately any solution to this problem will necessary encounter a phenomenon called "saturation" on large enough data streams [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF], and when it happens the algorithm performs no better than at random. This is problematic on two grounds: it makes the comparison of several algorithms difficult (since they all asymptotically behave in that fashion), and the unavoidable saturation ruins any particular design's merits. As such, it is more interesting to focus on wDDP rather than DDP.

Contributions and Related Work

Contributions

In this chapter, we start in Section 4.3 from a naïve solution for the wDDP to then derive bounds for when it can be solved within M memory bits, up to a window size w max , in constant time. We then introduce, Section 4.3.2, a generalization of the naïve solution, and study its error rate. We show that this construction, which we call Short Hash Filter (SHF), can push the value w max further while operating in constant time -at the cost of some errors. We also provide a different tradeoff, the Compact Short Hash Filter (CSHF), which uses fewer memory but operates in linear time.

Unfortunately, for w > w max the performance of SHF degrades very rapidly. We thus briefly turn our attention in to existing data structures designed for the "non-windowed" setting in Section 4.4, and observe how these structures behave in the sliding window context. Based on our observations, we then introduce the "queuing construction" in Section 4.5, a black box transformation of non-windowed data structures into windowed ones, that improves their performance in the wDDP setting. We give formal error rates of our construction.

We also run an exhaustive benchmark in Section 4.6. In this benchmark, we compare the efficiency of our queueing construction compared to the naïve "nonwindowed" data structures. We show that depending on the context (especially the sliding window size), SHF, queueing filters and existing "non-windowed" filters each have their area of dominance.

Finally, we provide an analysis of our queueing construction's resistance to adversarial streams in Section 4.7.

Related Work

The notion of sliding window was, as far as we know, first introduced in [MAEA05]; but several variations exist that are incomparable to one another (e.g., [START_REF] Shtul | Age-Partitioned Bloom Filters[END_REF]). The wDDP formulation we rely on is notably used in [Yoo10; SZ08], which also introduce algorithms for solving the wDDP approximately.

The notion of using subfilters, as in the queuing construction, can be found in the A2 filter's design [START_REF] Yoon | Aging Bloom Filter with Two Active Buffers for Dynamic Sets[END_REF] and a variation thereof can be found in [START_REF] Shtul | Age-Partitioned Bloom Filters[END_REF] but in a different DDP formulation. The A2 is built from two Bloom filters, a construction which we generalize and analyse generically in this chapter. Similarly, the construction in [START_REF] Shtul | Age-Partitioned Bloom Filters[END_REF] only works with Bloom Filters.

A literature review collects the following DDF constructions: A2 filters [Yoo10], Stable Bloom Filters (SBF) [START_REF] Deng | Approximately detecting duplicates for streaming data using stable bloom filters[END_REF], Quotient Hash Tables (QHT) [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF], Streaming Quotient Filters (SQF) [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF], Block-decaying Bloom Filters (b_DBF) [START_REF] Shen | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows[END_REF], and a slight variation of Cuckoo Filters [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF] suggested by [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF]. The structure proposed in [START_REF] Metwally | Duplicate Detection in Click Streams[END_REF] is not designed for wDDP but a variant called 'landmark' sliding window, which consists of a zero-resetting of the memory at some user-defined epochs.

Remark. On the topic metrics used on benchmarking of such filters, there seems to be no consensus in the literature. We measure the error rate ER = FPR w + FNR w , as it allows a practical ranking of the solutions. An error rate of 0 means a perfect filter, while a filter answering randomly has an error rate of 1. A filter being always wrong has an error rate of 2. Note that the error rate metric is also equal to 1 -J, where J is Youden's J statistic [START_REF] William J Youden | Index for rating diagnostic tests[END_REF].

Approximate Solution and SHF

Optimal and Approximate Optimal wDDF

Before trying to find new solutions, it is important to first observe when the problem can be solved optimally by simple constructions. Theorem 4.3.1. For M ≥ w(log 2 (w) + 2 log 2 (|Γ|)), the wDDP can be solved exactly (with no errors) in constant time.

Proof. We explicitly construct a DDF that performs the detection. Storing all w elements in the sliding window takes w log 2 (|Γ|) memory, using a FIFO queue Q; however lookup has a worst-time complexity of O(w).

We therefore rely on an ancillary data structure for the sake of quickly answering lookup questions. Namely we use a dictionary D whose keys are elements from Γ and values are counters.

When an element e is inserted in the DDF, e is stored and D[e] is incremented (if the key e did not exist in D, it is created first, and D[e] is set to 1). In order to keep the number of stored elements to w, we discard the oldest element e last in Q.

-Approximate Solution and SHF

As we do so, we also decrement D[e last ], and if D[e last ] = 0 the key is deleted from D. The whole insertion procedure is therefore performed in constant time.

Lookup of an element e ⋆ is simply done by looking whether the key D[e ⋆ ] exists, which is done in constant time.

The queue size is w log 2 |Γ|, the dictionary size is w(log 2 |Γ| + log 2 w) (as the dictionary cannot have more than w keys at the same time, a dictionary key occupies log 2 |Γ| bits and a counter cannot go over w, thus being less than log 2 w bits long). Thus a requirement of w(log 2 (w) + 2 log 2 (|Γ|)) bits for this DDF to work.

Finally this filter does not make any mistake, as the dictionary D keeps an exact account of how many times each element is present in the sliding window.

However, this optimal filter requires that the size of Γ is known in advance. The dependence on log 2 |Γ| can be dropped, at the cost of allowing errors. Theorem 4.3.2. Let w ∈ N. Let M ≃ 2w log 2 w, then the wDDP can be solved with almost no error using M memory bits.

More precisely, it is possible to create a filter of M bits with an FN of 0, an FP of 1

-(1 -1 w 2 ) w ∼ 1 w ,

and a time complexity of O(w).

Using M ≃ 5w log 2 w bits of memory, a constant-time filter with the same error rate can be constructed.

Note that we only consider the false positive probability after the filter has inserted at least w elements, i.e., once the filter is full and has reached a stationary regime.

Proof. Here again we explicitly construct the filters that attain the theorem's bounds.

Let h be a hash function with codomain {0, 1} 2 log 2 w . The birthday theorem [START_REF] Wagner | A Generalized Birthday Problem[END_REF] states that for a hash function h over a bits, one must on average collect 2 a/2 input-output pairs before obtaining a collision. Therefore 2 (2 log 2 w)/2 = w hash values h(e i ) can be computed before having a 50% probability of a collision (here, a collision is when two distinct elements of the stream e i , e j with i ̸ = j, e i ̸ = e j have the same hash, i.e., h(e i ) = h(e j )). The 50% threshold we impose on h is arbitrary but nonetheless practical.

Let F be the following DDF: the filter's state consists in a queue of w hashes, and for each new element e, Detect(e) returns DUPLICATE if h(e) is present in the queue, UNSEEN otherwise. Insert(e) appends h(e) to the queue before popping the queue.

There is no false negative, and a false positive only happens if the new element to be inserted collides with at least one other element, which happens with probability

1 -(1 - 1 2 2 log 2 w ) w = 1 -(1 -1 w 2 ) w , hence an FN of 0 and a FP of 1 -(1 -1 w 2 ) w .
The queue stores w hashes, and as such requires w • 2 log 2 w bits of memory.

Note that this solution has a time complexity of O(w). Using an additional dictionary, as in the previous proof, but with keys of size 2 log 2 (w), we get a filter with an error rate of about 1 w and constant time for insertion and lookup, using w • 2 log 2 w + w • (2 log 2 (w) + log 2 (w)) = 5w log 2 w bits of memory.

Chapter 4 -Towards Optimality for the wDDP When log 2 |Γ| > 5 log 2 w this DDF outperforms the naïve strategy1 , both in terms of time and memory, at the cost of a minimal error. When log 2 |Γ| > 2 log 2 w, it outperforms the exact solution described sooner in terms of memory.

Short Hash Filter and Compact Short Hash Filter Algorithms

Short Hash Filter (SHF)

The approximate filter we described uses hashes of size 2 log 2 (w) for a given sliding window w. However, this hash size is arbitrary, and while the current hash size guarantees a very low error rate, it can be changed. More importantly, in some practical cases the maximal amount of available memory is fixed beforehand. Fixing the memory is also more practical for benchmarking data structures, as it gives the guarantee that all filters operate under the same conditions. This gives us the Short Hash Filter (SHF), described in Algorithm 5. The implementation relies on a double-ended queue or a ring buffer, which allows pushing at beginning of a queue and popping at the end in constant time. h ← hash function of codomain size

⌊ M 2w -1 2 log 2 w⌋ 3: Q ← ∅ ◃ Q is a queue of elements of size h 4:
D ← ∅ ◃ D is a dictionary h ⇒ counter (of max value w)

Q.Push_Front(h(e))

3:

D[h(e)]++

4:

if Q.length() > w then 5:

h ′ ← Q.Pop_back() 6: D[h ′ ]-- 7: if D[h ′ ] = 0 then 8:
Erase key D[h ′ ] return UNSEEN

Compact Short Hash Filter (CSHF)

Removing the dictionary from the SHF construction yields a more memory-efficient, but less time-efficient construction, which we dub "compact" short hash filter (CSHF). The CSHF performs in linear time in w, and is a simple queue, the only point is that 4.4 -Non-windowed DDFs in a wDDP Setting instead of storing e, the filter stores h(e), where h is a hash function of codomain size ⌊ M w ⌋.

Error probabilities

Let w > 0 be a window size and M > 0 the available memory. We write FN w SHF the probability of false negative of an SHF with these parameters. We similarly define FP w SHF , FN w CSHF , FP w CSHF .

Theorem 4.3.3. We have:

• FN w SHF = 0 and FP w SHF = 1 -1 - √ w2 -M/w w • FN w CSHF = 0 and FP w CSHF = 1 -1 -2 -M/w w
Proof. This is an immediate adaptation of the proof from Theorem 4.3.2. An SHF has fingerprints of size h = M 2w -1 2 log 2 w, while a CSHF has fingerprints of size h ′ = M w .

Remark: A CSHF of size M on a sliding window w has the same error rate than an SHF of sliding window w of size 2M + w log 2 w.

Saturation SHF has strictly increasing error probabilities, which reach a threshold of 1/2 for some maximum window size w max . Beyond this value, these filters saturate extremely quickly: in other words, most SHF will either have an error rate of 0 or 1. The same can be said about the CSHF. An illustration of this phenomenon can be seen in Figure 4.1, which shows the error rates for SHF with M = 10 5 , against a uniformly random stream of 18-bit elements (|Γ| = 2 18 ). The benchmark used a finite stream of length 10 6 .

The value w max can be obtained by solving (numerically) for FP wmax = 1/2 for a given M . Experiments (numerical resolution of FP max = 1/2, for about 200 different values of M , uniformly distributed on a log scale between 10 2 and 10 6 ) indicate an approximately linear relationship between M and w max : w CSHF max = 0.0627M + 443 (r 2 = 0.9981) and w SHF max = 0.0233M + 186 (r 2 = 0.9977).

Non-windowed DDFs in a wDDP Setting

Saturation Resistance of DDFs

We now evaluate the saturation rate for several DDFs, in the original DDP setting (without sliding window). Parameters are chosen to yield equivalent memory footprints and were taken from [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF], namely:

• QHT [GLPN19], 1 bucket per row, 3 bits per fingerprint;

• SQF [START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF], 1 bucket per row, r = 2 and r ′ = 1; • Cuckoo Filter [START_REF] Fan | Cuckoo Filter: Practically Better Than Bloom[END_REF], cells containing 1 element of 3 bits each;

10 2 10
• Stable Bloom Filter (SBF) [START_REF] Deng | Approximately detecting duplicates for streaming data using stable bloom filters[END_REF], 2 bits per cell, 2 hash functions, targeted FPR of 0.02.

The other filters from [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF] were not considered in this benchmark, as they were desgined to operate on a sliding window. These filters are run against a stream of uniformly sampled elements from an alphabet of 2 26 elements. This results in around 8% duplicates amongst the 150 000 000 elements in the longest stream used. Results are plotted in Figure 4.2. The optimality bound has been extracted from [START_REF] Géraud | Quotient Hash Tables: Efficiently Detecting Duplicates in Streaming Data[END_REF].

The best results are given by the following filters, in order: QHT, SQF, Cuckoo and SBF. We also observe that QHT and SQF have error rates relatively close to the lower bound, hence suggesting that these filters are close to optimality, especially since the lower bound is not tight.

Performance in wDDP

We now consider the performance of the filters just discussed in the windowed setting, for which they were not designed. In particular, it is not possible to adjust their parameters as a function of w.

Remarkably, some of these filters still outperform dedicated windowed filters for some window sizes at least, as shown in Figure 4.3. In this benchmark, we used the following filters:

• block decaying Bloom Filter2 (b_DBF) [START_REF] Shen | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows[END_REF], sliding window of size w 4.5 -Queuing Filters • A2 filter [START_REF] Yoon | Aging Bloom Filter with Two Active Buffers for Dynamic Sets[END_REF], changing subfilter every w/2 insertions

• QHT [GLPN19], 1 bucket per row, 3 bits per fingerprint Nevertheless, we will now discuss the queuing construction, which allow us to build windowed filters from the DDP filters.

Queuing Filters

We now describe the queuing construction, which produces a sliding window DDF from any DDF. We first give the description of the setup, before studying the theoretical error rates. A scheme describing our structure is detailed in Figure 4.4.

The Queuing Construction

Principle of operation. Let F be a DDF. Rather than allocating the whole memory to F, we will create L copies of F, each using a fraction of the available memory. Each of these subfilters has a limited timespan, and is allowed up to c insertions. The subfilters are organised in a queue.

When inserting a new element in the queuing filter, it is inserted in the topmost subfilter of the queue. After c insertions, a new empty filter is added to the queue, and the oldest subfilter is popped and erased.

As such, we can consider that each subfilter operates on a sub-sliding window of size c, which makes the overall construction a DDF operating over a sliding window of size w = cL. Queue update. After c insertions, the last filter of the queue is dropped, and a new (empty) filter is appended in front of the queue.

Pseudocode. We give a brief pseudocode for the queuing filter's functions Lookup and Insert, as well as a Setup function for initialisation, in Algorithm 6. We introduced for simplicity a constructor F.Setup that takes as input an integer M and outputs an initialized empty filter F of size at most M . Here subfilters is a FIFO that has a pop and push_first operations, which respectevely removes the last element in the queue or inserts a new item in first position.

Error Rate Analysis

The queuing filter's properties can be derived from the subfilters'. False positive and false negative rates are of particular interest. In this section we consider a queuing filter Q with L subfilters of type F and capacity c (which means that the last subfilter is dropped after c insertions).

Remark. By definition, after c insertions the last subfilter is dropped. Informationtheoretically, this means that all the information related to the elements inserted in that subfilter has been lost, and there are c such elements by design. Therefore, in the steady-state regime, the queuing filter holds information about at least c(L -1) elements (immediately after deleting the last subfilter) and at most cL elements (immediately before this deletion). Hence, if w < cL, the queuing filter can hold information about more than w elements.

F 0 F 1 F 2 ... F L-1 F L F L+1

False Positive Probability

Theorem 4.5.1. Let FP w Q,m be the false positive probabilityof Q after m > w insertions, over a sliding window of size w = cL, we have

FP w Q,m = 1 -(1 -FP F ,c ) L-1 (1 -FP F ,m mod c )
where FP F ,m is the false positive probability of a subfilter F after m insertions.

Proof. Let E = (e 1 , . . . , e m , . . . ) be a stream and e ⋆ / ∈ w E. Therefore, e ⋆ is a false positive if and only if at least one subquery F i .Lookup(e ⋆ ) returns DUPLICATE. Conversely, e ⋆ is not a false positive when all subqueries F i .Lookup(e ⋆ ) return UNSEEN, i.e., when e ⋆ is not a false positive for each subfilter.

Each subfilter has undergone c insertions, except for the first subfilter which has only undergone m mod c, we immediately get Theorem 4.5.1. c ← 0 Remark. In the case w < cL, as mentioned previously, there is a non-zero probability that e ⋆ is in the last subfilter's memory, despite not belonging to the sliding window.

Algorithm 6 Queuing Filter Setup, Lookup and Insert

Assuming a uniformly random input stream, and writing δ = cLw, the probability that e ⋆ has occurred in {e m-cL , . . . e m-w+1 } is 1 -1 -1 |Γ| δ . For large |Γ| (as is expected to be the case in most applications), this probability is about δ |Γ| ≪ 1. Hence, we can neglect the probability that e ⋆ is present in the filter, and we consider the result of Theorem 4.5.1 to be a very good approximation even when w < cL.

False Negative Probability

Theorem 4.5.2. Let FN w Q,m be the false negative probability of Q after m > w insertions on a sliding window of size w = cL, we have

FN w Q,m = u L-1 c u m mod c
where we have introduced the short-hand notation

u η = p η FN F ,η + (1 -p η ) (1 -FP F ,η )
where FN F ,η (resp. FP F ,η ) is the false negative probability (resp. false positive) of the subfilter F after η insertions, and

p η = 1-1-1 |Γ| η 1-1-1 |Γ| w ≈ η w .
Proof. Let E = (e 1 , . . . , e m , . . . ) be a stream, let w be a sliding window and let e ⋆ ∈ w E. Then e ⋆ is a false negative if and only if all subfilters F i answer F i .Detect(e ⋆ ) = UNSEEN. There can be two cases:

-Queuing Filters

• e ⋆ is present in F i 's sub-sliding window;

• e ⋆ is not present in F i 's sub-sliding window.

In the first case, F i .Detect(e ⋆ ) returns UNSEEN if and only if e ⋆ is a false negative for F i . This happens with probability FN F ,c by definition, except for F 0 , for which the probability is FN F ,m mod c .

In the second case, F i .Detect(e ⋆ ) returns UNSEEN if and only if e ⋆ is not a false positive for F i , which happens with probability 1 -FP F ,c , execpt for F 0 , for which the probability is 1 -FP F ,m mod c .

Finally, each event is weighted by the probability p c that e ⋆ is in F i 's sub-sliding window:

p c = Pr[e ⋆ is in F i sub-sliding window | e ⋆ ∈ w E] = Pr[e ⋆ is in F i sub-sliding window ∩ e ⋆ ∈ w E] Pr[e ⋆ ∈ w E] = Pr[e ⋆ is in F i sub-sliding window] Pr[e ⋆ ∈ w E] = 1 -Pr[e ⋆ is not in F i sub-sliding window ] 1 -Pr[e ⋆ / ∈ w E] p c = 1 -1 -1 |Γ| c 1 -1 -1 |Γ| w
This concludes the proof.

Remark. As previously, the effect of w < cL is negligible for all practical purposes and Theorem 4.5.2 is considered a good approximation in that regime.

FNR and FPR

From the above expressions we can derive relatively compact explicit formulas for the queuing filter's FPR and FNR when m = cn for n a positive integer.

Theorem 4.5.3. Let FPR w Q,m be the false positive rate of Q after m = cn > w insertions on a sliding window of size w = cL, we have

FPR w Q,cn = 1 - (1 -FP F ,c ) L-1 c c-1 ℓ=0 (1 -FP F ,ℓ ).
Proof. We start by recalling that FP w Q,m = FP w Q,m mod c , which we use two times in Chapter 4 -Towards Optimality for the wDDP the proof.

FPR w Q,cn = 1 cn cn k=1 FP w Q,k = 1 cn n-1 j=0 c ℓ=1 FP w Q,jc+ℓ = 1 c c ℓ=1 FP w Q,ℓ = 1 c c-1 ℓ=0 FP w Q,ℓ = 1 c c-1 ℓ=0 1 -(1 -FP F ,c ) L-1 (1 -FP F ,ℓ ) FPR w Q,cn = 1 - 1 c (1 -FP F ,c ) L-1 c-1 ℓ=0 (1 -FP F ,ℓ )
Theorem 4.5.4. Let FNR w Q,m be the false negative rate of Q after m = cn > w insertions on a sliding window of size w = cL, we have

FNR w Q,cn = u L-1 c c c-1 ℓ=0 u ℓ Proof. Similarly, let us first recall that FN w Q,m = FN w Q,m mod c . FNR w Q,cn = 1 cn cn k=1 FN w Q,k = 1 cn n-1 j=0 c ℓ=1 FN w Q,jc+ℓ = 1 c c ℓ=1 FN w Q,ℓ = 1 c c-1 ℓ=0 FN w Q,ℓ = 1 c c-1 ℓ=0 u L-1 c u ℓ FNR w Q,cn = u L-1 c c c-1 ℓ=0 u ℓ

-Queuing Filters

As for the probabilities, the expressions derived above for the FNR and FNR are valid to first order in (w -cL)/|Γ|, i.e., they are good approximations even when w ≈ cL.

Optimising Queuing Filters

Let us relax, temporarily, the a priori constraint that w = cL. The parameter L determines how many subfilters appear in the queuing construction, and it might be interesting to determine what its optimal value should be. Summing up the false positive and false negative rates, we have a total error rate ER w

Q,cn = 1 -αβ L-1 + α ′ β ′L-1 , where β = 1 -FP F ,c , β ′ = u c , α = 1 c c-1 ℓ=0 1 -FP F ,ℓ and α ′ = 1 c c-1 ℓ=0 u ℓ are
all parameters which depend on w, c and the choice of subfilter type F.

Because

u η = p η FN F ,η + (1 -p η ) (1 -FP F ,η
), differentiating with respect to L, knowing that w = Lc, and equating the derivative to 0, one can find the optimal value for L by solving for x the following formula, which has been obtained via Mathematica:

-αβ -1+x log(β) + (β + FN F ,c (-1 + x)) -2+x x -x -αβ + FN F ,c (-β(-2 + x) + FN F ,c (-1 + x)) + (α + FN F ,c (-1 + x)) × (β + FN F ,c (-1 + x)) (log (β + FN F ,c (-1 + x)) -log(x)) = 0
If numerically solving the equation for individual cases is feasible, it seems unlikely that a closed-form formula exists. Hence, it is maybe more interesting to find experimentally the optimal value, which we do a few pages below in Section 4.6.2.

Queuing Filters from Existing DDFs

Our queuing construction relies on a choice of subfilters. A first observation is that we may assume that all subfilters can be instances of a single DDF design (rather than a combination of different designs).

Indeed, a simple symmetry argument shows that a heterogenous selection of subfilters is always worse than a homogeneous one: the crux is that all subfilters play the same role in turn. Therefore we lose nothing by replacing atomically one subfilter by a more efficient one. Applying this to each subfilter we end up with a homogenous selection.

It remains to decide which subfilter construction to choose. The results of an experimental comparison of different DDFs (details about the benchmark are given in Section 4.

Experiments and Benchmarks

This section provides details and additional information on the benchmarking experiments run to validate the above analysis. All the related code is accessible online on GitHub: https://github.com/mariuslp/qht_v2.

Benchmarking Queuing Filters

Applying the queuing construction to DDFs from the literature, we get new filters which are compared in the wDDP setting. In Section 4.5.5 we suggested the heuristic that the DDFs with the least saturation rate in the DDP would yield the best (error-wise) queuing filter for the wDDP. This heuristic is supported by results, summarized in Figure 4.5. For this benchmark we used the following parameters: uniform stream from an alphabet of size |Γ| = 2 18 , memory size M = 100, 000 bits, sliding window of size w = 10, 000, and we measure the error rate (sum of FNR w and FPR w ).

A surprising observation is that when Lw approaches the size of the stream, there is a drop in the error. This is an artifact due to the finite size of our simulations; the stream should be considered infinite, and this drop disappears as the simulation is run for longer (see Section 4.6.4). This effect also alters the error rates for smaller window sizes, albeit much less, and we expect that filter designers care primarily about the small window regime. Nevertheless a complete understanding of this effect would be of theoretical interest, and we leave the study of this phenomenon for future work.

The Number of Subfilters

The number of subfilters L is an important parameter in the queuing construction, as it affects the filter's error rate in a nontrivial way. An illustration of this dependence is shown in Figure 4.6 which plots the error rate of a queueing QHT on an uniform stream of alphabet size Γ = 2 16 , with 10 5 elements in the stream, on various sliding window sizes. We observe that the optimal value for L does indeed depend on the desired sliding window. However, other experiments on alphabets of other sizes yield very similar results, hence validating the observation made in Section 4.5.4 that the optimal number of subfilters does not depends on the alphabet, at least in first approximation.

Filters vs Queued Filters

Using the same stream as previously, we can build queued filters (with an optimal value L for each considered sliding window) and compare their performances to that of non-modified filters. Results on the QHT and SQF are shown in We observe that queueing filters do not necessarily behave better than their 'vanilla' counterparts, especially on large sliding windows. This can be interpreted by the fact that the DDPs were optimised for infinite sliding windows, and as such operate better than their queueing equivalent on large sliding windows.

Effects of the Simulation's Finiteness

Theoretical results about the queuing construction apply in principle to an infinite stream. However, simulations are necessarily finite, and for very large windows (that are approximately the same size as the whole stream) this causes interesting artefacts in the error rates.

Note that these effects have very little impact on practical implementations of queuing filters, since almost all use cases assume a window size much smaller than the stream (or, equivalently, a very large stream). Nevertheless we illustrate the effect of the finite simulation and the parameters affecting it, if only to motivate a further analytical study of this phenomenon.

Figure 4.9 (page 78) measures the error rate as a function of w, for different stream sizes N . The split between FPR and FNR is made in Figure 4.10, page 79. A visible decrease in error rate can be found around w ≈ N . When looking in more details (see Figure 4.10),the peak of false positive, and more importantly its decrease to the asymptotic error rate of the QHT (here, 1 7 ≈ 14%) seems to be related with the size of the alphabet, here 2 16 , which was confirmed by further experiments. However, these experiments showed that other parameters, such as the filter memory size, also played a role, and we did not achieve to establish a clear relation between the alphabet size, the memory size and the false positive rate. Such a relation would be an interesting addition to this work, and would help understand better how queueing filter error rates work. For high values of w, the plateau that we can see comes from the fact that, for w > L • N , only one subfilter is used for storing the whole stream. Hence, all values w > L • N are identical, and equal to the error rate of an underlying filter, of size M/L, on a stream of size N .

As can be seen on this simulation, there is only disagreement around w ≈ N/L, and increasing N results in a later and smaller peak.

It is also possible to run simulations for different alphabet sizes Γ, which shows that the peak's position increases with |Γ|, although the relationship is not obvious to quantify.

Adversarial Resistance of Queueing Filters

As DDFs have numerous security applications, we now discuss the queuing construction from an adversarial standpoint. We consider an adversarial game in which the attacker wants to trigger false positives or false negatives over the sliding window. One motivation for doing so is causing cache saturation or denial of service by forcing cache misses, triggering false alarms or crafting fradulent transactions without triggering fraud detection systems.

In this chapter, we have introduced two new constructions, the SHF and the queueing construction. However, the security of SHF is trivial to analyse. By construction, false negative attacks are impossible, and one can easily see that, assuming the existence of collision-resistance hash functions, false positive attacks are impossible as well. For this reason, in this section we only focus on the security of the queueing construction. Theorem 4.7.1 (Bound on false positive resistance). Let Q be a filter of L subfilters F i , with c insertions maximum per subfilter, let w be a sliding window.

If F is (p, c)-resistant to adversarial false positive attacks and cL ≤ w, then Q is

(1 -(1 -p) L ,

w)-resistant to adversarial false positive attacks on a sliding window of size w.

If cL > w, the adversary has a success probability of at least 1 -(1p) L .

Proof. If cL ≤ w, then information-theoretically the subfilters only have information on elements in the sliding window. The false positive probability for

Q is 1 -(1 - FP F ,c
) L , which is strictly increasing with FP F ,c . Hence, the optimal solution is reached by to maximising the false positive probability in each subfilter F i . By hypothesis the latter is bounded above by p after c insertions. On the other hand, if cL > w then the oldest filter holds information about elements that are not in the sliding window anymore. Hence, a strategy for the attacker trying to trigger a false positive on e ⋆ could be to make it so these oldest elements are all equal to e ⋆ . Let E be the optimal adversarial stream for triggering a false positive on the sliding window w with the element e ⋆ , when cL ≤ w. The adversary A can create a new stream E ′ = e ⋆ |e ⋆ | . . . |E where e ⋆ is prepended cLw times to E.

After w insertions, the last subfilter will answer DUPLICATE with probability at least p, hence giving a lower bound on A ′ s success probability. If, for some reason, the last subfilter answers DUPLICATE with probability less than p, then the same reasoning as for when cL ≤ w still applies, hence we get the corresponding lower bound (which is, in this case, an equality). Theorem 4.7.2 (Bounds on false negative resistance). Let Q be a filter of L subfilters of kind F, with c insertions maximum per subfilter, and let w be a sliding window.

If F is (p, c)-resistant to adversarial false negative attacks, then A can win the adversarial game on the sliding window w with probability at least p L . Furthermore, for q the lower bound on the false positive probability FP F ,c for a given stream, if w ≤ (L -1)c then Q is (min(1q, p) L-1 p, w)-resistant to false negative attacks on the sliding window w. On the other hand if w > (L -1)c then Q is (max(1q, p) L , w)-resistant to false negative attacks on the sliding window w.

Proof. Let us first prove that a PPT adversary A can win the game with probability at least p L . For this, let us consider the adversarial game against the subfilter F: after c insertions from an aversarial stream E c , A choses a duplicate e ⋆ which will be a false negative with proability p. Hence, if A crafts, for the filter Q, the following Chapter 4 -Towards Optimality for the wDDP

adversarial stream E ′ = E c | E c | • • • | E c consisting of L concatenations of the stream E c
, then e ⋆ is a false negative for Q if and only if it is a false negative for all subfilters F i , hence a success probability for A of p L . Now, Let us prove the case where w ≤ (L -1)c. In this case, at any time, Q remembers all elements from inside the sliding window. As we have seen in the previous example, the success probability of A is strictly increasing with the probability of each subfilter to answer UNSEEN. The probability of a subfilter to answer UNSEEN is:

• FN ′ F ,c if e ⋆ is
in the subfilter's sub-sliding window;

• 1 -FP ′ F ,c if e ⋆ is not in the subfilter's sub-sliding window where FN ′ and FP ′ are the probabilities of false negative and positives on the adversarial stream (which may be different from a random uniform stream). However, since e ⋆ is a duplicate, it is in at least one subfilter's sub-sliding window. As such, the optimal strategy for A is to maximise the probability of all subfilters to answer UNSEEN. Now, FN ′ F ,c is bounded above by p and 1-FP ′ F ,c is bounded above by 1q, so the best strategy is where as many filters as possible answer UNSEEN with probability max(p, 1q), knowing that at least one filter must contain e ⋆ and as such its probability for returning UNSEEN is at most p, hence the result. Now, let us consider the case when w > (L -1)c. We have already introduce the element e ⋆ in the last w elements, and we want to insert it again. It is possible, for the adversary, to create the following stream E = (e 1 , e 2 , . . . , e c-1 , e ⋆ , e c+1 , . . . , e Lc , e Lc+1 ), and to insert e ⋆ afterwards.

When e Lc+1 is inserted, all elements (e 1 , . . . , e c-1 , e ⋆ ) are dropped as the oldest subfilter is popped. Hence, in this context e ⋆ is not in any subfilter anymore, so by adapting the previous analysis, A can get a false negative with probability at most max(1q, p) L .

Conclusion

In this work, we have given bounds on the optimal solutions for the sliding window duplicate detection problem, and given solutions when optimality is reachable. When memory is too small, or conversely when the sliding window is too big, we first suggest the SHF, which experimentally is near-optimal in cases where optimality can be reached, and behaves well when the sliding window is slightly bigger than w max . If the sliding window is significantly bigger than w max , we introduce the queueing construction, which takes an existing ∞DDF and adapts it for the sliding window context. However, For even larger sliding windows, the queueing filter is actually less performant than the 'vanilla' setting, as the ∞DDF were optimised for large (or rather infinite) sliding windows.

Thus, we have listed different strategies for solving the wDDP. However, there is yet no guarantee of optimality, which we leave for future work.

impossible. However, we contend that there may be special conditions under which two blockchains can be interoperable. This leads us to prove the equivalence between two interoperable public blockchains and a ledger emulating both blockchains on two separate registries.

Related Work. The concept of sidechains (a sidechain is a blockchain attached to another blockchain, with exchanges possible between the two blockchains) has been explored in [START_REF] Back | Enabling blockchain innovations with pegged sidechains[END_REF]. The authors describe a two-way peg in which a sidechain is fed with an SPV proof, a short proof of the transaction allowing for lightweight clients. The sidechain plays the role of a lightweight client, and can thus allow subsequent operations following the SPV proof. However, this pegging system requires a contest period, during which it is assumed that people will verify that the SPV proof does not come from a fork. Hence, additional trust is required in this model. In a paper from 2016 [START_REF] Vitalik Buterin | Chain Interoperability[END_REF], Buterin lists ways of reaching interoperability, and focuses on trusted inter-chains exchanges, where one sends money on blockchain A and receives some in blockchain B.

Similarly, the Interledger protocol [START_REF] Thomas | A Protocol for Interledger Payments[END_REF] (ILP) allows one to automatize money transfers while leveraging the risk of fraud, thanks to micro-transactions. Yet, ILP is more about escrow synchronization than interoperability as we define it later on. In an ILP transaction from blockchain A to blockchain B, one must find an escrow having enough money on B (or several escrows having in total enough money), so the transfer can occur. More generally, we consider that interoperability can for instance allow money to 'disappear' from A and to 'reappear' on B, without the need for trusted escrows.

Interoperability has been notably implemented in the blockchain network Kadena [START_REF] Martino | Chainweb Whitepaper[END_REF], in which transfers from one blockchain of the network to another is possible. The money is destroyed on one side and generated on the other. Kadena also uses smart contracts for securing escrow transfer. However, there is no indication that Kadena can operate with chains outside of their specific network. So in our terminology, we say that Kadena is a "N-in-1 blockchain", which is to say one blockchain, with several ledgers.

To the best of our knowledge, no theoretical work on interoperability has been done to date. Our work, rather than giving a practical implementation of an interoperable blockchain, gives a theoretical background to the topic, and explores the conceptual meaning of having interoperable blockchains.

Outline. In the next section, we formally define a blockchain and interoperability. In Section 5.3, we prove that it is impossible by design to have interoperability between blockchains. In Section 5.4, we show that interoperability is possible with a weaker definition of the blockchain. Before concluding, in Section 5.5, we prove that interoperability is equivalent to having a blockchain with two ledgers.

Preliminaries

Sets and tuples are noted in calligraphic font: A, algorithms in serif: Mine. When a deterministic algorithm, say Algorithm, returns some value x from some input i, we use the notation x ← Algorithm(i). If Algorithm is randomised, we use the notation x $ ← -Algorithm(i). A list of elements e 1 , . . . , e n (in this order) is represented by [e 1 , . . . , e n ]. We denote concatenation of two lists a and b with a∥b. The set of elements belonging to A but not to B is noted A\B (this set is also called the difference of A and B.)

Blockchain Definition

Various definitions of blockchain have already been given [START_REF] Garay | The Bitcoin Backbone Protocol: Analysis and Applications[END_REF][START_REF] Fernández Anta | Formalizing and Implementing Distributed Ledger Objects[END_REF]. In this work, we rather give a formalization of blockchains, which we believe is easier to use for proving theoretical results such as the one in this chapter.

Intuitively, a blockchain is a chain of transactions. More precisely, each element of the chain (each block) contains several transactions (or one or none), as well a proof needed for consensus to take place. For instance in Bitcoin [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] or similar Proof of Work blockchains, the proof is a nonce (a random number such that the hash of the block is below a threshold value); in a Proof-of-Stake such as the Casper version for Ethereum [START_REF] Vitalik Buterin | Ethereum: A next-generation smart contract and decentralized application platform[END_REF] the proof consists of the successive bets on what the next block will be; in a Proof-of-Elapsed-Time as designed by Intel [START_REF]Hyperledger Sawtooth[END_REF], the proof is instead a certificate obtained from the SGX (a trusted enclave). Note that it exists blockchains not requiring proofs (for instance, one can argue that PBFT consensus does not require proof), in which case we consider the proof is empty. Definition 5.2.1 (Blockchain). Let T be a set of transactions and P be a set of proofs. A blockchain is a tuple of elements B = (L, W, Emit, Mine), where:

• A ledger L is a list of transactions with their proofs defined by: L = [([t 1,1 , t • W is such that W ⊂ T , W is called the pool of waiting transactions.

• Emit is a deterministic algorithm taking one transaction t ∈ T and W as input, and returning an updated pool Emit(t, W) = W ∪ t.

• Mine is an algorithm taking L, W and returning a new ledger L ′ , a new pool W ′ , where for any W ⊂ T , and for

(L ′ , W ′ ) $ ← -Mine(L, W), we have that L ′ is of the form L∥[(transacs, p)],
where transacs is a list containing all elements from W\W ′ , and p ∈ P a proof. Furthermore, after a call to Emit or Mine, the ledger L and the waiting pool W of B are updated with the values returned by said algorithms. In other words, Mine and Emit are not pure functions [START_REF] Milewski | Pure Functions, Laziness, I/O, and Monads[END_REF], as they have side effects on the blockchain.

At this point, transactions are appended (or not) to the blockchain after a call to Mine. We hereby give a formal definition of what a valid transaction is.

-Preliminaries

Definition 5.2.2 (Valid Transaction). Let B = (L, W, Emit, Mine) be a blockchain, and let t be a transaction (t ∈ W), t is a valid transaction for B (currently in state L) if and only if there exists a block in the ledger returned by Mine containing t.

As we can see, the validity of a transaction depends on the state of the ledger; if a transaction is valid at one point, it may not be valid forever, and reciprocally. For instance, a transaction from user U to user V is valid only as long as U has enough funds. Yet, after the emission and the insertion of the transaction in the blockchain, U may issue other transactions, emptying their wallet. This is the classical issue of double spending.

The same is true for smart contracts: here, they are seen as a special subset of transactions, and they affect the state of the ledger. Because Mine has access to the whole ledger, it can take into account the smart contract's side effects.

Note that Mine is a randomized algorithm, and as such, there is no guarantee that all users will agree on the same ledger. Because blockchain is a decentralised ledger, state synchronisation must be ensured. For this, we introduce a synchronisation algorithm, called Consensus.

Definition 5.2.3 (Decentralised Blockchain).

A decentralised blockchain is a tuple B ′ = (L, W, Emit, Mine, Consensus) where:

• B = (L, W, Emit, Mine) is a blockchain,
• Consensus is a deterministic algorithm, taking as input B, a set S of tuples (L i , W i ) such that ∀(L i , W i ) ∈ S, we have that (L i , W i , Emit, Mine) is a blockchain. Furthermore, for (L * , W * ) ← Consensus(B, S), then (L * , W * ) ∈ S ∪ (L, W). In other words, from a list of potential new blocks, Consensus chooses (or accepts) one of them, or rejects them all (and returns (L, W)).

• After a call to Consensus, B ′ 's ledger and waiting pool components are replaced with the values returned by said algorithms.

The idea of Consensus is that when a peer updates their local version of the blockchain, they first receive possibly more than one new version (i.e., new blocks) from peers. However only one of these new blocks will be accepted, and all the network must agree on this block. Definition 5.2.4 (Secure Blockchain). We say that a decentralised blockchain (L, W, Emit, Mine, Consensus) is secure if it is computationally hard for a user to craft a new ledger L ′ and a new transaction pool W ′ such that for all S such that (L ′ , W ′ ) ∈ S, we have both that Consensus(B, S) = (L ′ , W ′ ) and L is not a prefix of L ′ . This definition makes a blockchain immune against history rewriting (and double spending), as it is computationally hard to rewrite old blocks.

Interoperability Definition

The concept of interoperability is to enable two blockchains to work together. A classic blockchain A accepts transactions because given the current state of A's ledger, the transaction does not violate A's rules. Similarly, we say that a blockchain A that is interoperable with blockchain B accepts transactions because, given the current state of A and B's ledgers, the transaction does not violate A's rules. Furthermore, if the rules for said transaction only imply conditions on A's ledger, then the transaction does not require B to be valid, and as such does not make use of the interoperability. So an interoperable transaction on A must be dependent on B's ledger: if B's ledger is equal to some values, then the transaction is valid; otherwise it is invalid.

We now give a formalization of this definition.

Definition 5.2.5 (Blockchain Interoperability)

.

Let A = (L A , W A , Emit A , Mine A , Consensus A ) and B = (L B , W B , Emit B , Mine B , Consensus B ) be two decentralised block- chains. Let Ω A (resp. Ω B )

be the set of all possible values for A's ledger L A (resp. L B ).

A is interoperable with B if there exists:

• a transaction t ∈ T , • a non-empty subset ω A ⊂ Ω A ,
• a non-empty proper subset ω B Ω B such that there exists a block containing t that is accepted by

Consensus A if L A ×L B ∈ ω A × ω B ,

and rejected otherwise.

A and B are interoperable if they are both interoperable with each other.

General Impossibility of Interoperability

Our first result is to show that it is impossible to have interoperability between two blockchains in general. We build blockchain B so that it is interoperable with blockchain A in the following sense: a user can 'create' money on B if and only if at least the same amount of money has been consumed on A, by sending it to a 'bin' account.

We first note that accounts owned by nobody exist. In our scheme, in most cryptosystems the public key 0 (consisting of only zeroes) is not linked to any private key. Thus, while the account 0 A exists and money can be transferred on this account, it cannot be claimed by anyone.

Let us construct B in order to fulfil the previous requirements. First, let us define the interoperability transactions t * (m B , pk B ), which sends some amount of money m B from 0 B to the account pk B on B. t * (m B , pk B ) is only valid if there is at least one transaction on L A sending m to the account 0 A , with m > m B . 1Then, let us construct Mine B : a transaction t is valid for Mine B (L B , L A , W B , W A ) if and only if t is valid for Mine A (L A , ∅, W A , ∅), or if both statements are true:

• t is an interoperability transaction transferring some amount of money m from 0 B to an account on B,

• L A contains a transaction sending at least m on the zero-address 0 A .

Similarly, Consensus B (B, A, •) is conceived to accept new ledgers that would have been accepted by Consensus A (B, ∅, •), as well as ledgers where the new blocks are constituted solely of transactions that are accepted by Consensus A (B, ∅, •) and valid interoperability transactions (valid in the meaning that at the time of their incorporation in the ledger, the sender has enough funds to emit the transaction).

With this construction, we immediately get that B is interoperable with A: a user can transfer assets from A to B, which is shown by the fact that some transactions (here denoted t * ) are only valid on B if the sender has enough funds on A.

Equivalence of Interoperable Blockchains with a Single Blockchain

Even though interoperable blockchains can be tweaked into existence, we argue that they are conceptually equivalent to a single blockchain. More precisely, we argue that they are equivalent to one blockchain, composed of two ledgers. Such a blockchain can be easily implemented: if the first bit of the transaction is 0, then apply the transaction to the first ledger, and if 1 to the second. We say that two blockchains are equivalent if any valid transaction on one blockchain corresponds to one valid transaction on the other blockchain. This definition implies that two equivalent blockchains will have very similar evolutions of their ledgers. As Mine is not deterministic, we cannot ensure that the two ledgers will be identical, but the definition we give is enough for practical uses.

A ) = L B ⇒ ∀t A ∈ T A , t A is a valid transaction for A ⇔ φ(t A ) is a valid transaction for B).
Note that φ(L A ) is the generalization of φ to ledgers: if

L A = [[t 1,1 , t 1,2 , . . . ] , . . . , [t n,1 , t n,2 , . . . ]], then φ(L A ) = [[φ(t 1,1 ), φ(t 1,2 ), . . . ], . . . , [φ(t n,1 ), φ(t n,2 ), . . . ]],
in the case of a ledger without proofs. If the ledger has proofs (see Definition 5.2.1), φ would need to work on a projection of the ledger: a projection in which every poof is removed. This subtlety has been removed from the definition for the sake of simplicity.

For instance, let us assume that two blockchains are equivalent, and two smart contracts being the reciprocal image of each other. This means that whatever transaction triggers one smart contract, the effects on the state of the blockchain will be equivalent to the effects on the state of the image blockchain: in both cases, the acceptable elements after the transaction are the same (up to a bijection). This definition does not guarantee that the smart contract will behave identically: for instance, one could image a smart contract updating a useless write-only variable, which by definition does not affect the set of future acceptable transactions as it is write-only. However, it ensures that the behaviour of the blockchain is strictly the same in both cases. Let T A (resp. T B ) be the set of transactions for A (resp. B). Note that T A contains interoperability transactions. Let C be the tuple

C = (L C , W C , Emit C , Mine C , Consensus C ).
We define the set of transactions for

C, T C = (T A × ∅) ∪ (∅ × T B ). Let c A (resp. c B ) be the canonical projector of T C on T A (resp. T B ). For (L A ∥[(transacs A , p A )], W ′ A ) = Mine A (L A , L B , c A (W C )) and (L B ∥[(transacs B , p B )], W ′ B ) = Mine B (L B , c B (W C )), we define: Mine C (L C , W C ) = (L C ∥ [(transacs A × ∅∥∅ × transacs B , p A × p B ), (W ′ A × ∅) ∪ (∅ × W ′ B )]) Simply put,
. If Consensus A (A, B, c A (S C )) = (L * A , W * A ) and Consensus B (B, c B (S B )) = (L * B , W * B ), then we define Consensus C = (L A × ∅∥∅ × L B , W A × ∅ ∪ ∅ × W B ).
By construction, we see that C is a decentralised blockchain. Furthermore, by construction each transaction accepted by Mine C is either accepted by Mine A or Chapter 5 -About Blockchain Interoperability Mine B and, conversely, each transaction accepted by Mine A or Mine B is accepted by Mine C , hence the equivalence of the blockchains.

In practice, Theorem 5.5.1 means that creating two interoperable blockchains is equivalent to creating one blockchain, with a ledger divided into two separate registries: a '2-in-1' blockchain. So while creating interoperable blockchains (with a lax definition of a blockchain) is possible, we argue that the conceptual interest of doing so is limited. However, it may be interesting to create an interoperable blockchain on top of an already existing blockchain. Doing so allows both blockchains to fully operate, without the older blockchain being affected by anything. Nonetheless the obvious restriction is that only one of the two blockchains will be interoperable with the other, with all the limits implied by this fact.

Conclusion

In this chapter, we explored the possibility of making two blockchains interoperable, and focused on interoperability on the consensus layer. We showed that, under classical definitions, it is impossible to make a blockchain interact with anything other than itself. If we relax the definition, we do get the possibility of interoperable blockchains, but doing so is equivalent to creating a '2-in-1' blockchain, i.e., a blockchain with two ledgers. However, note that this result does not say interoperability is impossible, as we noted that solutions already exist for this problem. More importantly, our results show that 'one-way' interoperability can be achieved without losing information, which can be useful when one develops a new blockchain that can read on top of another, independent, blockchain. Moreover, in the case of full interoperability between two blockchains, the result could be interpreted as limited, as it shows that the two blockchains can be simulated by one blockchain with two ledgers. However, another way of exploring this result is to realize that a two-ledger blockchains can be split into two blockchains without loss of information. This can be useful in contexts where one ledger is highly resource consuming, while the other is lighter and is run by more actors.

It should also be noted that interoperability can be achieved at other levels than consensus, for instance using game theory on smart contracts and offchain exchanges, or relying on data oracles. Formalizing interoperability on these layers is left for future work.

Finally, we believe that the formalization we used in this chapter can be reused for studying other properties of blockchain, thus leading to formal proofs of other properties of blockchain.

Abstract

The stochastic multi-armed bandit is a classical decision making model, where an agent repeatedly chooses an action (pull a bandit arm) and the environment responds with a stochastic outcome (reward) coming from an unknown distribution associated with the chosen action. A popular objective for the agent is that of identifying the arm with the maximum expected reward, also known as the bestarm identification problem. We address the inherent privacy concerns that occur in a best-arm identification problem when outsourcing the data and computations to a honest-but-curious cloud.

Our main contribution is a distributed protocol that computes the best arm while guaranteeing that (i) no cloud node can learn at the same time information about the rewards and about the arms ranking, and (ii) by analyzing the messages communicated between the different cloud nodes, no information can be learned about the rewards or about the ranking. In other words, the two properties ensure that the protocol has no security single point of failure. We rely on the partially homomorphic property of the well-known Paillier's cryptosystem as a building block in our protocol. We prove the correctness of our protocol and we present proof-ofconcept experiments suggesting its practical feasibility.

This work is joint with Radu Ciucanu, Pascal Lafourcade and Marta Soare. It has been presented at the 15th International Conference on Information Security Practice and Experience (ISPEC 2019) and published as [START_REF] Ciucanu | Secure Best Arm Identification in Multi-armed Bandits[END_REF].

Introduction

In a stochastic multi-armed bandit model, a learning agent sequentially needs to decide which arm (option/action) to pull from K arms with unknown associated values available in the learning environment. After each pull, the environment responds with a feedback, in the form of a stochastic reward from an unknown distribution associated with the arm chosen by the agent. This is a dynamic research topic with a wide range of applications, including clinical trials for deciding on the best treatment to give to a patient [START_REF] William R Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF], on-line advertisements and recommender systems [START_REF] Li | A Contextual-Bandit Approach to Personalized News Article Recommendation[END_REF], or game playing [START_REF] Kocsis | Bandit Based Monte-Carlo Planning[END_REF][START_REF] Coquelin | Bandit Algorithms for Tree Search[END_REF][START_REF] Munos | From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning[END_REF].

In this chapter, we focus on a popular objective in multi-armed bandits, that of best arm identification: given a set of K arms and a limited budget of N pulls, the goal of the agent is to design a budget-allocation strategy that maximizes the probability of identifying the arm with the maximum expected reward. This problem has been extensively studied in the machine learning community [ABM10; CLK+14; EDMM06; GGL12; KCG16; SLM14], but to the best of our knowledge, there is no previous work that considers this problem from a privacy-preserving viewpoint. Next, we illustrate the problem via a motivating example.

Use Case Example

A classical real-world application of the best-arm identification problem is as follows. Before launching a new product on the market, companies can create several versions of the product that are put into a testing phase. By product, we refer here to any type of object/service that might be offered by a company and that may contain (or be obtained as a result of analyzing) private data. Each version of the product has distinguishing characteristics and the company surveys potential customers about the version they prefer. The company's objective is that once the testing phase is over, it can put on the market the version that is likely to yield the best sales. The goal of the best-arm identification problem is to define algorithms that maximize the probability of identifying the best arm (here, the best version among the K alternative versions), given a limited budget of N observations (here, customer surveys). Therefore, best-arm identification algorithms are a good fit for the product testing phase. Now, imagine the scenario where a company collected over the years a large quantity of customer surveys that it no longer needs for its purposes. This data may actually be useful for other smaller companies that cannot afford doing their own customer surveys, but nonetheless want to simulate the test of different versions of their product. This brings us to the system architecture depicted in Figure 6.1. The data owner is the company that owns a large quantity of customer surveys that it wants to monetize. The user is the small company that wants to simulate the testing of different versions of its product, without conducting its own customer survey. It may actually be cheaper to pay a limited budget to reuse pieces of existing data, rather than doing a new survey with real customers.

The interaction between the data owner and the user is done using some public cloud, where initially the data owner outsources its data, then the users interact directly with the cloud. More precisely, each user allocates some budget to the cloud and reuses the available surveys for deciding which version of its own product should be put on the market. The budget would refer here to the number of survey answers the user wants the cloud to use before outputting the best option. As a simplified example, assume that the available data consists of user preferences about the characteristics of security devices they would buy for protecting their homes. There are 1M surveys available and consulting a survey costs 0.1$. If a small company wants to know which type of device people from their market are more likely to buy, the precision of the answer it receives from the cloud depends on the paid budget. If it pays 100$, it is more likely to get a clearer image about the type of device that is the most likely to be purchased, than if it pays 5$. But in both cases the obtained information is not 100% sure because only a sample of the available data is consulted.

The aforementioned use case can be easily reformulated to other real-world sce-Chapter 6 -Secure Best Arm Identification in Multi-Armed Bandits narios, such as health or medical data, cosmetics (e.g., trials for finding the best anti-wrinkle cream), data concerning political preferences, education and employment records, to name a few.

As already mentioned, we consider a scenario where the multi-armed bandits (i.e., the data) as well as the best arm identification algorithm (i.e., the computation) are outsourced to some public cloud. We assume that the cloud is honest-but-curious: it executes tasks dutifully, and try to gain information on the ranking of the arms and their associated values from the data they receive. We address the privacy concerns that occur when outsourcing the data and computations.

Indeed, the externalized data can be communicated over an untrustworthy network and processed on some untrustworthy machines, where malicious public cloud users may learn private data that belongs only to the data owner. This is why we require the data owner to encrypt all information about the arms before outsourcing the data to the public cloud.

Moreover, each cloud user observes a result of the best arm identification algorithm that is proportional to the budget that the user pays. It should be impossible for a malicious cloud user to compose observations of several runs of the best arm identification algorithm in order to learn the best arm with a higher confidence, and then sell this information to some other user.

Summary of Contributions and Chapter Organization

In Section 2.2, we give background information on the problem of best-arm identification in multi-armed bandits.

In Section 6.2, we first present the considered security model, then the needed security tools, and finally the distributed security protocol, that is the main contribution of the chapter. We rely on the partial homomorphic property of Paillier's cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] as a building block in our protocol. The difficulty of our setting comes from the fact that we need additions, multiplications, and comparisons to solve the best arm identification problem, whereas a partially homomorphic cryptosystem such as Paillier's provides only homomorphic additions. Therefore, in our protocol we distribute the computation among several participants and insure that each of them can only learn the specific information needed for performing their task, and no any other information. Thus, we show that our distributed protocol has no single point of failure, in the honest-but-curious cloud model. The overhead due to the security primitives of our protocol depends only on the number of arms K and not on the budget N . This is a desirable property because in practice the budget N (i.e., the number of arm pulls that we are allowed to do) is often much larger than the number of arms K among which we can choose.

We prove the security of our protocol in Section 6.3, and we present proof-ofconcept experiments suggesting its feasibility in Section 7.4.5. We discuss related work in Section 6.5, and conclusions and future work in Section 6.6.

-Secure Protocol

Secure Protocol

Security Model

We assume that the reward functions associated to the arms as well as the best arm identification algorithm are outsourced to some cloud. We assume that the cloud is honest-but-curious i.e., it executes tasks dutifully, but tries to extract as much information as possible from the data that it sees. The user indicates to the cloud her budget and receives the best arm that the cloud can compute using the user's budget. The user does not have to do any computation, except for eventually decrypting i * if she receives this information encrypted from the cloud. We expect the following security properties:

1. No cloud node can learn at the same time information about the rewards and about the ranking of the arms.

2. By analyzing the messages communicated between the different cloud nodes, no information can be learned about the rewards or about the ranking.

The two aforementioned properties essentially ensure that the desired protocol has no security single point of failure. In particular, the first property says that (i) there may be some cloud node that knows the ranking of the arms (hence also the best arm), but it is not allowed to know which rewards are associated to these arms, and (ii) there may also be some cloud node that knows some rewards, but it is not allowed to know which arms are associated to these rewards. If all cloud nodes collude, the cloud can learn the rewards associated to the arms1 . We do not consider collusions in our model.

Security Background

We use Pailler's public key encryption scheme [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. We first recall the definition of public-key encryption. Pailler's encryption scheme is IND-CPA secure. We recall the definition of IND-CPA before presenting the scheme itself that has an additive homomorphic property that we use in our protocol.

Secure Algorithm

We revisit the successive rejects (SR) algorithm, presented in Section 2.2.2, page 14, in order to satisfy the properties outlined in Section 6.2.1. We consider K arms. We note n the set of the n first integers: n = {1, . . . , n}. Recall that SR has K-1 phases and at each phase j, it uses a budget of n j to pull each of the still candidate arms. At the end of each phase, SR rejects the worst arm, based on all pulls observed since the beginning. For the communications BAI → RP j , RP j → BAI, and RP j → Comp, the list concerns all the arms that are still candidates i.e., the set A j .

U BAI RP j Comp Data Owner (1) N (5) E(pk U , i * ) (2*) nj, E(pk RP j , σj), σj list of E(pk Comp , sum(i)) σj(list E(pk Comp , sum ′ (i))) (3*) (3*) σj(list of E(pk Comp , sum ′ (i))) (4*) arg min(sum ′ (i)) (0) list of E(pk Comp , x(i)), E(pk RP j , ϵ)
In the sequel, each time we refer to some (pk, sk), and associated encryption/decryption functions, we assume they are done using Paillier's cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. In particular, we rely on the homomorphic addition property of Paillier's cryptosystem i.e., E(pk, x + y) = E(pk, x) • E(pk, y).

In our security protocol, we assume K + 3 participants:

• DO is the Data Owner, who is not in the cloud. DO sends the encrypted arm values E(pk Comp , x i ) and E(pk RP j , ϵ) for i ∈ K and j ∈ K -1 .

• U is the User, a participant that is not in the cloud. The user generates (pk U , sk U ) and shares pk U and the budget N with the cloud. The cloud nodes compute i * and at the end BAI sends E(pk U , i * ) to the user, who is able to decrypt it using her secret key sk U .

• BAI (Best-Arm Identification) is the node responsible for executing the K -1 phases of the SR algorithm. BAI generates K -1 uniformly selected permutations σ j of K + 1j (as there are K + 1j candidate arms at round j). Each σ j is shared with the node RP j , but not with Comp. At each phase, BAI knows which arm is the worst and should be rejected, and after the last phase it knows which arm is the best. However, BAI does not know which rewards are associated to the arms because the rewards are encrypted with pk Comp .

• Comp is the node responsible of choosing the worst one among the sums of rewards associated to the candidate arms. Comp generates (pk Comp , sk Comp ) and shares pk Comp with all other cloud nodes and DO.

• RP 1 , . . . , RP K-1 are K -1 nodes, each of them knowing the value ϵ that is needed to generate a reward for each arm. Each node RP j generates (pk RP j , sk RP j ) and shares pk RP j with BAI and DO.

Node

BAI Comp RP j

Does know

• ranking of arms (including best arm)

• sums of rewards

• arms still candidate at phase j • arms already rejected before phase j • sums of rewards added at phase j

Does not know

• sums of rewards of any arm (Theorem 6.3.1)

• mapping between sums of rewards and the arms that produced them (Theorem 6.3.3) • ranking of arms (including best arm) (Theorem 6.3.2)

• ranking of arms (including best arm) (Theorems 6.3.4 and 6.3.5) • sums of rewards from phases 1, . . . , j -1, j + 1, . . . , K -1 (Theorem 6.3.6) Table 6.1: What each cloud node knows and does not know.

Complexity

We give here a brief description of the complexity, in terms of the number of calls to E and D (the costliest operations).

• At Step 0, DO computes ∀i ∈ K , E(pk Comp , x(i)). It also encrypts ϵ for each RP j , thus having O(K) complexity.

• At

Step 2, BAI computes a new encrypted permutation, that can be encoded as [E(pk RP j , σ j (1)), . . . , E(pk RP j , σ j (K + 1j)], thus having O(Kj) = O(K) complexity.

• At Step 3, RP j computes the added rewards. Given the algorithm in Section 6.2.3, this step has O(K) complexity.

• At Step 4, Comp decrypts all partial sums, with a complexity of O(K), before sending the argmin to BAI.

Steps 2, 3, 4 are repeated K -1 times. The total complexity of these three steps is then O(K 2 ), and the total complexity of the algorithm is O(K 2 ).

Note that the complexity of the algorithm is independent from the total budget N , which is a great advantage as typical budgets for these kinds of problems are often elevated and usually much larger than the number of arms. More precisely, the complexity related to N is hidden by the complexity of the encryptions.

Security Proofs

In this section, we prove that our secure algorithm presented in Section Section 6.2.3 satisfies the two desirable security properties outlined in Section 6.2.1: we prove

2 • 1 2 + 1 2 • 1 2 + x 2 + negl(λ) = 1 2 + x 4 + negl(λ)
, thus yielding to B an advantage of x 4 + negl(λ) in the IND-CPA game, in polynomial time. This is a contradiction with the fact that Paillier is IND-CPA secure.

Security Proofs for BAI

Lemma 6.3.3. From the data obtained at round j, a honest-but-curious BAI does not know the sum of the rewards of any arm. More precisely, for R the set of possible rewards,

P A reward (data BAI j ) ∈ {i, reward(i)} i∈ K+1-j - 1 |R| < negl(λ)
where A reward (data BAI j ) returns a tuple (i, g reward (i))), with g reward (i) being A's guess of the sum of rewards of i.

Proof. At round j, BAI has access to the permuted list of the encrypted partial sums, as well as to the permutation σ j and the index i min j of the lowest-ranking element from round j. From the first two arguments, BAI can access to the (unpermuted) list of the encrypted partial sums of the arms rewards se j = E(pk Comp , sum α 1 ), . . . ,

E(pk Comp , sum α K+1-j )
, where the α i are the arms still present in the algorithm at step j. So we can equivalently say that data j BAI = [se j , i min j ]. Assume that there exists a PPT adversary A able to break the above inequality, with advantage x + negl(λ): given [se, i min j ] as input, A returns some tuple (i, g reward ) where g reward is the guessed reward of the arm α i . The guess is correct with probability 1 |R| + x + negl(λ). Also note that, on average, i = 1 with probability

1 K+1-j .
Let us consider a classical IND-CPA game as previously defined. B first simulates an execution of blind bandits, with arm rewards of its own choice. From this, B gets a list of simulated sums ŝum 1 , . . . , ŝum K+1-j and the lowest ranking arm îmin j .

B selects a random value ŝum 0 different from all sums, sends the tuple (E(pk Comp , ŝum 0 ), E(pk Comp , ŝum 1 )) to the challenger, and receives E(pk Comp , ŝum b ).

Then, B calls A( E(pk Comp , ŝum b ), E(pk Comp , ŝum 2 ), . . . , E(pk Comp , ŝum K + 1j) , îmin j ) which returns (i, g reward ). If i = 1 and g reward = ŝum 1 then B returns 1. Otherwise B returns a random guess.

B is correct in the following cases:

• i = 1, b = 1 and A guesses correctly. This event happens with probability

1 K+1-j 1 2 1 |R| + x . • i = 1, b = 1,
A does not return ŝum 1 and B makes a correct random guess.

This happens with probability

1 K+1-j 1 2 1 -1 |R| -x 1 2 .
of c i with advantage x + negl(λ). Then we prove that the adversary breaks the IND-CPA property of Paillier's cryptosystem. Note that, on average, i = 1 with probability 1 K , and that a decryption is correct with probability 1 |R| + x + negl(λ). If we consider an IND-CPA game where the strategy of B is the same as in the proof of Lemma 6.3.3 (i.e., simulate a blind bandit execution so they can call A), we get that B has an advantage of 1 4K x in the IND-CPA game, which is a contradiction with Paillier being IND-CPA secure. Proof. Assume that there exists an adversary A able to break the above inequality, given M , in PPT. We then prove that an adversary B is able to break IND-CPA security of Paillier's scheme in PPT.

Security Proof for an External Observer

Let us consider a classical IND-CPA challenge, in which B choses two rewards r 0 , r 1 and sends them to the challenge. The challenger returns E(pk Comp , r b ), where b is a uniformly random bit. Then, B simulates a secure multi-armed bandit protocol, with 2 arms, so that at the end of round 1, one of the arms has for encrypted sum of rewards the value E(pk Comp , r b ), the other being random. This is possible because in this simulation, B can set herself the rewards x i of each arm, as well as the budget for round 1. Furthermore, knowing the cleartext of every encrypted value at any time, B can simulate the full protocol by herself (especially, she can simulate Comp execution). This simulation yields a set of messages M . Now, calling A(M ), B will retrieve in PPT, with some non-negligible advantage, some information about the sums of rewards of one of the arms. With probability 1 2 , this information will be about the arms of r b , thus giving, in PPT, a non-negligible advantage in the IND-CPA game, as B is able to find the value of b with some advantage. This is a contradiction with the fact that Paillier is IND-CPA secure. Theorem 6.3.8. An external observer, having access to the set M of all the messages exchanged during the protocol, cannot infer anything about the ranking of any arm:

P A rwd (M ) ∈ {i, ranking(i)} i∈ K - 1 K < negl(λ)
Proof. It is obvious that such an observer can deduce the permuted list of rankings by listening to data exchanged at step 4. However, from the data of one round, it is impossible to know more: the data from one round is an encrypted permuted sum of rewards S, the lowest permuted index i, and the same sum, with the lowest element removed S ′ (steps 3,4,2). This is equivalent of having knowledge of S and i only.

also compute c ′ i = E(pk, m ′ i ). Then, if A(σ([c b , c ′ 2 , . . . , c ′ k ]
), σ(0)) = 0, B returns 0, else 1. If A has a non-negligible advantage x, we prove similarly to the other proofs that B has a advantage of x 2 in the IND-CPA game, which is a contradiction. Now, because of Lemma 6.3.2, having access to all messages does not change anything. This is because each new round is indistinguishable from a simulation run by B, so an advantage in the "all-rounds" game would yield an advantage in the "one-round" game.

Experiments

Setup

We report on a proof-of-concept experimental study of our proposed protocol. We implemented and compared:

• SR: the successive rejects algorithm, adapted from [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF]. We give the pseudocode of SR in Algorithm 1.

• SR-secured: our proposed protocol, which adds security guarantees to SR. We describe SR-secured in Section 6.2.3 and we outline its workflow in Figure 6.2.

We implemented the algorithms in Python 3. Our code is available on a public git repository 3 . For SR-secured, we used phe 4 , an open-source Python 3 library for partially homomorphic encryption using the Paillier's cryptosystem. We summarize the results in Figure 6.3 and we discuss them next. We carried out these experiments on a laptop with Intel Core i5 3.10GHz and 8GB of RAM. We used 2048 bits keys. The results are averaged over 100 runs.

Run time comparison SR vs SR-secured

In each half of Figure 6.3a, we have 12 points, corresponding to the pairwise combinations between 4 budget values N (100000, 200000, 300000, 400000) and 3 values for the number of arms K (5,10,[START_REF] Fu | Design Tradeoffs for Data Deduplication Performance in Backup Workloads[END_REF]. We split the figure in two plots with different Y axis because the observed times are in the order of tens of milliseconds for SR and tens of seconds for SR-secured.

For SR, we observe that the time varies more on N and less on K, which makes sense because the operations depending on N (i.e., picking random numbers in the rewards generation) are more expensive than the operations depending on K (i.e., additions and multiplications).

On the other hand, for SR-secured, the slight run time increase depending on N is barely visible (hence the curves look rather constant) because of the threeorders-of-magnitude overhead that is a natural consequence of the high number of encryptions and decryptions performed by SR-secured.

As explained in Section 6.2.3, each participant and encryption/decryption from SR-secured is useful for the protocol in order to guarantee the desired security properties. We stress that the time of SR-secured barely grows when increasing the budget N , which confirms the essential property that we outlined in the complexity discussion: the number of cryptographic primitives does not depend on N . Hence, we were easily able to run SR-secured for large budgets as we show in the figure .  We conclude from this experiment that SR-secured retains the scalability of SR while adding an overhead (depending on K and not on N ) due to the security primitives. Obviously, both algorithms compute exactly the same result i.e., the best arm. Moreover, before running this time comparison study, we carefully checked that all intermediate sums and arm rankings are identical for SR and SR-secured, despite the encryptions and decryptions that the latter algorithm performs.

Zoom on SR-secured

In Figure 6.3b we highlight how the total time taken by SR-secured is split among the participants. We obtained this figure for N =400000 and K=5, hence there are 4 phases, thus 4 participants RP 1 , RP 2 , RP 3 , RP 4 in addition to Comp, BAI, the data owner DO, and the user U.

First, notice that the shares of U and DO of the total time are relatively small, which is a desired property. Indeed, we require the DO only to encrypt her knowledge of the arms before outsourcing such encrypted data to the cloud (step 0 in Figure 6.2). This could be actually done only once at the beginning and then all runs of the bestarm identification algorithm can be done using the same encrypted data, regardless of the user that pays for such a run.

Moreover, we require U to not do any computation effort other than decrypting the result of the best-arm identification algorithm that the cloud returns to her (step 5 in Figure 6.2).

Among the cloud participants, we observe that BAI takes the lion's share of the total running time. This is expected because the role of BAI is similar to a controller that interacts with all other cloud participants.

In what concerns Comp and the RP j , their shares are quite similar. We observed the same behaviour regardless of the chosen N and K on which we zoom.

Related work

To the best of our knowledge, our work is the first that relies on public-key encryption in order to add privacy guarantees to best-arm identification algorithms for multiarmed bandits.

There is a recent line of research on multi-armed bandits using differential privacy techniques [Dwo06; DR14], which are based on adding an amount of noise to the data to ensure that the removal or addition of a single data item does not affect the outcome of any data analysis. These works have either focused on strategies to obtain: (i) privacy-preserving input guarantees i.e., make the observed rewards un-6.6 -Conclusions and Future Work intelligible to an outside user [START_REF] Gajane | Corrupt Bandits for Preserving Local Privacy[END_REF], or (ii) privacy-preserving output guarantees i.e., protect the chosen actions and their associated rewards from revealing private information [START_REF] Mishra | Nearly) Optimal Differentially Private Stochastic Multi-Arm Bandits[END_REF][START_REF] Aristide | Algorithms for Differentially Private Multi-Armed Bandits[END_REF].

There are some fundamental differences between this line of work based on differential privacy and our work based on public-key encryption. First, the considered multi-armed bandit problems are different. Indeed, we focus on identifying the best arm, which is equivalent to minimizing the simple regret, that is the difference between the values associated to the arm that is actually the best and the best arm identified by the algorithm. On the other hand, the aforementioned works consider the cumulative regret minimization that roughly consists of minimizing the difference between the rewards observed after pulling N times the best arm and the rewards observed during the N pulls done by the algorithm.

A second difference is as follows. On the one hand, our secured algorithm based on public-key encryption is guaranteed to return exactly the same result as the (non-secured) SR algorithm [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] on which we rely as a building block in our protocol. On the other hand, the result of a differentially-private algorithm contains by definition some noise, hence it is different from the result of the algorithm without privacy guarantees.

Third, by construction, the performance measure (the regret) of our secure algorithm remains the same as for the non-secured version, since both versions use the same arm-pulling strategies (that is, the performed encryptions/decryptions have no influence on the choice of arms to be pulled). The price we pay for making the algorithm secure comes only in the form of additional time needed for the encryptions and decryptions. In contrast, in the differential privacy approach, noise is introduced in the inputs/outputs in order to guarantee that the algorithms are differentially private and this has a direct impact on the arm-selection strategies. Therefore, the performance of the differential private versions of the algorithms suffers an increased regret with respect to their non-secured versions by an additive [START_REF] Aristide | Algorithms for Differentially Private Multi-Armed Bandits[END_REF] or a multiplicative factor [GUK18; MT15].

Conclusions and Future Work

We studied the problem of best-arm identification in multi-armed bandits and we addressed the inherent privacy concerns that occur when outsourcing the data and computations to a public cloud. Our main contribution is a distributed protocol that computes the best arm while guaranteeing that (i) no cloud node can learn at the same time information about the rewards and about the ranking of the arms and (ii) by analyzing the messages communicated between the different cloud nodes, no information can be learned about the rewards or about the ranking. To do so, we relied on the partially homomorphic property of Paillier's cryptosystem. The overhead due to the security primitives of our protocol depends only on the number of arms K and not on the budget N . Our experiments confirmed this property.

Looking ahead to the future work, there are many directions for further investigation. For example, we plan to investigate whether we can leverage an addition-homomorphic cryptosystem other than Paillier's, which may be more efficient in practice and could help us reduce the run time gap between the secured and the non-secured algorithms that we observed in our proof-of-concept experimental study. Additionally, we plan to add privacy guarantees to other multi-armed bandit settings e.g., cumulative regret minimization [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF] or best-arm identification in linear bandits [START_REF] Soare | Best-Arm Identification in Linear Bandits[END_REF], where the rewards of the arms depend linearly on some unknown parameter. 2:

-Conclusions and Future Work

for j from 1 to K-1 do 3:

n j ← 1 log(K) N -K K + 1 -j - j-1 l=0 n l 4:
for all i ∈ K do 5:

sum[i] ← E(pk Comp , 0) 6: j ← 1 7: function Start_Round_BAI ◃ Step 2 * 8:
σ j ← random permutation of Kj + 1 Decrypt E(pk RP j , σ j ), retrieve σ j and un-permute σ j (sum) to get sum 13:

for each arm in sum do Decrypt each element of σ j (sum)

18:

x min ← the index of a lowest element of the decrypted list, randomly chosen amongst all lowest elements

u min ← σ -1 j (x min ) 22:
Remove arm u min from the list of participants, and from sum to reflect so Chapter 7 -Secure Outsourcing of Multi-Armed Bandits

Abstract

We consider the problem of cumulative reward maximization in multi-armed bandits. We address the security concerns that occur when data and computations are outsourced to an honest-but-curious cloud i.e., that executes tasks dutifully, but tries to gain as much information as possible. We are motivated by situations where data used in bandit algorithms is sensitive and has to be protected e.g., commercial or personal data. We rely on cryptographic schemes and propose UCB-DS, a distributed secure protocol based on the UCB algorithm, which yields the same cumulative reward as UCB while satisfying desirable security properties that we formally prove. In particular, cloud nodes cannot learn the sum of rewards for more than an arm or the cumulative reward. Moreover, by analyzing messages exchanged among cloud nodes, external observers cannot learn the cumulative reward or the sum of rewards produced by some arm. We show that the overhead due to cryptographic primitives is linear in the size of the input.

Our implementation confirms the linear-time behavior and the practical feasibility of our protocol, on both synthetic and real-world data.

This

Introduction

Stochastic Multi-armed Bandit Game

The stochastic multi-armed bandit game is a sequential learning framework where a learning agent aims at maximizing its cumulative reward while successively interacting with an uncertain environment. At each time step, the agent chooses an action (a bandit arm) from among a fixed set of actions with unknown associated values. The environment responds with a stochastic feedback (reward) drawn from the distribution associated with the chosen action. The learning agent uses the received feedback to update its estimate of the values for the chosen action and to decide which action to choose next. The agent has to continuously face the so-called exploration-exploitation dilemma: it can decide to explore actions with more uncertain associated values, or to exploit the information already acquired by selecting the action with the seemingly largest associated value. Cumulative reward maximization has been already extensively studied for several multi-armed bandit settings (see [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF] for a survey). In this chapter, we address the security concerns that occur when outsourcing the cumulative reward maximization data and computations to the cloud.

Our scenario is inspired by the machine learning as a service cloud computing model, for which security is known as a major concern [START_REF] Bourse | Fast Homomorphic Evaluation of Deep Discretized Neural Networks[END_REF]. As a motivating example, assume:

• A data owner i.e., a company that wants to monetize some collected data that can be input for bandit algorithms. For instance, the data owner may be a large company (e.g., Netflix) that collected a large quantity of customer preferences on TV series.

• A user i.e., a company that wants to spend some budget to obtain the output of a bandit algorithm run on data owner's data. For instance, the user may be a smaller company that considers acquiring streaming rights for a package of TV series and wants to estimate, given the user's budget, what is the maximal reward that the package of TV series could generate.

The cumulative reward captures such an income for a package of series (outsourced arms) because it sums up the customer preferences (rewards) produced by each series in the package. This scenario allows the data owner to monetize some data that it collected and that the user wants to reuse. However, the data owner keeps ownership of the data, hence users are incited to spend a larger budget to obtain a more accurate estimate of the cumulative reward. We assume that the interaction between the data owner and the user is done using the cloud (as shown in Thus, by relying on a standard cloud provider, the data owner does not have to build its own infrastructure. The data owner does the data outsourcing, and the user interacts directly with the cloud, by sending the budget and receiving the cumulative reward that can be learned for that budget. Such outsourced data may be sensitive (for instance, economical, personal or medical data) and we address the security concerns that occur when outsourcing data and computations. In other words, we want the outsourced learning algorithm to be run while protecting data against unauthorized access.

The problem that we address is how to allow the user to obtain precisely the same cumulative reward as with a standard algorithm, Upper Confidence Bound (UCB) [ACBF02; BC12], within a reasonable computation time and while preserving the data privacy. Indeed, the outsourced data can be communicated over an untrustworthy network and processed on some untrustworthy machines, where malicious cloud users may learn sensitive data that belongs only to the data owner. The privacy-preserving cumulative reward maximization is a hard problem. In [GUK18; MT15; TD16] the authors use differential privacy [START_REF] Dwork | Differential Privacy[END_REF] in these approaches, the reward returned to the user is not the exact reward that can be learned for the user's budget (this happens because noise is injected in the input/output). It is unavoidable in any privacy-preserving approach that uses differential privacy.

We take a complementary look by relying on cryptography instead of differential privacy. To the best of our knowledge, our approach is original and its goal is to have an exact reward. The security for obtaining an exact reward has a price, since the computation time may increase because of cryptographic primitives that are time-consuming in practice. More precisely, we require that the data owner (which can be seen as an oracle knowing the reward functions associated with each arm) encrypts her data before outsourcing it to the cloud.

Then, the cumulative reward maximization algorithm is run directly in the encrypted domain, and by using the right primitives, the (encrypted) output should be exactly the same as for standard UCB, at the price of an increased computation time. From a theoretical point of view, the problem could be straightforwardly solved by using a fully homomorphic encryption scheme [START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF], which allows to compute any function directly in the encrypted domain. However, it remains an open question how to make such a scheme work fast and be accurate in practice.

Indeed, the state-of-the-art fully homomorphic systems either yield only approximate results when they work with real numbers as those that we need in the UCB algorithm (this is the case for Microsoft SEAL [Sea] using CKKS scheme [START_REF] Hee Cheon | Homomorphic Encryption for Arithmetic of Approximate Numbers[END_REF] for real numbers) or do not support real numbers at all (this is the case for IBM HElib [START_REF] Halevi | Algorithms in HElib[END_REF]). Hence, it is not currently possible to program an algorithm such as UCB in a fully homomorphic system and obtain exactly the same result as in the standard, non-encrypted UCB.

Consequently, our challenge is to rely on simpler cryptographic schemes and design a distributed protocol with several cloud node participants such that each of them can only learn the specific data needed for performing its task and nothing else e.g., if a participant does in clear computations on real numbers, these computations concern data of only one arm, and no other participant has access to this piece of data.

Our distributed algorithm returns exactly the same cumulative reward as UCB, while satisfying desirable security properties such as: only the user can see the 7.1 -Introduction cumulative reward, which cannot be learned by any cloud node participant nor by an external observer. We precisely characterize our security model and security guarantees later on in the chapter.

To achieve our goals, we rely on indistinguishable under chosen-plaintext attack (IND-CPA) cryptographic schemes: symmetric encryption AES-CBC [NIS01; BDJ+97] and asymmetric partially homomorphic Paillier's scheme [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. We formally prove the security of our protocol and we precisely characterize the number of needed cryptographic operations.

Related work

We summarize related work in Table 7.1, where each line corresponds to a standard problem in stochastic multi-armed bandits. The most popular problem is cumulative reward maximization [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF], where the agent uses its limited budget to maximize the sum of observed rewards.

To fulfil this goal, the agent decides which arm to pull next based on previously observed rewards: the agent can either choose to exploit the information acquired thus far and keep selecting the arm with the seemingly largest reward, or to explore by pulling one of the most uncertain arms. UCB is a standard algorithm for cumulative reward maximization [ACBF02; BC12].

From the privacy-preserving point of view, there is a recent line of research on enhancing algorithms such as UCB with differential privacy. These works have either focused on strategies to obtain: (i) privacy-preserving input guarantees i.e., making the observed rewards unintelligible to an outside user [START_REF] Gajane | Corrupt Bandits for Preserving Local Privacy[END_REF], or (ii) privacypreserving output guarantees i.e., protecting the chosen actions and their associated rewards from revealing private information [MT15; TD16]. Differential privacy algorithms have been also proposed for different bandit models than the standard stochastic one that we consider in this chapter e.g., for contextual bandits [START_REF] Shariff | Differentially Private Contextual Linear Bandits[END_REF].

There are some fundamental differences between this line of work based on differential privacy [GUK18; MT15; TD16] (top left box in Table 7.1) and our work based on cryptography (top right box in Table 7.1), which to the best of our knowledge is a novel approach in the community. On the positive side, the running time overhead of differentially-private algorithms is negligible, but on the other side the returned cumulative reward is different from the output of standard UCB. Indeed, to obtain differentially-private guarantees for a bandit algorithm, noise is added to the input or the output of the algorithm. Thus, the cumulative reward obtained using a differentially-private algorithm is different from that obtained by the algorithm without privacy guarantees. This is reflected in the regret analysis of the algorithms (where the regret is given by the difference in the cumulative reward obtained by a learning agent and the best cumulative reward possible obtained by always playing the best arm): the regret of differentially-private bandit algorithms have as overhead an additive [START_REF] Aristide | Algorithms for Differentially Private Multi-Armed Bandits[END_REF] or a multiplicative factor [GUK18; MT15] with respect to the regret of their non-private version. In contrast, our cryptography-based algorithm is guaranteed to return exactly the same cumulative reward as the standard UCB.

The second line in Table 7.1 corresponds to a different bandit problem that is 1. each cloud node is trusted: it correctly does the required computations, it does not sniff the network and it does not collude with other nodes, 2. an external observer has access to all messages exchanged over the network.

The user indicates to the cloud her budget N and receives the cumulative reward R that the cloud computes using the K arms outsourced by the data owner and the user's budget N . The user does not have to do any computation, except for decrypting R when the user receives this information encrypted from the cloud. We expect the following security properties:

1. No cloud node can learn the cumulative reward.

2. The user cannot learn information about the rewards produced by each arm or which arm has been pulled at some round.

3. By analyzing the messages exchanged between different cloud nodes, an external observer cannot learn the cumulative reward, the sum of rewards produced by some arm, or which arm has been pulled at some round.

We next give a brief intuition for each property. Property 1 implies that only the user can see in clear the cumulative reward for which she spends a budget. Property 2 ensures that the user can see only the information for which she pays, and nothing else. Otherwise, depending on the difficulty of the bandit problem, the user could estimate the arm values based on the contribution of each arm to the cumulative reward, which would leak information that should be known only by the data owner. Property 3 states that if some curious cloud admin analyzes all messages exchanged over the network, then she should have no clue on any input, output, or intermediate data that is used by the cumulative reward maximization algorithm. Next, we design a distributed protocol that satisfies the aforementioned properties. Intuitively, we achieve these properties by exchanging only encrypted messages, and moreover, by distributing the computations among several cloud node participants, each of them having access only to the specific data that it needs for performing its task and nothing else. The challenge is to efficiently distribute tasks among as few cloud participants as possible, while minimizing the time needed for cryptographic primitives.

Overview of UCB-DS

In Figure 7.2, we present an overview of UCB-DS. There are K+1 cloud participants: K arm nodes R i and a node AS (Arm Selector) that is the controller of the protocol.

We assume that the data owner and all cloud participants share the same symmetric AES-CBC key, which is used for the encryption function Enc in Figure 7.2. We also assume that the user U generates a key pair (pk, sk) using the Paillier cryptosystem, and this pk is used for the encryption function E U in Figure 7.2. In the sequel, by x we denote the set {1, . . . , x}, and by y||z we denote the concatenation of y and z.

-UCB-DS: A Distributed and Secure Protocol Based on UCB Algorithm

In a nutshell, UCB-DS works as follows:

• Figure 7.2a (steps 0 and 1). For i ∈ K , the data owner outsources to arm node R i the reward function (encrypted with Enc) associated to arm i. The user sends to the cloud her budget N .

• Figure 7.2b (steps 2, 3, and 4). This is the core of the protocol, being done during 1+N -K iterations: once for the initialization phase of UCB and N -K times for the exploration-exploitation phase of UCB cf. Algorithm 2. For each iteration, all arm nodes interact to decide which arm should be pulled next and communicate this information to AS. The arm nodes communicate in a random order, which changes at each iteration. All messages exchanged between nodes are encrypted with Enc. Although each arm node stores information about its rewards, it never reveals this information to other nodes.

• Figure 7.2c (steps 5 and 6). After spending the user's budget, each arm node sends to AS the sum of rewards that it produced, encrypted with E U . Due to the additive homomorphic property of Paillier cryptosystem, AS is able to sum up the K partial rewards to compute the cumulative reward E U (R) directly in the encrypted domain. Only the user can decrypt this information.

We next detail each step and present pseudocode only when the step is not trivial.

Algorithm 8 Pseudocode of AS during steps 2, 3, and 4 cf. Figure 7.2b

1: i m ← 0 2: for j ∈ N -K + 1 do 3:
σ ← random permutation of K 4:

for i ∈ K do ◃ b i is a bit indicating whether arm i should be pulled or not 5:

if i m = 0 or i m = i then 6: b i ← 1 7: else 8: b i ← 0 9: if σ(i) ̸ = K then ◃ next i indicates the next arm node in the ring, or 0 if i is the last cf. σ 10: next i ← σ -1 (σ(i) + 1) 11: else 12: next i ← 0 13: Send Enc(b i ||first i ||next i ) to arm node R i 14: Receive ciphertext from arm node R σ -1 (K) ◃ ciphertext is Enc(i m ) 15: i m ← Dec(ciphertext)
Step 0. We recall (cf. Algorithm 2) that the data owner knows µ 1 , . . . , µ K defining K Bernoulli distributions associated to the K arms. The data owner sends to each arm node R i the encrypted value Enc(µ i ), for i ∈ K . Since the data owner and the 123

AS R σ

-1 (1) R σ -1 (2) . . . R σ -1 (K) . . . (2) Enc(b σ -1 (1) ||1||σ -1 (2)) (2) Enc(b σ -1 (2) ||0||σ -1 (3)) (2) Enc(b σ -1 (K) ||0||0) (3.1) Enc(B m ||i m ) (3.2) Enc(B m ||i m ) (3.K-1) Enc(B m ||i m ) (4) Enc(i m ) (b)
Steps 2, 3, and 4 are done 1 + N -K times.

User AS R 1 . . . . . . R K (5) E U (s 1 ) (5) E U (s K ) (6) E U (R)
1: Receive ciphertext1 from AS ◃ ciphertext1 is Enc(b i ||first i ||next i ) 2: (b i , first i , next i ) ← Dec(ciphertext1) 3: t ← t + 1 4: if b i = 1 then
◃ Pull arm i and update its variables 5:

r ← pull(i)

6:

s i ← s i + r 7: n i ← n i = 1 8: B i ← s i n i + 2 ln(t) n i ◃ Always update B i because t changes 9: if first i = 0 then 10: Receive ciphertext2 from preceding arm node in ring ◃ ciphertext2 is Enc(B m ||i m ) 11: (B m , i m ) = Dec(ciphertext2) 12: if first i = 1 or B m < B i then 13: i m ← i 14: B m ← B i 15: if next i ̸ = 0 then 16: Send Enc(B m ||i m ) to R next i 17: else 18:
Send Enc(i m ) to AS cloud nodes have shared the key used for Enc, then each arm node R i can decrypt and obtain µ i . Moreover, each node R i initializes to 0 the following two variables that it later on updates during the protocol: s i (i.e., sum of rewards for arm i) and n i (i.e., number of times the arm i has been pulled). Additionally, each arm node R i initializes a variable t = K -1, which is later on updated and needed for the computation of B i .

Step 1. This step is trivial: the user sends her budget N to AS, which receives N .

Steps 2, 3, and 4 are the most technical pieces of our protocol. We present the pseudocode of these steps in Algorithms 8 and 9 and we explain them next.

Step 2. This step corresponds to everything except the last two lines in Algorithm 8 and has 1 + N -K iterations. At each iteration, AS sends three pieces of information to the R i nodes. The first one is a bit b i indicating whether the arm i should be pulled or not. At the first iteration (that corresponds to the initialization phase of UCB cf. Algorithm 2), AS sends b i = 1 to each arm, and at the next N -K iterations (that correspond to the exploration-exploitation phase of UCB cf. Algorithm 2), AS sends b i = 1 only to a chosen arm i m and sends b i = 0 to all other arms. Moreover, at each iteration, AS generates a permutation σ : K → K (i.e., a function for which every element occurs exactly once as an image value), based on which AS computes two more components that it sends to R i : first i that indicates whether the arm node is the first of the ring hence it should initialize B m and i m , and next i that indicates to which node the updated B m and i m should be sent during Step 3. The arm node that receives 0 on the next component is the last one of the ring and sends i m to AS, which thus knows which arm should be pulled next. All three components that AS sends to R i are thus useful for the ring computation of i m in Step 3. The permutation changes at each AS iteration because it is important to have a random order during the ring communication. Without a random order, it may happen that the last arm is much better than all others and it is almost always pulled, hence it has a very good estimate of the cumulative reward.

Step 3. This step corresponds to everything except the last two lines in Algorithm 9. Note that the variable t stores how many arm pulls have been done in total since the beginning of the protocol. As discussed for Step 0, each arm initialized t = K -1, hence t = K after the first iteration of AS, which allows to compute the first B i values at the end of the initialization phase. Then, during the next N -K iterations of AS, the variable t is incremented, which allows to compute B i values during the exploration-exploitation phase. To decide which arm has the highest B i and should be pulled at the next iteration, the arm nodes R i do a distributed ring computation, where the first arm node according to permutation σ (i.e., the only arm node that received first i =1) initializes max value B m and argmax i m . At each ring iteration (Steps 3.1, . . ., 3.K-1, cf. Figure 7.2b), the current arm node sends updated B m and i m to the next arm node cf. σ. Even though B m and i m do not change, it is important to re-encrypt Enc(B m ||i m ) before sending it to the next node to prevent an external observer from knowing when there is a change in the max and argmax (and hence learn information about which arms are pulled more often). Finally, once the ring computation reaches the last arm node relative to σ (i.e., the only one that received next i = 0), we go to Step 4.

Step 4. This step corresponds to the last two lines in Algorithm 9 (the last arm node in the ring sends Enc(i m ) to AS), followed by the last two lines in Algorithm 8 (AS receives and decrypts the index of the arm to be pulled at the next iteration).

Step 5. Once the budget is entirely spent and no more arm has to be pulled, each bandit arm R i (for i ∈ K ) encrypts with E U the sum of its rewards s i and sends the result E U (s i ) to AS.

Step 6. The node AS takes the K ciphertexts E U (s i ) received at Step 5, and

computes E U (R)=E U K i=1 s i = K i=1 (E U (s i ))
. This identity follows from the additive homomorphic property of Paillier cryptosystem, cf. Section 7.2. Then, AS sends E U (R) to the user, who is able to decrypt using her sk and hence the user obtains R.

-Analysis of UCB-DS

Analysis of UCB-DS

Next, we analyze the correctness (Section 7.4.1), the security properties (Section 7.4.2), and the complexity (Section 7.4.3) of UCB-DS.

Correctness

We point out that UCB-DS outputs exactly the same cumulative reward as UCB. The computations done in Algorithms 8 and 9 to maximize the reward are the same as the one done in Algorithm 2. Indeed, if we take UCB-DS and remove all encryptions/decryptions (both symmetric and asymmetric), and all messages are communicated in clear between participants, then we obtain a protocol that we call UCB-D, which outputs exactly the same result as UCB-DS. This happens because of the consistency property of the chosen cryptographic schemes i.e., if we encrypt a message M using Enc (or E U , respectively) to obtain a ciphertext C, then if we decrypt C using Dec (or D U , respectively), then we obtain exactly M .

Next, to reduce UCB-D to UCB, we simply remove all distributions of tasks among participants and rewrite UCB-D as a sequential algorithm to obtain exactly UCB. In particular, the random permutation σ (that is generated at each round to decide in which order to iterate over arms) reduces to the randomness in the argmax function used in standard UCB (cf. Algorithm 2) when, if several arms have maximal B i -value, then the argmax should be randomly picked among those arms.

Security

In Table 7.2, we summarize what each participant in UCB-DS knows/does not know, while referencing the relevant theorems. The main properties of our protocol are:

1. No cloud node can learn the cumulative reward and additionally:

• Only AS and the pulled arm know which arm is pulled at each round.

Arms that are not pulled can guess the pulled arm with average probability 1 2 + 1 2K . • Only arm node R i knows the sum of rewards for arm i.

2. Only U knows the cumulative reward, and she knows nothing else.

3. An external observer cannot learn the cumulative reward, the sum of rewards for some arm, or which arm has been pulled at some round.

These properties subsume the list of desirable security properties listed in Section 7.3.1. Before formally stating the theorems, we point out some assumptions. First, we recall (cf. Section 7.3.1) that the participants are honest-but-curious and do not collude. We discuss the impact of collusions at the end of this section. Second, during the ring computation (cf. Step 3 in Section 7.3.2), each arm learns an intermediate max value B m , together with intermediate arm argmax i m ; we assume that the 7.4 -Analysis of UCB-DS Lemma 7.4.1. Let A be a PPT adversary trying to find the cumulative reward R, and let B be a PPT adversary trying to find the sum of rewards of some arm. Let d be some data, cr(.) be the problem of guessing the cumulative reward, and sum(.) be the problem of guessing the sum of rewards of some arm. We have the following statement:

A cr(.) (d) has a non-negligible advantage ⇔ B sum(.) (d) has a non-negligible advantage.

Proof. ⇐ Assume that B can guess the sum of rewards of some arm with probability better than random. Then, A can call B, and hence get the sum of rewards of one arm with probability better than random. From this sum, A can guess a lower bound on the cumulative reward, hence eliminating some possibilities, and thus guessing the cumulative reward with probability better than random.

⇒ If A can guess the cumulative reward with probability better than random, then B can use this cumulative reward as an upper bound on the sum of rewards of some arm, thus having a probability better than random of guessing the sum of rewards of some arm.

Security of AS.

By construction of UCB-DS, AS knows the arm pulled at each round. We state that AS cannot learn the sum of rewards produced by some arm. Theorem 7.4.1. For an arm i ∈ K and a round t ∈ N -K + 1 , an honestbut-curious AS cannot learn s i,t , given data t AS , with a probability better than random. More precisely, for all PPT adversaries A,

Pr (i, ŝi,t ) ← A sum(t) (data t AS ); ŝi,t = s i,t -p S (n i,t , s i,t )
is negligible in λ, where A sum(t) (data t AS ) returns (i, ŝi,t ) in which ŝi,t is A's guess on s i,t for the arm i (chosen by A), and p S (n i,t , s i,t ) is the probability of obtaining a sum of rewards s i,t from n i,t pulls of arm i until round t.

Proof. Before Step 5 of UCB-DS, AS has access at each round to the indices of the pulled arms. Thus, AS knows n i,t i.e., the number of times the arm i has been pulled until round t. The set of all possible sums of rewards for arm i until round t is {0, 1, . . . , n i,t }. We denote by p S (n i,t , s i,t ) the probability of obtaining the sum of rewards s i,t from n i,t pulls of arm i until round t. Next, we show that the advantage of AS based of data t AS is p S (n i,t , s i,t ) plus an amount negligible in λ. Since AS has no knowledge on µ i , the property stated in the theorem is respected at each round before Step 5, i.e., for all t < N -K + 1.

We next prove the property for the last round i.e., t = N -K + 1. At the end of UCB-DS, at Step 5, AS receives the values E U (s 1,t ), . . . , E U (s K,t ). We prove that retrieving any information about any s i,t from these ciphertexts breaks the IND-CPA property of Paillier's cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. At this point of UCB-DS, data t AS consists of E U (s 1,t ), . . . , E U (s K,t ) and the list of arms that have been pulled at each round. Assume there exists a PPT adversary A able, from data t AS to find s i,t for some i with non negligible advantage x:

Pr (i, ŝi,t ) ← A sum(t) (data t AS ); ŝi,t = s i,t -p S (n i,t , s i,t ) = x + negl(λ).
In the worst case, each i ∈ K has an equal probability of being chosen by A. We also assume that if data

sum(t) ([E U (m b ), E U (s ′ 2,t ), . . . , E U (s ′ K,t ), L]
). The strategy of B is as follows: if A returns (1, m 1 ), then B answers 1. Otherwise, B answers randomly. We next derive the probability of a correct answer by B.

• If i ̸ = 1 (probability 1 -1 K ), then B answers randomly and is correct with probability 1 2 . Hence this branch offers a probability of success of (1 -1 K ) 1 2 .

• If i = 1 (probability 1 K ), let us consider the value of b.

-If b = 0 (probability Hence, B has an advantage of x 4K in the IND-CPA game, which is non negligible. This is a contradiction with the fact that Paillier is IND-CPA secure. Consequently, there does not exist any PPT adversary A that violates the property stated in the theorem.

As a corollary, by Lemma 7.4.1 and Theorem 7.4.1, we infer that AS cannot learn the cumulative reward with probability better than random.

Security of R i . By construction of UCB-DS, each arm node R i knows its sum of rewards. Moreover, due to the properties of the ring computation, R i knows with average probability 1 2 + 1 2K the arm to be pulled at the next round (Theorem 7.4.2), but it cannot learn the sum of rewards of any other arm (Theorem 7.4.3). Theorem 7.4.2. At the end of round t ∈ N -K and before the start of round t + 1, given data t R i , the average probability that an honest-but-curious R i guesses the arm to be pulled at round t + 1 is 1 2 + 1 2K . Proof. After round t, an arm i can either guess randomly (with a success probability of 1 K ), or use the data to which it has access: the partial max B m , the partial argmax index i m , and the next arm in the ring communication. The knowledge of the next arm is useless, as it does not bring any information about any B value. Similarly, the knowledge of B m does not leak more information than i m . Hence, the only useful piece is i m . Based on this only useful piece of data and on the assumption cf. Section 7.4.2 that any information derived from partial argmax data from the previous rounds is negligible, we infer that the best policy for the arm is to bet that arm i m is the arm to be pulled at the next round. Let us consider an arm at position σ -1 (i), where σ is the ring permutation used at the round t. Its guess is correct if and only if the next arm to be selected, say j, has position σ -1 (j) ≤ σ -1 (i). Hence, the arm at position σ -1 (i) has a success probability of σ -1 (i) K . On average, an arm has a success probability of

1 K K i=1 σ -1 (i) K = 1 K 2 K(K + 1) 2 = K + 1 2K = 1 2 + 1 2K
which concludes the proof.

-Analysis of UCB-DS

Hypothesis 2. We assume that the messages exchanged by the nodes during the protocol are uniformly random among possible messages, or at least that, with overwhelming confidence, they are not related to the secret keys of the encryption schemes.

This hypothesis is required, because specific messages such as key-dependant messages [START_REF] Black | Encryption-Scheme Security in the Presence of Key-Dependent Messages[END_REF] can alter the security of the protocol. For instance, it is known that IND-CPA does not imply circular security [START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF] (which states that, for a collection of encryption algorithms E i or secret key sk i , it is impossible to distinguish the encryptions E i (sk i+1 ) from encryptions of 0. Especially, [START_REF] Cash | New Definitions and Separations for Circular Security[END_REF] shows that there exists IND-CPA schemes in which circular encryption leads to a complete breakup (key recovery) of both schemes.

However, if we assume that messages are random, then key-related messages become a negligible event, and as such, all the related weaknesses vanish. Theorem 7.4.7. For an arm i ∈ K and a round t ∈ N -K + 1 , an honest-butcurious external observer cannot learn s i,t , given data t ext , with a probability better than random. More precisely, for all PPT adversaries A, Pr (i, ŝi,t ) ← A sum(t) (data t ext ); ŝi,t = s i,tp Q (t, s i,t ) is negligible in λ, where A sum(t) (data t ext ) returns (i, ŝi,t ) in which ŝi,t is A's guess on s i,t for the arm i (chosen by A), and p Q (t, s i,t ) is the probability of obtaining a sum of rewards s i,t from at most t pulls of arm i until round t.

Proof. The external observer collects data t ext , which consists of several encrypted messages, some of them being encrypted with Enc (AES-CBC) and some other being encrypted with E U (Paillier). We prove that these messages do not provide an advantage bigger than the advantage of an adversary in a classical IND-CPA game on Enc or E U . For simplicity, we assume that the data t ext only contains two encrypted messages, Enc(m) and E U (n). The proof can naturally be adapted if data t ext consists of more than two messages.

The goal of the adversary is to extract at least a bit of information from either m or n, with probability better than random. The entropy of this system is minimal when m = n. Hence, when m = n, the adversary has the highest probability of guessing at least a bit from either m or n (which are the same in this case). As a consequence, in the general case, the advantage of an adversary having to guess a bit about m or n, knowing Enc(m) or E U (n) is bounded above by the advantage of an adversary having to guess a bit about m, knowing Enc(m) and E U (m).

Let us prove that the advantage of a PPT adversary in this latter case (having to guess a bit about m from Enc(m) and E U (m)) is negligible.

We assume, toward a contradiction, that there exists a PPT adversary A able to win the game where, given Enc(m) and E U (m), A recovers a bit of information about m with a non-negligible advantage x: given Enc(m) and E U (m), the probability that A outputs a correct guess about a bit of m is equal to 1 2 + x + negl(λ). • If b = 0 (happens with probability 1 2 ), then A has a non negligible advantage in guessing a bit about m.

-A outputs a correct guess about one bit of m 0 with probability 1 2 + x + negl(λ). In this case, B is correct. This branch happens with probability Hence, B has a non-negligible advantage of 1 4 x in the IND-CPA game against Enc (or E U , respectively), which is a contradiction with its IND-CPA property. Guessing a bit about the encrypted message is equivalent to guessing the reward with a probability better than random (i.e., better than p Q (t, s i,t ) cf. our theorem statement), which concludes our proof.

As a corollary, by Lemma 7.4.1 and Theorem 7.4.7, we infer that the external observer cannot learn the cumulative reward with probability better than random.

Impact of collusions.

As pointed out earlier, an hypothesis behind our security theorems is that cloud nodes do not collude. By collusion we mean that cloud nodes put together all their data. If at least 2 of the R i nodes collude, they could learn their respective algorithm inputs (i.e., bandit arm values that only the data owner is supposed to know at the same time) and outputs (i.e., cloud nodes could sum up the partial sums of rewards known by each node), hence UCB-DS would not satisfy the desirable security properties. In addition to following a standard security model (cf. discussion in Section 7.3.1), we believe that the no-collusion hypothesis is necessary if we want a secure cumulative reward maximization algorithm that produces exactly the same output as standard UCB, which manipulates real numbers i.e., B i needs average, ln, and sqrt. Indeed, as already mentioned in the introduction, it is not currently possible in practice to use fully-homomorphic encryption on real numbers without result approximation. Hence, to minimize data leakage, our choice is to do computations on real numbers in clear, and to distribute reward functions and B i -value computations among K cloud nodes (one per arm), each of them having access in clear only to data pertaining to its arm.

Complexity

We detail in Table 7.3 the number of cryptographic operations used in each step of UCB-DS. By summing up, we obtain O(N K) AES-CBC encryptions/decryptions, K Paillier encryptions, and one Paillier decryption. Hence, we have a number of AES-CBC operations linear in N , whereas the number of Paillier operations does not depend on N . These are desirable complexity properties. In particular, the number of Paillier operations (which are quite slow to evaluate in practice) depends only on K that is typically much smaller than N in bandit scenarios.

Our implementation follows the aforementioned theoretical analysis and confirms the linear time behaviour and the scalability of UCB-DS. We include details on our proof-of-concept experimental study, following synthetic [GUK18; TD16] and realworld scenarios [KSS13; GRG+01; HK15].

Refinement: UCB-DS2

We propose next the UCB-DS2 refinement, which adds slightly stronger security guarantees to UCB-DS, for few more cryptographic operations. A property of UCB-DS, stated in Theorem 7.4.2, is that an arm node R i knows with average probability of 1 2 + 1 2K what arm is pulled at the next round. This happens because during the ring computation, every arm sees in clear the partial argmax i m . We propose the UCB-DS2 refinement of UCB-DS, which removes the aforementioned leakage and hence allows relaxing the second hypothesis from Section 7.4.2.

The idea of UCB-DS2 is that, in addition to UCB-DS, we also encrypt the partial argmax i m during the ring computation. This modification is not trivial as we need to introduce new keys, as detailed next. More precisely, we recall that UCB-DS assumes an AES-CBC key that is shared between the data owner and all cloud participants and that is used for the functions Enc/Dec used until now in the chapter. For UCB-DS2, if we want that an arm node R i cannot decrypt the partial argmax i m received from the previous arm node in the ring, we need to encrypt i m with some other key. This is why in UCB-DS2 we introduce K new AES-CBC keys, each of them shared between AS and a single R i arm node. Each such key defines functions Enc i /Dec i . (N , K, µ) used in the related work, that we adapt for our scalability experiments, as we detail next.

Scalability with respect to N . In this experiment, we fix K and µ, and we vary N . To fix K and µ, we rely on six scenarios from the related work, as detailed in Figure 7.3, where we show the comparison of the four algorithms for these scenarios. We vary N from 10 2 to 10 5 that is also the maximum budget considered in [START_REF] Gajane | Corrupt Bandits for Preserving Local Privacy[END_REF][START_REF] Aristide | Algorithms for Differentially Private Multi-Armed Bandits[END_REF]. The running times for UCB and UCB-D are very close, and up to two orders of magnitude smaller than the times of UCB-DS and UCB-DS2, which are also very close. All algorithms have a similar linear time behavior. The overhead between the secure and non-secure algorithms comes naturally from the cryptographic primitives. Moreover, the two lines corresponding to the secure algorithms are not parallel with the other two lines because, cf. Section 7.4.3, the overhead due to Paillier encryptions depends only on K (that is fixed in the figure) and not on N (that varies in the figure), hence the Paillier overhead is more visible for small N . The running times of UCB-DS/UCB-DS2 for the largest considered budget N = 10 5 is of ∼100 seconds, which remains practical. In Figure 7.3, we also zoom on the time taken by each participant of UCB-DS for N = 10 5 . We observe that AS takes the lion's share, which is expected because at each round AS sends encrypted messages to all R i participants, whereas each R i sends an encrypted message only to one other participant. As expected, all R i take roughly the same time. which is a desirable property because we require them to do as few computations as possible, whereas the bulk of the computation is outsourced to the cloud.

Scalability with respect to K. In this experiment, we fix N = 10 5 , and we vary K ∈ [5,10,[START_REF] Fu | Design Tradeoffs for Data Deduplication Performance in Backup Workloads[END_REF], 20] and implicitly µ with µ 1 = 0.9 and all other µ 2≤i≤K = 0.8. We present results in Figure 7.4, where we observe, as in the previous experiment, a similar linear time behavior and a similar zoom on the time taken by each participant.

Real-world data. In addition to the two aforementioned scalability experiments on synthetic data, we think it is important to also stress test our algorithms on some real-world data. For this experiment, we use the same data and experimental setup as [START_REF] Kohli | A Fast Bandit Algorithm for Recommendations to Users with Heterogeneous Tastes[END_REF]. More precisely, we use data from Jester4 [GRG+01], a collection of ratings ranging from -10 (very not funny) to 10 (very funny), given by 25K users on 100 jokes. Exactly as [START_REF] Kohli | A Fast Bandit Algorithm for Recommendations to Users with Heterogeneous Tastes[END_REF], we pre-process this dataset by assigning the lowest score to the unrated jokes, and then we extract two bandit scenarios:

• Jester-small: K = 10, corresponding to the 10 most rated jokes, where µ i = (# of ratings ≥ threshold 3.5 for joke i) / (# of users).

• Jester-large: K = 100, corresponding to all 100 jokes, where µ i is computed similarly as for Jester-small, except that the threshold here is set to 7.

Moreover, we use data from MovieLens5 [HK15], more precisely the "MovieLens 100K Dataset" that contains ratings ranging from 1 (bad) to 5 (very good) given by 1K users on a set movies, from which, exactly as [START_REF] Kohli | A Fast Bandit Algorithm for Recommendations to Users with Heterogeneous Tastes[END_REF], we look only at the first 100 movies and derive the following bandit scenario:

• MovieLens: K = 100, corresponding to the first 100 movies, where µ i = (# of ratings ≥ threshold 4 for movie i) / (# of users).

We ran each of the three aforementioned scenarios with budget N = 10 5 , which is the largest budget considered in [START_REF] Kohli | A Fast Bandit Algorithm for Recommendations to Users with Heterogeneous Tastes[END_REF]. We show results in Figure 7.5, which essentially confirms the behavior observed in the synthetic experiments i.e., there are roughly two orders of magnitude between non-secure and secure algorithms. In the largest considered scenarios (Jester-large and MovieLens, both with K = 100), where standard UCB takes around twenty seconds, both UCB-DS and UCB-DS2 take around one thousand seconds, that we believe acceptable as waiting time for the user before getting the cumulative reward result for which she pays.

Conclusions and Future Work

We tackled the problem of cumulative reward maximization in multi-armed bandits in a setting where data and computations are outsourced to some honest-but-curious cloud. We proposed UCB-DS, a distributed and secure protocol based on UCB, which yields exactly the same cumulative reward as UCB while enjoying desirable security properties that we precisely characterize. In particular, no cloud node or external observer can learn the cumulative reward, which can be seen only by the user who pays a budget. We rely on distribution of tasks and on cryptographic schemes to achieve the security properties of UCB-DS, and we characterize the overhead of cryptography from both theoretical and empirical points of view. Our experiments show the scalability and practical feasibility of UCB-DS, and of its refinement UCB-DS2.

As future work, we plan to extend our scenario such that multiple users can concurrently submit budgets to the cloud and receive in return corresponding learned cumulative rewards. Such a scenario would imply heavier computations. We believe that the different tasks of our secure distributed algorithms could be pipelined among cloud nodes in order to increase the system's throughput. We also plan to develop protocols for adding security guarantees to other types of bandit algorithms (such as contextual and linear bandits), and more in general, for other learning settings.

Conclusion

The aim of this thesis was to fill in some gaps between theoretical cryptography and everyday software, by proposing new applications of existing cryptographic primitives with guarantees on the security properties, so that the user can confidently know what they are doing and how secure the framework they are using actually is. In this context, we have taken a look on a special topic of computing, namely duplicate detection, and started by improving the current state, and comparing our solution to an optimal bound we derived. After that, we compared our solutions to the state of the art, and showed a net improvement of our solution. After that, we drove into a general study of the security of each filter, in the context where an adversary only has access to the filter's output (and not its internal state). These results help understanding how filters may behave in adversarial context, and if they are efficient enough for the use case (for instance, some applications require very low false positive when others require very low false negative, when both low error rates usually cannot be obtained). As such, we have opened a new field of study on the optimization of such filters in adversarial settings.

Then, we took a look into blockchain and tried to formalize one of its properties, namely interoperability. We acknowledge that blockchain interoperability was already reached before the writing of our paper, thus our work only focuses on the formal definition of what interoperability is, and how it can be studied on blockchain. For this, we created a formal framework for studying blockchain, which might be reused for other purposes.

Finally, we proposed new exchange protocols for decentralizing machine learning algorithms. In this chapter, the idea was to decentralise machine learning algorithms, which might have an elevated computing cost for the user, who might prefer to delegate this computation to a cloud. However, naive implementations would leak data to the cloud nodes, hence our use of cryptographic primitives for securing data exchanges. Furthermore, we quantified the amount of information each node learns, thus formally guaranteeing the security of our schemes.

Contents 1 . 1 1

 111 Goal and Contributions . . . . . . . . . . . . . . . . . Security in Data Streams for Duplicate Detection . . . . . . 2 1.2.2 Applied Security on Blockchain . . . . . . . . . . . . . . . . 3 1.2.3 Security of a Cryptographic Protocol . . . . . . . . . . . . . 4 1.2.4 Other Publications . . . . . . . . . . . . . . . . . . . . . . . 5

Definition 2. 1 . 3 (

 13 False positive (resp. negative)). If, for an unseen (resp. duplicate) element e, Detect(e) outputs DUPLICATE (resp. UNSEEN), e is called a false positive (resp. negative).Definition 2.1.4 (FPR, FNR). The false positive rate (FPR) of a stream E is the frequency of false positive. The false negative rate is similarly defined as the frequency of false negatives.

  A tries to break the security of Π. Definition 2.3.5 (IND-CPA game). Let Π= (KeyGen, Encrypt, Decrypt) be a cryptographic scheme. The IND-CPA game, denoted by EXP(A), works as follows: the adversary A chooses two messages (m 0 , m 1 ) and receives a challenge c = Encrypt(LR b (m 0 , m 1 )) from the challenger who selects a bit b ∈ {0, 1} uniformly at random, and where LR b (m 0 , m 1 ) is equal to m 0 if b=0, and m 1 otherwise.

1 2.

 1 By α = Pr[b ′ ← EXP(A); b = b ′ ], we denote the probability that A correctly outputs her guessed bit b ′ when the bit chosen by the challenger in the experiment is b. Definition 2.3.6 (IND-CPA security). Let Π be a PKE scheme. Let α = Pr[b ′ ← EXP(A); b = b ′ ] be the probability of success of a PPT adversary in an an adversarial game on Π.

Chapter 3 -

 3 Quotient Hash Tables By definition of a conditional probability, P dup,i = P (e i = e) ∩ j>i (e j ̸ = e) ∩ D P [D] = P j>i (e j ̸ = e) ∩ (e i = e) ∩ (∃k ≤ m, e k = e) P [D] = P j>i (e j ̸ = e) ∩ (e i = e) P [D]

Chapter 3 -

 3 Quotient Hash Tables Algorithm 4 Queued Quotient Hash Table with Duplicates' (QQHTD) Stream 1: for each element e ∈ E do 2: result ← UNSEEN 3:

4 : 8 :

 48 for each cell b i in the queue T [h(e)] do5: if (entry in b i ) = f (e) then 6:Pop the first element of the queue T [h(e)] and append f (e) at the end of same queue 9:

Figure 3 . 4 :

 34 Figure 3.4: Error rate (times 100) of filters depending on the filter size, on streams of 10 000 000 elements. Hatched area represents over-optimal (impossible) values, see Section 3.4.2.

Figure 3 . 5 :

 35 Figure 3.5: Error rate (times 100) of filters of 1Mb, depending on the size of the sliding window, on streams of 150M elements. Hatched area represents over-optimal (impossible) values, see Section 3.4.2.

Algorithm 5 SHF

 5 Setup, Lookup and Insert 1: function Setup(M, w) ◃ M is the available memory, w the size of the sliding window 2:

Figure 4 . 1 :

 41 Figure 4.1: Error rates of SHFs and CSHFs for M = 10 5 bits, for varying window sizes w.

Figure 4 . 2 :

 42 Figure 4.2: Error rate (times 100) of DDFs of 1Mb as a function of stream length. Hatched area represents over-optimal (impossible) values, see Section 3.4.2 (page 31).

Figure 4 . 3 :

 43 Figure 4.3: Error rates for QHT, b_DBF, and A2. While A2 and b_DBF were designed and adjusted to the wDDP, this is not the case of QHT. Still, QHT outperforms these filters for some values of w.

Figure 4 . 4 :

 44 Figure 4.4: Architecture of the queuing filter, which consists of L subfilters F i , each containing up to c elements. Once the newest subfilter has inserted c elements in its structure, the oldest one expires. As such, the latter is dropped and a new one is created and put under population at the beginning of the queue. In this example, the sub-sliding window of F 1 is (e m-2 , e m-3 , e m-4 ).

1 :

 1 function Setup(F, M, L, c) ◃ M is the available memory, F the subfilter structure, L the number of subfilters and c the number of insertions per subfilter subfilters.push_first(F.Setup(m)) 7:

4 . 1 )Figure 4 . 5 :

 4145 Figure 4.5: Error rate (times 100) of queuing filters as a function of window size, M = 10 5 , L = 10, |Γ| = 2 18 , on a stream of size 10 7 .

Figure 4 . 6 :

 46 Figure 4.6: Evolution of the error rate of a queueing QHT as a function of L, for several window sizes, with M = 10 5 , |Γ| = 2 18 , on a stream of size 10 6 .

Figure 4 .

 4 7, results for the Cuckoo and SBF are shown in Figure 4.8.

Figure 4 . 7 :

 47 Figure 4.7: Comparing performances of QHT and SQF filters, in 'vanilla' setting or when placed in our queueing structure.

Figure 4 . 8 :

 48 Figure 4.8: Comparing performances of the Cuckoo and SBF filters, in 'vanilla' setting or when placed in our queueing structure.

Chapter 4 -2 10 3 10 4 10 5 10 6 10 7 10 8 10

 410 Towards Optimality for the wDDP 10

Figure 4 . 9 :

 49 Figure 4.9: Error rate for queueing QHTs (L = 10, M = 10 4 , |Γ| = 2 16 , varying w, QHT of parameters k = 1, s = 3) with streams of size 10 5 to 10 8 .

4. 7 - 8 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10

 7810 Adversarial Resistance of Queueing Filters 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9

Figure 4 . 10 :

 410 Figure 4.10: False positive and false negative curves of the previous graph, see Figure 4.9.

Theorem 5 . 5 . 1 .

 551 A decentralised blockchain A interoperable with a blockchain B is equivalent to a decentralised blockchain C containing both A and B's ledgers. Proof. Let A = (L A , W A , Emit A , Mine A , Consensus A ) and B be two decentralised blockchains, with A being interoperable with B. A being interoperable with B, we have Mine A of the form Mine A (L A , L B , •), and Consensus A of the form Consensus A (A, B, •).

Figure 6 . 1 :

 61 Figure 6.1: System architecture.

Figure 6 .

 6 Figure 6.2: Workflow of the secure algorithm. We use numbers to indicate the order of the steps. The steps annotated with * are repeated for each phase j ∈ {1, K -1}.For the communications BAI → RP j , RP j → BAI, and RP j → Comp, the list concerns all the arms that are still candidates i.e., the set A j .

Chapter 6 -

 6 Secure Best Arm Identification in Multi-Armed Bandits b being randomly chosen, B correctly guesses b with probability 1

Theorem 6 . 3 . 7 .

 637 An external observer, having access to the set M of all the messages exchanged during the protocol, cannot infer anything about the sum of rewards of any arm. More specifically, any such observer is bound by the inequality mentioned in Theorem 6.3.1, with data BAI ≤j being replaced by M .

  If an adversary A breaks the inequality with S and i, then we can break IND-CPA. Let B be the IND-CPA adversary, picking K + 1 messages such that m 0 < m ′ i < m 1 , and a permutation σ. Sending m 0 and m 1 , they receive c b = E(pk, m b ), and 108 6.4 -Experiments

Algorithm 7

 7 Secure SR algorithms 1: function Setup_BAI(N ) ◃ Step 1 ◃ j tracks the round number, sum contains the sum of rewards of each competing arm. Both are stored in BAI state.

14 :

 14 Homomorphically add to sum[arm] the rewards from n j pulls of the arm 15: return σ j (sum) 16: function Round_Comp(σ j (sum)) ◃ Step 4 * 17:

  20: function End_Round_BAI(σ j (sum), x min ) ◃ After Step 4 * , before next round 21:

  Get the only remaining competing arm i * from sum in BAI state26:return E(pk U , i * ) Run time (in seconds) for SR (full lines), and for SR-secured (dashed). Time share during SR-secured execution, for N =400000 and K=5.

Figure 6 . 3 :

 63 Figure 6.3: Experimental results.

  work is joint with Radu Ciucanu, Pascal Lafourcade and Marta Soare. It has been accepted presented at the 19th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom 2020), and published as [CLLP+20].

Figure 7 . 1 )Figure 7 . 1 :

 7171 Figure 7.1: Outsourcing data and computations.

Chapter 7 -

 7 Secure Outsourcing of Multi-Armed Bandits Enc(µ 1 ) (0) Enc(µ K ) (1) N (a) Steps 0 and 1 are done only once at the beginning.

  (c) Steps 5 and 6 are done only once at the end.

Figure 7 . 2 :Algorithm 9

 729 Figure 7.2: Overview of UCB-DS. The dashed rectangle is the cloud.

  We use this adversary to create another adversary B able to break the IND-CPA property of the encryption schemes Enc (or E U , respectively). As usually in the IND-CPA game, B chooses two messages m 0 and m 1 , and sends them to the challenger. Then, B receives the challenge Enc(m b ) (or E U (m b ), respectively), and calls A(Enc(m b ), E U (m 0 )) (or A(Enc(m 0 ), E U (m b )), respectively). If A returns a correct guess about m 0 , then B returns 0. Otherwise, it returns 1.

  on UCB-DS for N=100000 (a) Scenario 1[START_REF] Gajane | Corrupt Bandits for Preserving Local Privacy[END_REF]: K = 10, µ1 = 0.9, µ2 = . . . = µ10 = 0.8. -DS for N=100000 (b) Scenario 2 [GUK18; TD16]: K = 2, µ1 = 0.9, µ2 = 0.6.

  -DS for N=100000 (c) Scenario 3 [GUK18] K = 2 µ1 = 0.9, µ2 = 0.8 on UCB-DS for N=100000 (d) Scenario 4 [GUK18] K = 10: µ1 = 0.9, µ2 = µ3 = µ4 = 0.8, µ5 = µ6 = µ7 = 0.7, µ8 = µ9 = µ10 = 0.6.

Figure 7 . 3 :

 73 Figure 7.3: Scalability with respect to N . In the zoom, we do not show DO (its share is close to 0).

  on UCB-DS for N=100000 (f) Scenario 6 [TD16] K = 10: µ1 = 0.55, µ2 = 0.2, µ3 = . . . = µ10 = 0.1.

Figure 7 . 3 :

 73 Figure 7.3: (cont.) Scalability with respect to N . In the zoom, we do not show DO (its share is close to 0).

Figure 7 . 4 :Figure 7 . 5 :

 7475 Figure 7.4: Scalability with respect to K for fixed N = 10 5 . In the zoom (labels not shown because they would be colliding): the AS takes the lion's share, R 1≤i≤20 take the 20 equal shares, U is barely visible, and DO is not shown since its share is close to 0.

Part I Security in Data Streams for Duplicate Detection Part I Security in Data Streams for Duplicate Detection 3 Quotient Hash Tables Contents 3.1 Introduction and preliminaries . . . . . . . . . . . . . . . . 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .

	1. Paillier is IND-CPA under the decisional composite residuosity assumption [Pai99],
	2. AES-CBC is IND-CPA under the assumption that AES is a pseudo-random
	permutation [BDJ+97].
	3.2.1 Hash-based Filters . . . . . . . . . . . . . . . . . . . . . . .
	3.2.2 Streaming Quotient Filter . . . . . . . . . . . . . . . . . . .
	3

.3 Contributions and Organisation . . . . . . . . . . . . . . . 3.4 Redefining the Problem of Duplicate Detection . . . . . .

	3.4.1 Filter Saturation . . . . . . . . . . . . . . . . . . . . . . . .
	3.4.2 Lower Bound on Saturation . . . . . . . . . . . . . . . . . .

3.5 Revisiting SQF: Quotient Hash Table . . . . . . . . . . . .

	3.5.1 Full-size Hashing, Memory Adjustments . . . . . . . . . . .
	3.5.2 Empty Cells . . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.5.3 Semi-sorting . . . . . . . . . . . . . . . . . . . . . . . . . .
	3.5.4 Comparison with Hash Tables . . . . . . . . . . . . . . . . .

3.6 Error Rate Analysis . . . . . . . . . . . . . . . . . . . . . .

	3.6.1 False Positive Rate . . . . . . . . . . . . . . . . . . . . . . .
	3.6.2 False Negative Rate . . . . . . . . . . . . . . . . . . . . . .
	3.6.3 Comparing QHT to SQF . . . . . . . . . . . . . . . . . . .
	3.6.4 Parameter Tuning . . . . . . . . . . . . . . . . . . . . . . .
	3.

7 Further Improvements: QQHTD . . . . . . . . . . . . . . .

	3.7.1 Keeping Track of Duplicates . . . . . . . . . . . . . . . . . .
	3.7.2 Queuing cells for a Better Sliding Window . . . . . . . . . .
	3.

8 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Chapter 3 -Quotient Hash Tables
	3.8.1 Comparison of QHT and QQHTD . . . . . . . . . . . . . . 48
	3.8.2 Comparison of QHT to Other Filters . . . . . . . . . . . . . 49
	3.8.3 Speed Comparison . . . . . . . . . . . . . . . . . . . . . . . 51
	3.8.4 Saturation Resistance . . . . . . . . . . . . . . . . . . . . . 52
	3.8.5 Memory Impact . . . . . . . . . . . . . . . . . . . . . . . . 53
	3.8.6 Influence of the Sliding Window . . . . . . . . . . . . . . . 53
	3

.9 Adversarial Resistance . . . . . . . . . . . . . . . . . . . . . 55 3.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Abstract

	This chapter presents the Quotient Hash Table (QHT) a new data structure for
	duplicate detection in unbounded streams. QHTs stem from a corrected analysis
	of streaming quotient filters (SQFs), resulting in a 33% reduction in memory usage
	for equal performance. With the same memory amount, QHT reduce by up to 7.7
	points of percentage the error rate (about 13% more efficient) when compared to
	SQF. We also introduce an optimised version of our new data structure dubbed
	Queued QHT with Duplicates (QQHTD).

Table 3 .

 3

	16 S = 32 S = 64

1: Error rates of QHTs with the same asymptotic FPR. The QHT with both better FPR and FNR is in bold.

Table 3 .

 3 2: Error rate (times 100) of QHTs of 1 Mb memory, k = 1 and various S size, for different sliding windows, on an artificial stream. The minimum value for each sliding window is in bold.

	3.7 -Further Improvements: QQHTD

Table 3 .

 3 3: Error rate (times 100) of QHTs and QQHTDs with the same parameters on different streams, depending on their parameters k and S. The best behaving filter for each run is in bold.

	64

Table 3 .

 3

	.4) shows that even

5: Error rate (multiplied by 100) on real and artificial streams of 150,000,000 elements. For each stream, the most efficient result is in bold.

though their FPR is close to 0, they get an FNR close to 1. Moreover, as we see in Section 3.8.3, they are significantly slower, which can be a bottleneck for critical applications. Further more, not only are QHT/QQHTD the most efficient filter on both real and artificial streams, they are also very easily tunable, and any asymptotic FPR rate is very simply achievable. This is not the case of other filters, such as A2 or b_DBF, which require careful tuning.

  Assume that an interoperable transaction t exists. Then there is a set ω B of possible ledger values of B for which a block containing t is accepted byConsensus A , if L B ∈ ω B . Moreover, if L B ∈ Ω B \ω B , then Consensus A will refuse any block containing t.However, Consensus A only takes A, S as arguments, where S is a set of tuples (L i , W i ) (see Definition 5.2.3). As a consequence, Consensus A is independent from B, and especially from L B . Then, if t is accepted by Consensus A when L B ∈ ω B , then t is also accepted by Consensus A when L B ∈ Ω B \ω B ; this implies that Ω B \ω B = ∅, i.e., ω B = Ω B , which is a contradiction with the hypothesis of Definition 5.2.5, namely that ω B is a proper subset of Ω B .

	Theorem 5.3.1. Under the Definitions 5.2.3 and 5.2.5, blockchain interoperability
	is impossible.
	Proof.

  5.5 -Equivalence of Interoperable Blockchains with a Single Blockchain Definition 5.5.1 (Blockchain equivalence). Let there be two blockchains A = (L A , W A , Emit A , Mine A ) and B = (L B , W B , Emit B , Mine B ) accepting transactions from T A and T B , respectively. A and B are said to be equivalent if there exists a bijection φ : T A → T B such that, if both ledgers are equivalent, then there is an equivalence of the valid transactions. In mathematical terms, φ(L

  Mine C is a parallelisation of Mine A and Mine B : a block proposed by Mine C is a block comprised of the transactions accepted by Mine A and Mine B .Similarly, Consensus C is built as a parallelisation of Consensus A and Consensus B

6.3 Security Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 102 6

  .3.1 Notations and Security Hypothesis . . . . . . . . . . . . . . 6.3.2 Security Proofs for BAI . . . . . . . . . . . . . . . . . . . . 6.3.3 Security Proofs for Comp . . . . . . . . . . . . . . . . . . . 6.3.4 Security Proofs for the RP j . . . . . . . . . . . . . . . . . . 6.3.5 Security Proof for an External Observer . . . . . . . . . . . 6.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Run time comparison SR vs SR-secured . . . . . . . . . . . 6.4.3 Zoom on SR-secured . . . . . . . . . . . . . . . . . . . . . . 6.

	6
	Secure Best Arm Identification in
	Multi-Armed Bandits

Contents 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.

1 Use Case Example . . . . . . . . . . . . . . . . . . . . . . . 6.1.2 Summary of Contributions and Chapter Organization . . . 6.2 Secure Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Security Model . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Security Background . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Secure Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 6.2.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.6 Conclusions and Future Work . . . . . . . . . . . . . . . . 111

  Chapter 6 -Secure Best Arm Identification in Multi-Armed Bandits

  (sum), E(pk RP j , σ j ), n j 11: function Round_RP j (σ j (sum), E(pk RP j , σ j ), n j ) ◃ Step 3

	9:	save σ j in BAI state
	10:	return σ j

*

12:

Table 7 .

 7 to solve it. However, 1: Summary of related work and positioning of our contribution.

		Differential privacy	Cryptography
	Cumulative reward maximization a.k.a. minimization cumulative regret	Gajane et al. [GUK18] Tossou, Dimitrakakis [TD16] Mishra, Thakurta [MT15]	This work
	Best arm identification a.k.a. simple regret minimization	Not yet studied to the best of our knowledge	Ciucanu et al. [CLLP+19]

  t AS does not correspond to the data collected by AS during a run of UCB-DS (for instance, if one piece of data t AS has been replaced by another unrelated message), then A does not give any advantage. If such an adversary A exists, then we show how to construct an adversary B able to break the IND-CPA property of Paillier. Let us build an IND-CPA game, in which B chooses two values m 0 , m 1 , and sends them to the challenger. The challenger randomly selects b ∈ {0, 1} and answers with E U (m b ). B wins the IND-CPA game if B guesses b with a non-negligible advantage.To do so, B first creates a simulation of an UCB-DS execution i.e., B creates nodes U ′ , AS ′ , R ′ i , and DO ′ , with Bernoulli distributions defined by µ ′ i of its choice. Then, B runs an execution of UCB-DS on these nodes. Because B controls all the nodes, it knows the sums of rewards s ′ 1,t , . . . , s ′ K,t , as well as a list L of arms pulled at each round.

As input for the IND-CPA game, B chooses m 1 = s ′ 1,t and another value m 0 , different from all s ′ i,t , sends both values to the challenger, and receives E U (m b ). Then, B computes E U (s ′ i,t ) for each i, and calls A

  1 2 ), then we have two cases: * If the output of A is (1, m 1 ) (probability p S (n 1,t , s 1,t )), then B answers 1 and it is wrong, hence the probability of success is 0. * Otherwise (probability 1p S (n 1,t , s 1,t )), B answers randomly and is correct with probability 1 2 . The probability of success of this branch is1 p S (n 1,t , s 1,t )) 1 2 . -If b = 1 (probability 12 ), then we have two cases: * If the output of A is (1, m 1 ) (probability p S (n 1,t , s 1,t ) + x + negl(λ)), then B correctly answers 1. The probability of success of this branch is 1 S (n 1,t , s 1,t ) + x + negl(λ)). * Otherwise (probability 1p S (n 1,t , s 1,t )x -negl(λ)), B answers randomly and is correct with probability 1 2 . The probability of success of this branch is1 p S (n 1,t , s 1,t )x -negl(λ)) 1 2 . 130 7.4 -Analysis of UCB-DSBy aggregating the aforementioned cases, the probability α of success of B is:

	K 2 (1 K 1 1 2 (p K (1 -p S (n 1,t , s 1,t )) 1 (1 -p S (n 1,t , s 1,t ) -x -negl(λ)) 1 K 1 2 + 1 K 1 2 1 2 1 2 1 2K K 1 -+ 1 2 + 1 4K -p S (n 1,t , s 1,t ) 4K + p S (n 1,t , s 1,t ) + 1 K 1 2 1 2 2K + (p S (n 1,t , s 1,t ) + x + negl(λ)) x 2K + 1 4K -p S (n 1,t , s 1,t ) 4K -x 4K + negl(λ) 2 (1 α = 1 -= = 1 2 + x 4K + negl(λ)

  If A does not answer correctly (happens with probability 1 2x -negl(λ)), then B is correct with probability 1 2 . This branch happens with probabil-ity 1 2 ( 1 2x -negl(λ)) 1 2 . • If b = 1 (happens with probability 12 ), then A has no advantage. -If A returns a correct guess about one bit of m 0 (happens with probability 1 2 ), then B is wrong.-If not (happens with probability 1 2 ), then B returns a random guess and is correct with probability 1 2 . This branch of events happen with probability

	1 2 ( 1 2 + x + negl(λ)).
	-1 2 3 .
	α =	1 2	(	1 2	+ x + negl(λ)) +	1 2	(	1 2	-x -negl(λ))	1 2	+	1 8
	=	1 4	+	1 2	x +	1 8	-	1 4	x +	1 8	+ negl(λ)
	=	1 2	+	1 4	x + negl(λ)

By aggregating these cases, the probability α of success of B is:

[START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF] refers to them as "signatures", but we shun this term to avoid any claim of cryptographic properties.

µ can go up to 2 as theoretically, a filter can be always wrong, hence with an error rate of 2.

Even though not mentioned in[START_REF] Dutta | Streaming Quotient Filter: A Near Optimal Approximate Duplicate Detection Approach for Data Streams[END_REF], the approximation (stemming from Catalan numbers) is only asymptotically valid, but computations show that the approximation is satisfying even for small values of r, such as the ones used in practical applications.

https://github.com/efficient/cuckoofilter/blob/aac6569cf30f0dfcf39edec1799fc3f8d6f594da/ src/cuckoofilter.h

If we are on a system without the empty feature (see Section 3.5.2), then S = 2 s -1. For an SQF, one can just assign the empty value to one of the unassigned fingerprints.

https://bitbucket.org/team_qht/qht/src/master

github.com/mariuslp/libqht

Our benchmarks actually obtained an asymptotic FPR of around 28%, without us being able to find bugs in our implementation.

The naïve strategy consisting of storing the w elements of the sliding window, requiring w log

|Γ| bits of memory.

Note that by design, a b_DBF of 10 5 bits cannot operate for w > 6000.

Note that for a real cryptocurrency more checks would be needed for any practical use, notably because of the fact that in the current setting, anyone can withdraw m from 0B as many times as they want. However, for the sake of simplicity, we only describe a simple, naive interoperability operation here, so these checks are omitted.

In case of collusions, if several users spent successive budgets to learn the best arm among the same set of arms, the cloud could compose the observed rewards. Hence the cloud could compute the best arm using as budget the total budget of the users and leak this information to some malicious user.

https://gitlab-sds.insa-cvl.fr/vciucanu/secure-bai-in-mab-public-code

https://python-paillier.readthedocs.io/en/develop/

http://eigentaste.berkeley.edu/dataset/

https://grouplens.org/datasets/movielens/

Remerciements

Chapter 1 -Introduction Chapter 3 -Quotient Hash Tables However, this optimality bound is not tight. Furthermore, it is probable that such an optimal structure will be extremely slow, and as such will require an efficiency/time adjustment. Further work may include research in this area.

Finally, other future research can be directed in the analysis of the error rate of QQHTDs, as well as a finer study of the parameter tuning in the sliding window configuration.

Part II

Applied Security on Blockchain 81

Chapter 5 -About Blockchain Interoperability Abstract A blockchain is designed to be a self-sufficient decentralised ledger: a peer verifying the validity of past transactions only needs to download the blockchain (the ledger) and nothing else. However, it might be of interest to make two different blockchains interoperable, i.e., to allow one to transmit information from one blockchain to another blockchain. In this chapter, we give a formalisation of this problem, and we prove that blockchain interoperability is impossible according to the classical definition of a blockchain. Under a weaker definition of blockchain, we demonstrate that two blockchains are interoperable is equivalent to creating a '2-in-1' blockchain containing both ledgers, thus limiting the theoretical interest of making interoperable blockchains in the first place. We also observe that all practical existing interoperable blockchain frameworks work indeed by exchanging already created tokens between two blockchains and not by offering the possibility to transfer tokens from one blockchain to another one, which implies a modification of the balance of total created tokens on both blockchains. It confirms that having interoperability is only possible by creating a '2-in-1' blockchain containing both ledgers.

This work is joint with Pascal Lafourcade and has been published in Information Processing Letters Volume 161, September 2020, as [START_REF] Lafourcade | About blockchain interoperability[END_REF].

Introduction

Blockchain was first introduced in 2008 by Nakamoto in [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. In their paper, the anonymous author(s) described the first decentralised ledger: a database in which anyone can write, and that is not controlled by a single or a conglomerate of identities. Since then, many other blockchains have been described: Ethereum [START_REF] Vitalik Buterin | Ethereum: A next-generation smart contract and decentralized application platform[END_REF], Ripple [START_REF] Schwartz | The Ripple Protocol Consensus Algorithm[END_REF] and many others. In May 2019, 248 active blockchains were listed on [START_REF]Crypto-currency blockchain explorers[END_REF].

While many different blockchains exist, there is no direct way of reaching interoperability, at least without a trusted third party. Consider for instance a client willing to convert their Bitcoins to Ether: they would need to consume the amount of Bitcoins they wants to convert and to generate the equivalent amount of Ether. While Bitcoin consumption may be reachable (by sending coins to a non-existing address, such as the address 0), it is impossible to spontaneously generate Ether (or any other kind of cryptocurrency). For now, the problem is solved with the help of trusted brokers (also called escrows), even though other solutions are on their way [START_REF] Johnson | Sidechains and interoperability[END_REF][START_REF] Thomas | A Protocol for Interledger Payments[END_REF].

The issue of interoperability is solved in some cases, like "atomic exchanges" and hash-locking [START_REF] Vitalik Buterin | Chain Interoperability[END_REF], in which game theory ensures that a broker only benefits when following the protocol. However the question of trustless interoperability in the general context remains open.

Contributions. We introduce a theoretical background to blockchain interoperability, providing a formal definition of a blockchain and of interoperability. We then prove that, by definition, interoperability between two public blockchains is

-Interoperability with a Weaker Definition

This result is actually quite straightforward if we remember that a blockchain is, by construction, made to be self-sufficient: no blockchain can rely on external data. Especially, no blockchain can rely on another blockchain for asserting the validity of a transaction. Hence, interoperability is a contradiction of one of the intrinsic characteristics of blockchain.

The interpretation of the result is as follows: without additional assumptions, interoperability between two blockchains is impossible. Therefore, to achieve interoperability further assumptions need to be made. For instance, in the two-way pegged blockchain mechanism, a dispute period is required for each interoperabilty operation; as the blockchain cannot know by itself whether the proposed SPV proof is the one of the latest block.

Interoperability with a Weaker Definition

Even though blockchain is not suited for interoperability stricto sensu, we can generalise our blockchain definition, in order to make a blockchain interoperable.

Hypothesis 1. We assume that for two blockchains

and B, with A both Mine A and Consensus A have access to both A and B: Consensus A is of the form Consensus A (A, B, S), and Mine

We now use the notation Consensus A (A, B, •) to note the new consensus algorithm. Hence, the 'version' of Consensus in the previous definition, is now noted Consensus A (A, ∅, •). Similarly, the non-interoperable version of Mine is now noted as Mine A (L A , ∅, W A , ∅).

Definition 5.4.1 (Interoperable transaction). Under the assumption Hypothesis 1, a transaction t on the blockchain A is said to be interoperable with B if t can be accepted by Consensus A (A, B, •) but cannot be accepted by Consensus

In this context, we have the following result. Theorem 5.4.1. Under Hypothesis 1, it is possible to build interoperable blockchains.

Proof. Note that we already know that interoperable blockchains exist, such as Kadena [START_REF] Martino | Chainweb Whitepaper[END_REF] or other blockchains listed in [START_REF] Johnson | Sidechains and interoperability[END_REF], but we give an example of interoperable blockchain in our own theoretical framework.

Consider two decentralised blockchains A = (L A , W A , Emit A , Mine A , Consensus A ) and B. On the blockchains we define accounts. An account ownership is defined by the knowledge of a private key, and for simplicity the public key is assimilated to the account itself. A transaction t ∈ T A (resp. T B ) specifies the sender's public key, the receiver's public key, an amount and a signature of the previous fields by the sender's private key. An account i on blockchain A (resp. B) is designed by i A (resp i B ).

Part III

Security of a Cryptographic Protocol

-Secure Protocol

The algorithm, which is summarized in Algorithm 7, consists of:

• Initialization done by BAI is:

-Based on the total budget N , compute n 1 , . . . , n K-1 that is the number of times each of the candidate arms should be pulled at phase 1, . . . , K -1, respectively.

-Uniformly select a permutation σ 1 of K and send E(pk RP 1 , σ 1 ) to RP 1 .

A new permutation σ j on K + 1j is randomly selected at each round, and sent to RP j .

-For each arm i, compute sum[σ 1 (i)] = E(pk Comp , 0).

During the K -1 phases of the algorithm, these encrypted sums are updated by the nodes RP j .

• K -1 phases where nodes BAI, RP j , and Comp interact as shown in Figure 6.2. We add the following specifications:

-Each RP j updates the encrypted sums using the homomorphic addition property of the Paillier's cryptosystem: for a round j and a candidate arm i with sum sum[σ j (i)], we get the updated sum sum ′ [σ j (i)] by homomor-

where k l is uniformly selected in [-ϵ, ϵ] by RP j .

-When Comp computes the index of the worst arm, if two or more arms have the same worst sum of rewards, then Comp selects uniformly at random one of these arms as the worst one. This ensures that the index of the worst arm has a uniform distribution.

We summarize in Table 6.1 what each cloud node knows and does not know, in order to satisfy the desired security properties. We formally prove the security properties in Section 6.3. Next, we briefly outline why we need so many nodes:

• Assuming that all RP j nodes are a single one, this node would know all rewards since the beginning of the algorithm hence it would learn the ranking of the arms.

• Assuming that Comp and RP j are the same, then it would leak which arm is associated to which sum, hence the best arm could be leaked.

• Assuming that Comp and BAI are the same, then BAI would learn the plain rewards in addition to the ranking that it already knows.

• Assuming that BAI and RP j are the same, then it would leak to BAI the sum of rewards associated to each arm.

-Security Proofs

the first property from Section 6.3.2 to Section 6.3.4, and the second property in Section 6.3.5.

Notations and Security Hypothesis

For a node A, we note data A the data to which A has access and A pb (d) the answer of a Probabilistic Polynomial-Time (PPT) adversary A having knowledge of d, trying to solve the problem pb. We recall that, in our notation conventions, K denotes the set of positive integers lower than or equal to K: K = {1, . . . , K}.

Lemma 6.3.1. For a list l = [l 1 , . . . , l n ], a permutation σ and the permuted list σ(l) = [l σ(1) , . . . , l σ(n) ], a PPT adversary A(l σ ) cannot invert one element with probability better than random. More specifically,

where A returns a tuple (i, g(i)) and g(i) is A's guess for the preimage of i.

Proof. This is immediate, as all preimages are equally likely if σ is uniformly selected.

Proof. Assume there is a PPT adversary A able to win the game with significant advantage x + negl(λ): then A can guess b with probability 1 2 + x 2 + negl(λ). We then prove that an PPT adversary B can break the IND-CPA property of Paillier. We can assume that when A is given c 0 , c ′ 0 , s as input (where c ′ 0 is another encryption of m 0 ), then the advantage of A is negligible: this gives us a lower bound of the advantage of A in a more general adversarial game.

Let If b = 0, then B has actually called A(c ′ 0 , c 0 , s), which guesses the correct b * with probability 1 2 + negl(λ). On the other hand, if b = 1, then B has actually called A(c ′ 0 , c 1 , s), which gives the correct b * with probability 1 2 + x 2 + negl(λ).

-Security Proofs

• i = 1, b = 0, A does not return ŝum 1 , and B makes a correct random guess. This happens with probability

• i ̸ = 1 and B makes a correct random guess. This happens with probability

Summing it up, B makes a correct guess with probability

x , which yields an advantage of From the data obtained up to round j, a honest-but-curious BAI does not know the sum of the rewards of any arm. More precisely, for R the set of possible rewards,

where the data data BAI ≤j is the data obtained by BAI during the first j rounds and reward(i) is the reward of the i-th arm.

Proof. We notice that data BAI ≤j is equal to

We know that each ciphertext from se j+1 results from the homomorphic addition of one ciphertext from se j and one other unknown ciphertext 2 . Given Lemma 6.3.2, the set [se j , se j+1 ] is indistinguishable from the set [se j , se ′ j+1 ] where se ′ j+1 is a list of ciphertexts, unrelated to the ones in se j . Hence, data BAI ≤j is indistinguishable from the list [se 1 , se ′ 2 , . . . , se ′ j , i min 1 , . . . , i min j ], where se ′ i is a list of ciphertexts unrelated to se ′ j or se 1 . Assume that there exists a PPT adversary A able to break the above inequality, with an advantage of x + negl(λ). The data available to A basically consists of j iterations, of various sizes, of the problem addressed in Lemma 6.3.3. Then, if A can solve our current adversarial game with non negligible advantage, A can immediately solve the problem in Lemma 6.3.3 with non negligible advantage (from one set of ciphertexts, A will generate other sets, and immediately places itself in the current problem). Because a non negligible advantage to the above problem breaks IND-CPA security, we conclude to a contradiction.

Security Proofs for Comp

Lemma 6.3.4. Let j ∈ K -1 . From the data received at the round j, a honestbut-curious Comp cannot infer the ranking of any arm. More specifically,

2 Namely, the ciphertext of the rewards of the arm i at round j.

Proof. We have data

which can be decrypted by Comp to s σ j = [sum σ j (α 1 ) , . . . , sum σ j (α K+1-j ) ] where the α i are the arms still present at round j. From this list of scores, Comp can infer the ranking of the permuted arms, i.e., compute the ranking any A σ j (i) in polynomial time.

Assume there exists a PPT adversary A rank capable of breaking the above equality. If A is able to predict the ranking of the arm i with advantage better than random, then A knows the ranking of A i , namely ranking(A i ). Knowing the ranking of all A σ j (i) , with probability better than random, A is then able to compute σ -1 j (i) with advantage better than random by identifying which A σ j (i) matches A i . Hence a contradiction with Lemma 6.3.1. Theorem 6.3.2. Let j ∈ K -1 . From the data received until the round j, A honest-but-curious Comp cannot infer the ranking of any arm. More specifically,

Proof. The proof is based on the proof of Lemma 6.3.4, with additional arguments similar to the ones of the proof of Theorem 6.3.1: because of Lemma 6.3.2, we can assume that we have j independent sets of unrelated permuted data. If an adversary A can break the above equality with non-negligible advantage in PPT, then we can construct an adversary who breaks the equality of Lemma 6.3.4 with non-negligible advantage, in PPT, which breaks Lemma 6.3.1, so we get a contradiction. Lemma 6.3.5. Let j ∈ K -1 . From the data received at round j, a honest-butcurious Comp does not know the correspondence between sums of rewards and arms. More specifically,

Assume that Comp is able, from s σ j , to infer the sum of rewards of the arm A k with probability better than 1 K+1-j . Because Comp knows the sum of rewards of the permuted arms A σ j (α i ) for all i ∈ K + 1j , then by matching these rewards with the sum of the rewards of A i , Comp is able to compute σ j (i) with a probability better than random. Hence, Comp breaks Lemma 6.3.1. Theorem 6.3.3. Let j ∈ K -1 . From the data received until round j, a honestbut-curious Comp does not know the correspondence between sums of rewards and arms. More specifically,

Proof. Similar to the proof of Theorem 6.3.2.

Security Proofs for the RP j

Theorem 6.3.4. A honest-but-curious RP j does not know the ranking of the K-j+1 best ranking arms, for j ∈ K -1 . More specifically, ∀j ∈ K -1 , ∀i ∈ K + 1j , and ranking j (i) is the ranking of the i-th arm at round j,

where se

), the permuted list of encrypted sums of rewards. RP j can further 'un-permute' se σ j to se = [E(pk Comp , sum α 1 ), . . . , E(pk Comp , sum α K-j )], the list of encrypted sums of rewards. Note that n j does not carry any information about the partial sum, as one can simulate any se with the same n j , so does not carry significant information to our problem. Assume that RP j can guess the ranking of one element with advantage x+negl(λ): there exist a PPT oracle A taking as input se, and outputs (i, v(i)), with i ∈ K +1j . Furthermore, we have v(i) = ranking j (i) with probability 1 K+1-j + x + negl(λ). Note that, on average, i = 1 with probability 1 K+1-j . Let us consider an IND-CPA game, in which the strategy of B is the same as the one in the proof of Lemma 6.3.3 (i.e., simulate a blind bandit execution, and call A with the relevant data). Then, following the same reasoning we get that B wins the IND-CPA game with probability 1

x, hence B has an advantage of 1 4(K+1-j) x + negl(λ), which is a contradiction with the IND-CPA property of Paillier's. Theorem 6.3.5. A honest-but-curious RP j does not know the ranking of the j -1 lowest ranking arms. More specifically, ∀j ∈ {3, . . . , K -1}, ∀i ∈ j -1 , and ranking(i) the ranking of the i-th arm,

Proof. This is straightforward as RP j does not receive any information about the sums of the j lowest ranking arms. Furthermore, we must impose j ≥ 3 because it is clear that RP 1 and RP 2 know the ranking of the lowest ranking arm. Theorem 6.3.6. A honest-but-curious RP j does not know the sums of rewards at step j. More precisely, for R the set of possible rewards, ∀i ∈ K + 1j ,

Proof. Assume that a PPT adversary A breaks the above inequality: there exists a PPT oracle A(c 1 , . . . , c K ), that returns the tuple (i, m i ) where m i is the cleartext Chapter 7 -Secure Outsourcing of Multi-Armed Bandits best arm identification [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF], equivalent to minimizing the simple regret, that is the difference between the values associated with the arm that is actually the best and the best arm identified by the algorithm. To the best of our knowledge, this problem has not yet been studied from a differential-privacy point of view. From the cryptography point of view, there already exists a distributed algorithm [START_REF] Ciucanu | Secure Best Arm Identification in Multi-armed Bandits[END_REF] that enhances the Successive rejects algorithm [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] for best arm identification with security guarantees that are similar to the ones from this chapter. However, the standard algorithms that are secured (Successive rejects [START_REF] Audibert | Best Arm Identification in Multi-Armed Bandits[END_REF] in [START_REF] Ciucanu | Secure Best Arm Identification in Multi-armed Bandits[END_REF] and UCB [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF] in this chapter) solve different problems and the corresponding distributed protocols cannot be reduced to one another.

Summary of contributions and Chapter organization

In Section 7.2, we introduce some basic notions: standard UCB algorithm and some cryptographic tools. Then, Section 7.3 is the core of our contribution:

• We propose UCB-DS, a secure and distributed protocol for cumulative reward maximization that guarantees the same cumulative reward as standard UCB.

• We show that UCB-DS satisfies desirable security properties that we precisely characterize, and prove.

• We analyze the theoretical complexity of UCB-DS, by quantifying the number of needed cryptographic primitives: O(N K) AES-CBC encryptions/decryptions, K Paillier encryptions, and one Paillier decryption.

• We run a proof-of-concept empirical evaluation that confirms the theoretical complexity, and shows the scalability and practical feasibility of our protocols, on synthetic and real-world data.

• We propose the UCB-DS2 refinement, with stronger security guarantees at the price of K more AES-CBC keys and O(N K) more AES-CBC encryptions/decryptions, and the same number of Paillier encryptions/decryptions as UCB-DS.

Finally, we conclude our chapter and outline directions for future work in Section 7.5.

The aforementioned evaluation suggests that it is practical to deploy our protocol on a real cloud and with real users, where parallelism between nodes could be leveraged to improve the system's throughput if multiple users are concurrently submitting budgets. We leave such an extended cloud system empirical evaluation as future work.

Preliminaries

We first recall the UCB algorithm [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF]. Then, we present two cryptographic schemes that we use to build our protocols: Paillier asymmetric encryption scheme 7.3 -UCB-DS: A Distributed and Secure Protocol Based on UCB Algorithm and AES-CBC symmetric encryption scheme. We also recall the notion of IND-CPA security, held by both aforementioned schemes and useful for our security proofs.

Upper Confidence Bound (UCB)

We already defined the UCB algorithm in Section 2.2.3, page 15. We quickly give here a small reminder, that the UCB aims at maximising the cumulative reward sum, while the exact reward given by each machine is unknown and the budget limited.

An algorithm has been proposed by [START_REF] Auer | Finite-Time Analysis of the Multiarmed Bandit Problem[END_REF] which identifies, at each turn, an upper bound of the estimation of reward of each arm. Given this parameter, named B i for each arm i, one can select the next arm in order to maximize the expected total reward.

Paillier and AES cryptosystems

We have already introduced and defined Paillier and AES-CBC cryptosystems in Section 2.3, that the reader may confer to if needed, page 17. We simply mention in this section by pointing out that all theoretical security properties of our protocols also hold if we choose any other IND-CPA symmetric scheme instead of AES-CBC, and any other additive homomorphic IND-CPA asymmetric scheme instead of Paillier. Our choice to rely on the aforementioned schemes is due to practical reasons. AES-CBC is very efficient in practice and implemented in standard libraries for modern programming languages. Paillier is also supported by a number of libraries that can be used in practice. In our protocol, we rely on Paillier whenever we need its additive homomorphic property, and on AES-CBC in all other situations when we need to symmetrically encrypt data.

UCB-DS: A Distributed and Secure Protocol Based on UCB Algorithm

We first define the security model and the desired security properties (Section 7.3.1). Then, we propose our secure protocol UCB-DS (Section 7.3.2), and we analyze its correctness, security, and complexity (Section 7.4). We introduce a refinement of UCB-DS in Section 7.4.4.

Security Model

As outlined in the Introduction and in Figure 7.1, we assume that the data (i.e., the reward functions associated to K bandit arms) and the computations (i.e., the cumulative reward maximization algorithm) are outsourced to an honest-but-curious cloud. This means that the cloud executes tasks dutifully, but tries to extract as much information as possible from the data that it sees. knowledge on intermediate B m and i m by each arm does not leak significant information on the sum of rewards. We show in Section 7.4.4 our refinement UCB-DS2, which hides i m during the ring computation to relax the second hypothesis. Before discussing the security properties for each participant, we introduce some notations needed for the theorem statements:

• n i,t = the number of times arm i has been pulled until round t.

• s i,t = the sum of rewards obtained by arm i until round t.

• data t A = the data to which participant A has access until round t, where A can be a participant from Figure 7.2 or the external observer (ext). If t is omitted, this denotes the data to which A has access at the end of the protocol.

• A pb(.) (d) = the answer of a Probabilistic Polynomial-Time (PPT) adversary A that knows d and tries to solve the problem pb. Depending on the problem, pb can also take some input.

• By negligible in λ, we denote that our security theorems are always asymptotic i.e., they describe the behavior when the security parameter λ of the cryptographic schemes becomes infinitely large. More precisely, a function f : N → R is negligible in λ if for any c ∈ N, and for any λ large enough, f (λ) < λ -c .

We next provide theorems that state each non-trivial property from Table 7.2. We first state an useful lemma, which intuitively says that guessing the cumulative reward with probability better than random is equivalent to guessing the sum of rewards of some arm with probability better than random.

Chapter 7 -Secure Outsourcing of Multi-Armed Bandits

Encryptions Decryptions

AES-CBC

is negligible in λ, where A sum(t) (data t R i ) returns a tuple (j, ŝj,t ) in which j ̸ = i is chosen by A and ŝj,t is A's guess of the sum of rewards for arm j, and p R (n i,t , t, s j,t ) is the probability of arm j to have sum of rewards s j,t at round t seen that arm i has been pulled n i,t times. Proof. If an arm i has been pulled n i,t times until round t, then another arm j has been pulled at most tn i,t times. Hence, a baseline probability of R i to guess the sum of rewards of any other arm j is the p R (n i,t , t, s j,t ) defined in the theorem statement. The arm node R i cannot possibly guess the sum of rewards for arm j with a better probability because it does not see any useful information that it can leverage. In particular, the only information that R i receives about the rewards of any other arm is the partial max value B m (derived from the sum of arm i m using the number of pulls of i m , to which R i does not have access) received during Step 3. As mentioned in Section 7.4.2, we assume that the information that one arm can derive from one such random B value does not provide any advantage.

As a corollary, by Lemma 7.4.1 and Theorem 7.4.3, we infer that R i cannot learn the cumulative reward with probability better than random.

Security of U. The user knows the cumulative reward that she can decrypt after

Step 6. Moreover, the user cannot learn the arms selected at some round (Theorem 7.4.4) or the sum of rewards for some arm (Theorem 7.4.5). Theorem 7.4.4. For each round t ∈ {2, . . . , N -K + 1}, the user U cannot guess which arm is pulled at round t with probability better than random.

Proof. The user does not receive any message until the end of UCB-DS (Step 6). By construction of UCB-DS, all arms are pulled at the first round, then from round 2 and until the end of UCB-DS i.e., round N -K + 1, there is a single arm pulled at each round. In particular, the user does not receive any information on which arm is pulled at some round, hence her best strategy is to answer randomly, with a probability of success of 1 K .

-Analysis of UCB-DS

Theorem 7.4.5. For an arm i ∈ K , the user U cannot guess the sum s i of rewards for the arm i with probability better that random.

Proof. Similarly to the previous proof, we observe that the user U does not receive any message until the end of UCB-DS (Step 6). In particular, U does not get any information about which arm is selected at some round. Because all arm probability distributions are equiprobable to U, it is also true that all partitions of the cumulative reward R are equiprobable to U, thus U has no advantage in guessing the partition of rewards. Hence, the the probability of U guessing a correct partition of the rewards is equal to 1 p(R) , where p(R) is the number of partitions of R. This observation also proves that U cannot guess the individual sum of rewards of some arm i. If it was the case, then U would know that some of the partitions are more likely e.g., if U can guess the sum of rewards s i of the arm i, then all partitions not having s i as the value for arm i would be discarded, which is a contradiction. External observer. An external observer sees all messages exchanged between nodes, from which we show that she cannot learn which arm is pulled at some round (Theorem 7.4.6) or the sum of rewards for some arm (Theorem 7.4.7). Theorem 7.4.6. For each round t ∈ {2, . . . , N -K + 1}, an honest-but-curious external observer cannot learn which arm is pulled at round t, given data t ext , with probability better than random. More precisely, for all PPT adversaries A,

where A pa(t) (data t ext ) returns the guess of A on which arm is pulled at round t, and i t m is the true arm pulled at round t. Proof. By construction of UCB-DS, all arms are pulled at the first round, then from round 2 and until the end of UCB-DS i.e., round N -K + 1, there is a single arm pulled at each round. We next show that if there exists a PPT adversary with a non negligible advantage in guessing the arm pulled at some round 2 ≤ t ≤ N -K + 1, then this would break the IND-CPA property of AES-CBC.

An external observer (denoted ext in the sequel) sees all encrypted messages that are exchanged among UCB-DS participants. We denote by data t ext this collection of data after round t. We assume, toward a contradiction, that there exists a PPT adversary A able from data ext to find the arm i t m pulled at some round t with a non negligible advantage x:

We also assume that if data t ext does not correspond to an actual collection of encrypted messages that ext sees, then the advantage for such an input is negligible.

We next show that by using the adversary A, we can construct an adversary B able to break the IND-CPA property of AES-CBC. To do so, B creates a simulation Chapter 7 -Secure Outsourcing of Multi-Armed Bandits of an UCB-DS execution, similarly to the proof of Theorem 7.4.1. Even though the messages of such a simulation are encrypted, B knows the keys hence the state of each arm. In particular, B knows in plain text the message sent by AS to the arm pulled at round t. This message is of the form m 1 = (1||f irst i,t ||next i,t ), with 1 being the Boolean value saying the arm has to be pulled.

As input for the IND-CPA game, B sends the aforementioned m 1 and another message m 0 = (0||f irst i,t ||next i,t ) that it generates based on m 1 . Then, B receives back Enc(m b ), where b is a random bit selected uniformly by the challenger. Next, B calls A pa(t) (data ′ ext ), where data ′ ext is the collection of encrypted messages from the B's simulation, except that it replaces Enc(m 1 ) by Enc(m b ). The strategy of B is: if A returns the correct i t m , then B returns 1, otherwise answer randomly.

• If b = 0 (probability 1 2 ), then A does not receive a correct simulation because no arm is pulled at round t. According to our assumption, A does not give any advantage.

-If A returns the correct i t m (probability 1 K ), then B answers 1 and is wrong.

-Otherwise (probability 1 -1 K ), then B answers randomly and is correct with probability 1 2 . This branch yields a probability of success of 1 2 (1 -

• If b = 1 (probability 1 2 ), then the advantage given by A can be leveraged by B.

-If A returns the correct i t m (probability 1 K + x + negl(λ)), then B correctly answers 1. The probability of success of this branch is 1 2 ( 1 K + x + negl(λ)). -Otherwise (probability 1 -1 Kx -negl(λ)), B answers randomly and is correct with probability 1 2 . This branch yields a probability of success of

By aggregating the aforementioned cases, the probability α of success of B is:

Hence, B has an advantage of x 4 in the IND-CPA game, which is non negligible. This contradicts the fact that AES-CBC is IND-CPA secure. Hence, we conclude that there does not exist any PPT adversary A that violates the property stated in the theorem.

Before proving the next theorem, we add a new hypothesis.

Chapter 7 -Secure Outsourcing of Multi-Armed Bandits Algorithm 10 Modifications to the pseudocode of UCB-DS, cf. Algorithms 8 and 9, to obtain UCB-DS2. For AS, take everything but the last 2 lines as in Algorithm 8, then take this pseudocode:

Break

For R i (with i ∈ K ), take the first 8 lines as in Algorithm 9, then take the following pseudocode. All theorems from Section 7.4.2 also hold for UCB-DS2, except Theorem 7.4.2 that is replaced by the next theorem, which formally states the stronger security guarantees of UCB-DS2. Theorem 7.4.8. In UCB-DS2, at the end of round t ∈ N -K and before the start of round t + 1, given data t R i , an honest-but-curious arm node R i cannot learn the arm to be pulled at round t + 1 with probability better than random.

Proof. At each round t, the arm node R i receives Enc(B m ||Enc im (i m )) and decrypts into B m ||Enc im (i m ). By hypothesis, B m does not leak any information about the next arm to be pulled. The only way for R i to guess the next arm with probability better than random is to use some information contained in Enc im (i m ). However, since Enc im is IND-CPA, it is impossible to learn any information on i m with non negligible advantage. Hence, the strategy of R i to guess the arm pulled at round t + 1 is not better than random.

Experiments

We next present a proof-of-concept experimental study devoted to showing that the overhead due to cryptographic primitives is reasonable, hence our protocols are feasible in practice. More precisely, we show the scalability of our protocols with respect to both parameters N and K through an experimental study using synthetic and real data. We compare:

• UCB = Standard UCB algorithm [ACBF02; BC12], outlined in Algorithm 2.

• UCB-D = UCB with distribution of tasks among participants in the spirit of UCB-DS cf. Section 7.3.2, but with all messages exchanged in clear among participants (that is, UCB-D does not use any cryptographic primitive). The only overhead compared to UCB comes from the distribution of tasks.

• UCB-DS = Distributed Secure UCB cf. Section 7.3.2.

• UCB-DS2 = The refinement of UCB-DS cf. Section 7.4.4.

We implemented the algorithms in Python 3. For AES-CBC we used the Py-Cryptodome library 1 and keys of 256 bits. For additive homomorphic encryption using the Paillier's cryptosystem, we used the phe library 2 in the default configuration with keys of 2048 bits. We carried out our experiments on a laptop with CPU Intel Core i7 of 2.80GHz and 16GB of RAM, running Ubuntu. Each result that we report is averaged over 100 runs. In each run, we executed all four algorithms using the same random seeds, needed for drawing the arm rewards and for generating the permutation used to iterate in a random order over the arms when choosing the argmax arm to be pulled at the next round.

For reproducibility reasons, we make available on a public GitHub repository 3 our source code, together with the data that we used, the generated results from which we obtained our plots, and scripts that allow to install the needed libraries and reproduce our plots.

Before discussing our experimental results, we would like to stress that, as expected, in each experiment, all four algorithms output exactly the same cumulative reward. The property that our secure algorithms return exactly the same cumulative reward as standard UCB is in contrast with differentially-private multi-armed bandit algorithms [GUK18; MT15; TD16], where the returned cumulative rewards are different from that of standard UCB. Consequently, a shallow empirical comparison between these works and ours boils down to comparing apples and oranges: (i) on the one hand, the running time of differentially-private bandit algorithms is roughly the same as for standard UCB and is never reported in their experiments, whereas (ii) on the other hand, for our algorithms the cumulative reward is always the same as for standard UCB and consequently there is no point for us in doing any plot on the cumulative reward. Nevertheless, we carefully analyzed all experimental settings 1 https://pycryptodome.readthedocs.io/en/latest/src/cipher/classic.html 2 https://python-paillier.readthedocs.io/en/develop/ 3 https://github.com/radu1/secure-ucb

Images Credits

The images under each part title belong to their respective authors.

, in an empty cell.

In this example, h q (e n ) = 2 q -1. If there is no such empty cell in T [h q (e n )], the fingerprint is stored in a random cell of the row. . . .

List of Algorithms

ABSTRACT

In this thesis, we are interested in two major themes: data security in exchange protocols, and the analysis and securing of data structures. To do so, we apply formal analyses, based on existing cryptographic tools as well as ad-hoc modelling for the problem under consideration. Firstly, we will study the security of duplicate detectors, as well as an optimisation of the use of available storage space. Then, we will turn to a practical modelling case, proposing a new formal model for blockchain. Finally, we will study the problem of outsourcing bandit learning protocols. We will see how to outsource calculations, while proving that the network learns as little as possible.

KEYWORDS

information security, modelisation, exchange protocols, optimisation, applied cryptography