Quoc-Cuong To

Benjamin Nguyen

Private and Scalable Execution of SQL Aggregates on a Secure Decentralized Architecture 

Keywords: Descriptors: [Security and Privacy]: Privacy-Preserving Protocols SQL execution, privacy-preserving database protocols Trusted hardware, decentralized architecture, parallel computing

Current applications, from complex sensor systems (e.g. quantified self) to online e-markets acquire vast quantities of personal information which usually end-up on central servers where they are exposed to prying eyes. Conversely, decentralized architectures helping individuals keep full control of their data, complexify global treatments and queries, impeding the development of innovative services. This paper precisely aims at reconciling individual's privacy on one side and global benefits for the community and business perspectives on the other side. It promotes the idea of pushing the security to secure hardware devices controlling the data at the place of their acquisition. Thanks to these tangible physical elements of trust, secure distributed querying protocols can reestablish the capacity to perform global computations, such as SQL aggregates, without revealing any sensitive information to central servers. This paper studies how to secure the execution of such queries in the presence of honest-but-curious and malicious attackers. It also discusses how the resulting querying protocols can be integrated in a concrete decentralized architecture. Cost models and experiments on SQL/AA, our distributed prototype running on real tamperresistant hardware, demonstrate that this approach can scale to nationwide applications.

INTRODUCTION

With the convergence of mobile communications, sensors and online social networks technologies, an exponential amount of personal data -either freely disclosed by users or transparently acquired by sensors -end up in servers. This massive amount of data, the new oil, represents an unprecedented potential for applications and business (e.g., car insurance billing, traffic decongestion, smart grids optimization, healthcare surveillance, participatory sensing). However, centralizing and processing all one's data in a single server incurs a major problem with regards to privacy. Indeed, individuals' data is carefully scrutinized by governmental agencies and companies in charge of processing it [START_REF] De Montjoye | On the Trusted Use of Large-Scale Personal Data[END_REF]. Privacy violations also arise from negligence and attacks and no current server-based approach, including cryptography based and server-side secure hardware [START_REF] Agrawal | Hippocratic databases[END_REF], seems capable of closing the gap. Conversely, decentralized architectures (e.g., personal data vault), providing better control to the user over the management of her personal data, impede global computations by construction.

This paper aims to demonstrate that privacy protection and global computation are not antagonist and can be reconciled to the best benefit of the individuals, the 39:2 . ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY community and the companies. To reach this goal, this paper capitalizes on a novel architectural approach called Trusted Cells [START_REF] Anciaux | Trusted Cells: A Sea Change for Personal Data Services[END_REF]. Trusted Cells push the security to the edges of the network, through personal data servers [START_REF] Allard | Secure Personal Data Servers: a Vision Paper[END_REF] running on secure smart phones, set-top boxes, plug computers 1 or secure portable tokens 2 forming a global decentralized data platform. Indeed, thanks to the emergence of low-cost secure hardware and firmware technologies like ARM TrustZone 3 , a full Trusted Execution Environment (TEE) will soon be present in any client device. In this paper, and up to the experiments section, we consider that personal data is acquired and/or hosted by secure devices but make no additional assumption regarding the technical solution they rely on.

Global queries definitely make sense in this context. Typically, it would be helpful to compute aggregates over smart meters without disclosing individual's raw data (e.g., compute the mean energy consumption per time period and district). Identifying queries also make sense assuming the identified subjects consent to participate (e.g., send an alert to people living in Paris-La Defense district if their total energy consumption reaches a given threshold). Computing SQL-like queries on such distributed infrastructure leads to two major and different problems: computing joins between data hosted at different locations and computing aggregates over this same data. We tackled the first issue in [To et al. 2015a] thanks to a trusted MapReducebased system that can support joins and cover parallelizable tasks executed over a Trusted Cells infrastructure. This paper concentrates on the second issue: how to compute global queries over decentralized personal data stores while respecting users' privacy? Indeed, we believe that the computation of aggregates is central to the many novel privacy preserving applications such as smart metering, eadministration, etc.

Our objective is to make as few restrictions on the computation model as possible. We model the information system as a global database formed by the union of a myriad of distributed local data stores (e.g., nation-wide context) and we consider regular SQL queries and a traditional access control model. Hence the context we are targeting is different and more general than, (1) querying encrypted outsourced data where restrictions are put on the predicates which can be evaluated [START_REF] Agrawal | Order-preserving encryption for numeric data[END_REF][START_REF] Amanatidis | Provably-secure schemes for basic query support in outsourced databases[END_REF][START_REF] Raluca | CryptDB: protecting confidentiality with encrypted query processing[END_REF][START_REF] Hacigümüs | Efficient execution of aggregation queries over encrypted relational databases[END_REF]], (2) performing privacy-preserving queries usually restricted to statistical queries matching differential privacy constraints [Fung et al. 2010, Fayyoumi and[START_REF] Fayyoumi | A survey on statistical disclosure control and micro-aggregation techniques for secure statistical databases[END_REF] and (3) performing Secure-Multi-Party (SMC) query computations which cannot meet both query generality and scalability objectives [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF].

The contributions of this paper are 4 : (1) to propose different secure query execution techniques to evaluate regular SQL "group by" queries over a set of distributed trusted personal data stores, (2) to quantify and compare the respective information exposure of these techniques, (3) to study the range of applicability of these techniques and show that our approach is compatible with nation-wide contexts by thorough analysis of a cost model and performance measurements of a prototype running on real secure hardware devices.

The rest of this paper is organized as follows. Section 2 states our problem. Section 3 discusses related works. Section 4 introduces a framework to execute simple queries and Section 5 concentrates on complex queries involving Group By and Having clauses. Section 6 discusses practical aspects of the proposed solution.

Section 7 presents a privacy analysis of each querying protocol. Section 8 analyzes the performance of these solutions through cost models while section 9 validates these cost models through performance measurements. Finally section 10 concludes. Appendix A is added at the end to clarify how we prevent malicious attacks.

CONTEXT OF THE STUDY 2.1 Scenarios and queries of interest

As discussed in [START_REF] Anciaux | Trusted Cells: A Sea Change for Personal Data Services[END_REF], trusted hardware is more and more versatile and has become a key enabler for all applications where trust is required at the edges of the network. Figure 1 depicts different scenarios where a Trusted Data Server (TDS) is called to play a central role, by reestablishing the capacity to perform global computations without revealing any sensitive information to central servers. TDS can be integrated in energy smart meters to gather energy consumption raw data, to locally perform aggregate queries for billing or smart grid optimization purpose and externalize only certified results, thereby reconciling individuals' privacy and energy providers' benefits. Green button5 is another application example where individuals accept sharing their data with their neighborhood through distributed queries for their personal benefit. Similarly, TDS can be integrated in GPS trackers to protect individuals' privacy while securely computing insurance fees or carbon tax and participating in general interest distributed services such as traffic jam reduction. Moreover, TDSs can be hosted in personal devices to implement secure personal folders like e.g., PCEHR (Personally Controlled Electronic Health Record) fed by the individuals themselves thanks to the Blue Button initiative6 and/or quantified-self devices. Distributed queries are useful in this context to help epidemiologists performing global surveys or allow patients suffering from the same illness to share their data in a controlled manner.

For the sake of generality, we make no assumption about how the data is actually gathered by TDSs, this point being application dependent [START_REF] Allard | Secure Personal Data Servers: a Vision Paper[END_REF][START_REF] De Montjoye | On the Trusted Use of Large-Scale Personal Data[END_REF]. We simply consider that local databases conform to a common schema (Fig. 3) which can be queried in SQL. For example, power meter data (resp., GPS traces, healthcare records, etc) can be stored in one (or several) table(s) whose schema is defined by the national distribution company (resp., insurance company consortium, Ministry of Health7 , specific administration, etc). Since raw data can be highly sensitive, it must also be protected by an access control policy defined either by the producer organism, by the legislator or by a consumer association. Depending on the scenario, each individual may also opt-in/out of a particular query. For sake of generality again, we consider that each TDS participating in a distributed query protocol enforces at the same time the access control policy protecting the local data it hosts, with no additional consideration for the access control model itself, the choice of this model being orthogonal to this study. Hence, the objective is to let queriers (users) query this decentralized database exactly as if it were centralized, without restricting the expressive power of the language to statistical queries as in many Privacy-Preserving Data Publishing (PPDP) works [START_REF] Fayyoumi | A survey on statistical disclosure control and micro-aggregation techniques for secure statistical databases[END_REF]Oommen 2010, Popa et al. 2011]. the mean energy consumption of consumers living in a detached home grouped by district, for districts where over 100 consumers answered the poll and the poll stops after having globally received at least 50.000 answers. The semantics of the query are the same as those of a stream relational query [START_REF] Daniel | Aurora: a new model and architecture for data stream management[END_REF]]. Only the smart meter of customers who opt-in for this service will participate in the computation. Needless to say that the querier, that is the distribution company, must be prevented to see the raw data of its customers for privacy concerns 9 .

In other scenarios where TDSs are seldom connected (e.g., querying mobile PCEHR), the time to collect the data is probably going to be quite large. Therefore the challenge is not on the overall response time, but rather to show that the query computation on the collected data is tractable in reasonable time, given local resources.

restriction on the queries executed locally by each TDS. 9 At the 1HZ granularity provided by the French Linky power meters, most electrical appliances have a distinctive energy signature. It is thus possible to infer from the power meter data inhabitants activities [START_REF] Lam | A Novel Method to Construct Taxonomy Electrical Appliances Based on Load Signatures[END_REF]]. Also note that unless specified otherwise, our semantics make the Open World Assumption: since we assume that data is not replicated over TDS, many true tuples will not be collected during the specified period and/or due to the limit, both indicated in the SIZE clause. Hence, the SIZE clause is mandatory, since having a complete answer is contradictory with the open world assumption. Under the closed world assumption (in which all TDS are always connected to the infrastructure), one can replace the keyword SIZE by ALL to collect all available data.

Private and Scalable

Asymmetric Computing Architecture

The architecture we consider is decentralized by nature. It is formed by a large set of low power TDSs embedded in secure devices. Despite the diversity of existing hardware platforms, a secure device can be abstracted by (1) a Trusted Execution Environment and (2) a (potentially untrusted but cryptographically protected) mass storage area (see Fig. 2)10 . E.g., the former can be provided by a tamper-resistant microcontroller while the latter can be provided by Flash memory. The important assumption is that the TDS code is executed by the secure device hosting it and thus cannot be tampered, even by the TDS holder herself. Each TDS exhibits the following properties:

High Security. This is due to a combination of factors: (1) the microcontroller tamper-resistance, making hardware and side-channel attacks highly difficult, (2) the certification of the embedded code making software attacks also highly difficult, (3) the ability to be auto-administered, in contrast with traditional multi-user servers, precluding DBA attacks, and (4) the fact that the device holder cannot directly access the data stored locally (she must authenticate and can only access data according to her own privileges). This last point is of utmost importance because it allows the definition of distributed protocols where data is securely exchanged among TDSs with no confidentiality risk.

Low Availability. The Secure Device is physically controlled by its owner who may connect or disconnect it at will, providing no availability guarantee.

Modest Computing Resource. Most Secure Devices provide modest computing resources (see section 8) due to the hardware constraints linked to their tamperresistance. On the other hand, a dedicated cryptographic co-processor usually handles cryptographic operations very efficiently (e.g., AES and SHA). Hence, even if there exist differences among Secure Devices (e.g., smart tokens are more robust against tampering but less powerful than TrustZone devices), all provide much stronger security guarantees combined with a much weaker availability and computing power than any traditional server. The computing architecture, illustrated in Fig. 3 is said asymmetric in the sense that it is composed of a very large number of low power, weakly connected but highly secure TDSs and of a powerful, highly available but untrusted SSI.

Threat Model

TDSs are the unique elements of trust in the architecture and are considered honest.

As mentioned earlier, no trust assumption needs to be made on the TDS holder herself because a TDS is tamper-resistant and enforces the access control rules associated to its holder (just like a car driver cannot tamper the GPS tracker installed in her car by its insurance company or a customer cannot gain access to any secret data stored in her banking smartcard).

We primarily consider honest-but-curious (also called semi-honest) SSI (i.e., which tries to infer any information it can but strictly follows the protocol), concentrating on the prevention of confidentiality attacks. We additionally discuss (see Appendix A) how to extend our protocols with safety properties to detect attacks conducted by malicious SSI (i.e., which may tamper the protocol with no limit, including denial-ofservice), although the probability of such attacks is supposed to be much lower because of the risk of an irreversible political/financial damage and even the risk of a class action against the SSI.

The objective is thus to implement a querying protocol so that (1) the querier can gain access only to the final result of authorized queries (not to the raw data participating in the computation), as in a traditional database system and (2) intermediate results stored in SSI are obfuscated. Preventing inferential attacks by combining the result of a sequence of authorized queries as in statistical databases and PPDP work (see section 3) is orthogonal to this study.

RELATED WORKS

This work has connections with related studies in different domains, namely protection of outsourced (personal) databases, statistical databases and PPDP, SMC and finally secure aggregation in sensor networks. We review these works below.

Security in outsourced databases. Outsourced database services or DaaS [START_REF] Hacigumus | Executing SQL over encrypted data in database service provider model[END_REF] allow users to store sensitive data on a remote, untrusted server and retrieve desired parts of it on request. Many works have addressed the security of DaaS by encrypting the data at rest and pushing part of the processing to the server side. Searchable encryption has been studied in the symmetric-key [START_REF] Amanatidis | Provably-secure schemes for basic query support in outsourced databases[END_REF]] and public-key [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF] settings but these works focus mainly on simple exact-match queries and introduce a high computing cost. [START_REF] Agrawal | Order-preserving encryption for numeric data[END_REF] proposed an order preserving encryption (OPE) scheme, which ensures that the order among plaintext data is preserved in the ciphertext domain, supporting range and aggregate queries, but OPE relies on the strong assumption that all plaintexts in the database are known in advance and order-preserving is usually synonym of weaker security. The assumption on the a priori knowledge of all plaintext is not always practical (e.g., in our highly distributed database context, users do not know all plaintexts a priori), so a stateless scheme whose encryption algorithm can process single plaintexts on the fly is more practical. Bucketizationbased techniques [START_REF] Hacigumus | Executing SQL over encrypted data in database service provider model[END_REF][START_REF] Hore | Secure multidimensional range queries over outsourced data[END_REF]] use distributional properties of the dataset to partition data and design indexing techniques that allow approximate queries over encrypted data. Unlike cryptographic schemes that aim for exact predicate evaluation, bucketization admits false positives while ensuring all matching data is retrieved. A post-processing step is required at the client-side to weed out the false positives. These techniques often support limited types of queries and lack of a precise analysis of the performance/security tradeoff introduced by the indexes. To overcome this limitation, the work in [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF]] quantitatively measures the resulting inference exposure. Other works introduce solutions to compute basic arithmetic over encrypted data, but homomorphic encryption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]] supports only range queries, fully homomorphic encryption [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]] is unrealistic in terms of time, and privacy homomorphism [Hacigumus et al. 2004] is insecure under ciphertext-only attacks [START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF]. Hence, optimal performance/security tradeoff for outsourced databases is still regarded as the Holy Grail. Recently, the Monomi system [START_REF] Tu | Processing analytical queries over encrypted data[END_REF] has been proposed for securely executing analytical workloads over sensitive data on an untrusted database server. Although this system can execute complex queries, there can be only one trusted client decrypting data, and therefore it cannot enjoy the benefit of parallel computing. Another limitation of this system is that to perform the GROUP BY queries, it encrypts the grouping attributes with deterministic encryption, allowing frequency-based attacks. Statistical Database and PPDP. Statistical databases (SDB) [START_REF] Fayyoumi | A survey on statistical disclosure control and micro-aggregation techniques for secure statistical databases[END_REF] are motivated by the desire to compute statistics without compromising sensitive information about individuals. This requires trusting the server to perform query restriction or data perturbation, to produce the approximate results, and to deliver them to untrusted queriers. Thus, the SDB model is orthogonal to our context since (1) it assumes a trusted third party (i.e., the SDB server) and (2) it usually produces approximate results to prevent queriers from conducting inferential attack [START_REF] Fayyoumi | A survey on statistical disclosure control and micro-aggregation techniques for secure statistical databases[END_REF]. For its part, Privacy-Preserving Data Publishing [START_REF] Benjamin | Privacy-Preserving Data Publishing: A survey of Recent Developments[END_REF] provides a non trusted user with some sanitized data produced by an anonymization process such as k-anonymity, ldiversity or differential privacy to cite the most common ones [START_REF] Benjamin | Privacy-Preserving Data Publishing: A survey of Recent Developments[END_REF].

Similarly, PPDP is orthogonal to our context since it again assumes a trusted third party (i.e., the publisher) and produces sanitized data of lower quality to match the information exposure dictated by a specific privacy model. The work in [START_REF] Allard | MetaP: Revisiting Privacy-Preserving Data Publishing using Secure Devices[END_REF] tackles the first limitation by pushing the trust to secure clients but keeps the objective of producing sanitized releases. Contrary to these works, our paper targets Secure Multi-party Computation. Secure multi-party computation (SMC) allows N parties to share a computation in which each party learns only what can be inferred from their own inputs (which can then be kept private) and the output of the computation. This problem is represented as a combinatorial circuit which depends on the size of the input. The resulting cost of a SMC protocol depends on the number of inter-participant interactions, which in turn depends exponentially on the size of the input data, on the complexity of the initial function, and on the number of participants. Despite their unquestionable theoretical interest, generic SMC approaches are impractical where inputs are large and the function to be computed complex. Ad-hoc SMC protocols have been proposed [START_REF] Kissner | Privacy-Preserving Set Operations[END_REF] to solve specific problems/functions but they lack of generality and usually make strong assumptions on participants' availability. Hence, SMC is badly adapted to our context. Secure Data Aggregation. Wireless sensor networks (WSN) [START_REF] Alzaid | Secure Data Aggregation in Wireless Sensor Networks: A Survey[END_REF] consist of sensor nodes with limited power, computation, storage, sensing and communication capabilities. In WSN, an aggregator node can compute the sum, average, minimum or maximum of the data from its children sensors, and send the aggregation results to a higher-level aggregator. WSN have some connection with our context regarding the computation of distributed aggregations. However, contrary to the TDS context, WSN nodes are highly available, can communicate with each other in order to form a network topology to optimize calculations (In fact, TDSs can collaborate to form the topology through SSI, but because of the weak connectivity of TDSs, forming the topology is inefficient in term of time). Other work [START_REF] Castelluccia | Efficient Aggregation of Encrypted Data in Wireless Sensor Networks[END_REF] uses additively homomorphic encryption for computing aggregation function on encrypted data in WSN but fails to consider queries with GROUP BY clauses. Liu et al. [2010] protects data against frequency-based attacks but considers only point and range queries.

As a conclusion, and to the best of our knowledge, our work is the first proposal achieving a fully distributed and secure solution to compute aggregate SQL queries over a large set of participants.

BASIC QUERYING PROTOCOL

This section presents the protocol to compute Select-From-Where queries. This protocol is simple yet very useful in practice, since many queries are of this form. We also use it to help the reader get used to our approach. We tackle the more difficult Group By clause in section 5.

Core infrastructure

Our querying protocols share common basic mechanisms to make TDSs aware of the queries to be computed and to organize the dataflow between TDSs and queriers such that SSI cannot infer anything from the queries and their results.

Query and result delivery: queries are executed in pull mode. A querier posts its query to SSI and TDSs download it at connection time. To this end, SSI can maintain personal query boxes (in reference to mailboxes) where each TDS receives queries directed to it (e.g., get the monthly energy consumption of consumer C) and a global query box for queries directed to the crowd (e.g., get the mean of energy consumption per month for people living in district D). Result tuples are gathered by SSI in a temporary storage area. A query remains active until the SIZE clause is evaluated to true by SSI, which then informs the querier that the result is ready.

Dataflow obfuscation: all data (queries and tuples) exchanged between the querier and the TDSs, and between TDSs themselves, can be spied by SSI and must therefore be encrypted. However, an honest-but-curious SSI can try to conduct frequency-based attacks [START_REF] Liu | Ensuring Data Storage Security against Frequency-based Attacks in Wireless Networks[END_REF] contain identifying information about the individuals. Though basic, these queries answer a number of practical use-cases, e.g., a doctor querying the embedded healthcare folders of her patients, or an energy provider willing to offer special prices to people matching a specific consumption profile. To compute such queries, the protocol is divided in two phases (see Fig. 4):

Collection phase: (step 1) the querier posts on SSI a query Q encrypted with kQ, its credential ₡ signed by an authority and S the SIZE clause of the query in cleartext so that SSI can evaluate it; (step 2) targeted TDSs11 download Q when they connect; (step 3) each of these TDSs decrypts Q, checks ₡, evaluates the AC policy associated to the querier and computes the result of the WHERE clause on the local data; then each TDS either sends its result tuples (step 4), or a small random number of dummy tuples12 when the result is empty or the querier has not enough privilege to access these local data (step 4'), non-deterministically encrypted with kT. The collection phase stops when the SIZE condition has been reached (i.e., the total number of collected encrypted tuples is S)13 . The result of the collection phase is actually the result of the query, possibly complemented with dummy tuples. We call it Covering Result. Accuracy. Since SSI is honest-but-curious, it will deliver to the querier all tuples returned by the TDSs. Dummy tuples are marked so that they can be recognized and removed after decryption by each TDS. Therefore the final result contains only true tuples. If a TDS goes offline in the middle of processing a partition, SSI resends that partition to another available TDS after a given timeout so that the result is complete. As discussed in Appendix A, accuracy is more difficult to achieve in the case of malicious SSI.

Security. Since SSI does not know key kQ, it can decrypt neither the query nor the result tuples. TDSs use nDet_Enc for encrypting the result tuples so that SSI can neither launch any frequency-based attacks nor detect dummy tuples. There can be two additional risks. The first risk is that SSI acquires a TDS with the objective to get the cryptographic material. As stated in section 2, TDS code cannot be tampered, even by its holder. Whatever the information decrypted internally, the only output that a TDS can deliver is a set of encrypted tuples, which does not represent any benefit for SSI. The second risk is if SSI colludes with the querier. For the same reason, SSI will only get the same information as the querier (i.e., the final result in clear text and no more).

Efficiency. The efficiency of the protocol is linked to the frequency of TDSs connection and to the SIZE clause. Both the collection and filtering phases are run in parallel by all connected TDSs and no time-consuming task is performed by any of them. As the experiment section will clarify, each TDS manages incoming partitions in streaming because the internal time to decrypt the data and perform the filtering is significantly less than the time needed to download the data.

While important in practice, executing Select-From-Where queries in the Trusted Cells context shows no intractable difficulties and the main objective of this section was to present the query framework in this simple context. Executing Group By queries is far more challenging. The next section will present different alternatives to tackle this problem. Rather than trying to get an optimal solution, which is context dependent, the objective is to explore the design space and show that different querying protocols may be devised to tackle a broad range of situations.

GROUP BY QUERIES

The Group By clause introduces an extra phase: the computation of aggregates of data produced by different TDSs, which is the weak point for frequency-based attacks. In this section, we propose several protocols, discussing their strong and weak points from both efficiency and security points of view.

Generic query evaluation protocol

Let us now consider general SQL queries of the form 14 :

SELECT <attribute(s) and/or aggregate function(s)> FROM <Table(s)> [WHERE <condition(s)>] [GROUP BY <grouping attribute(s)>] [HAVING <grouping condition(s)>][SIZE <size condition(s)>]

These queries are more challenging to compute because they require performing set-oriented computations over intermediate results sent by TDSs to SSI. The point is that TDSs usually have limited RAM, limited computing resources and limited connectivity. It is therefore unrealistic to devise a protocol where a single TDS downloads the intermediate results of all participants, decrypts them and computes the aggregation alone. On the other hand, SSI cannot help much in the processing since (1) it is not allowed to decrypt any intermediate results and (2) it cannot gather encrypted data into groups based on the encrypted value of the grouping attributes, denoted by AG={Gi}, without gaining some knowledge about the data distribution. This would indeed violate our security assumption since the knowledge of AG distribution opens the door to frequency-based attacks by SSI: e.g. in the extreme case where AG contains both quasi-identifiers and sensitive values, attribute linkage would become obvious. Finally, the querier cannot help in the processing either since she is only granted access to the final result, and not to the raw data.

To solve this problem, we suggest a generic aggregation protocol divided into three phases (see Fig. 5):

Collection phase: similar to the basic protocol. Aggregation phase:(step 5) SSI partitions the result of the collection phase; (step 6) connected TDSs (may be different from the ones involved in the collection phase) download these partitions; (step 7) each of these TDS decrypts the partition, eliminates the dummy tuples and computes partial aggregations (i.e., aggregates data belonging to the same group inside each partition); (step 8) each TDS sends its partial aggregations encrypted with kT back to SSI; depending on the protocol (see next sections), the aggregation phase is iterative, and continues until all tuples belonging to the same group have been aggregated (steps 6', 7', 8'); The last iteration 14 For the sake of clarity, we concentrate on the management of distributive, algebraic and holistic aggregate functions identified in [START_REF] Locher | Foundations of Aggregation and Synchronization in Distributed Systems[END_REF]] as the most prominent and useful ones. Filtering phase: this phase is similar to the basic protocol except that the role of step 11 is to eliminate the groups which do not satisfy the HAVING clause instead of eliminating dummy tuples.

The rest of this section presents different variations of this generic protocol, depending on which encryption scheme is used in the collection and aggregation phases, how SSI constructs the partitions, and what information is revealed to SSI. Each solution has its own strengths and weaknesses and therefore is suitable for a specific situation. Three kinds of solutions are proposed: secure aggregation, noisebased, and histogram-based. They are subsequently compared in terms of privacy protection (Section 7) and performance (Section 8).

Secure Aggregation protocol

This protocol, denoted by S_Agg and detailed in Algorithm 1, instantiates the generic protocol as follows. In the collection phase, each participating TDS encrypts its result tuples using nDet_Enc (i.e., nEkT(tup)) to prevent any frequency-based attack by SSI.

The consequence is that SSI cannot get any knowledge about the group each tuple belongs to. Thus, during step 5, tuples from the same group are randomly distributed among the partitions. This imposes the aggregation phase to be iterative, as illustrated in Fig. 6. At each iteration, TDSs download encrypted partitions (i.e., Ω e ) containing a sequence of (AG, Aggregate) value pairs ((City, Energy_consumption) in the example), decrypt them to plaintext partitions (i.e., Ω ← nEkT -1 (Ω e )), aggregate values belonging to the same grouping attributes (i.e., Ωnew = Ωold⨢ Ω), and sends back to SSI an (usually smaller) encrypted sequence of (AG, Aggregate) value pairs where values of the same group have been aggregated. SSI gathers these partial aggregations to form new partitions, and so on and so forth until a single partition (i.e., Ωfinal) is produced, which contains the final aggregation. Accuracy. The requirement for S_Agg to terminate is that TDSs have enough resources to perform partial aggregations. Each TDS needs to maintain in memory a data structure called partial aggregate which stores the current value of the aggregate function being computed for each group. Each tuple read from the input partition contributes to the current value of the aggregate function for the group this tuple belongs to. Hence the partial aggregate structure must fit in RAM (or be swapped in stable storage at much higher cost). If the number of groups is high (e.g., grouping on a key attribute) and TDSs have a tiny RAM, this may become a limiting factor. In this case, FLASH memory can be used to store large intermediate results, at the cost of swapping.

Noise-based protocols

In these protocols, called Noise_based and detailed in Algorithm 2, Det_Enc is used during the collection phase on the grouping attributes AG. This is a significant change, since it allows SSI to help in data processing by assembling tuples belonging to the same groups in the same partitions. However, the downside is that using Det_Enc reveals the distribution of AG to SSI. To prevent this disclosure, the fundamental idea is that TDSs add some noise (i.e., fake tuples) to the data in order to hide the real distribution. The added fake tuples must have identified characteristics, as dummy tuples, such that TDSs can filter them out in a later step.

The aggregation phase is roughly similar to S_Agg, except that the content of partitions is no longer random, thereby accelerating convergence and allowing parallelism up to the final iteration. Two solutions are introduced to generate noise: random (white) noise, and noise controlled by complementary domains. Random (white) noise solutions. In this solution, denoted Rnf_Noise, nf fake tuples are generated randomly then added. TDSs apply Det_Enc on AG, and nDet_Enc on ĀG (the attributes not appearing in the GROUP BY clause). However, because the fake tuples are randomly generated, the distribution of mixed values may not be different enough from that of true values especially if the disparity in frequency among AG is big. To overcome this difficulty, a large quantity of fake tuples (nf>>1) must be injected to make the fake distribution dominate the true one. Noise controlled by complementary domains. This solution, called C_Noise, overcomes the limitation of Rnf_Noise by generating fake tuples based on the prior knowledge of the AG domain cardinality. Let us assume that AG domain cardinality is nd (e.g., for attribute Age, nd ≈ 130), a TDS will generate nd -1 fake tuples, one for each value different from the true one. The resulting distribution is totally flat by construction. However, if the domain cardinality is not readily available, a cardinality discovering algorithm must be launched beforehand (see section 5.4).

Accuracy. True tuples are grouped in partitions according to the value of their AG attributes so that the aggregate function can be computed correctly. Fake tuples are eliminated during the aggregation phase by TDSs thanks to their identified characteristics and do not contribute to the computation.

Security. Although TDSs apply Det-Enc on AG, AG distribution remains hidden to SSI by injecting enough white noise such that the fake distribution dominates the true one or by adding controlled noise producing a flat distribution.

Efficiency. TDSs do not need to materialize a large partial aggregate structure as in S_Agg because each partition contains tuples belonging to a small set of (ideally one) groups. Additionally, this property guarantees the convergence of the aggregation process and increases the parallelism in all phases of the protocol. However, the price to pay is the production and the elimination afterwards of a Suitable queries. Rnf_Noise with small nf is suitable for the queries in which there is no wide disparity in frequency between AG such as Q3: SELECT COUNT(Child) FROM Customer C GROUP BY C.Name HAVING COUNT(Child) <3. In contrast, the white noise solution with big nf is suitable for queries with big disparity such as Q4: SELECT COUNT(*) FROM Customer C GROUP BY C.Salary because the number of very rich people (i.e, salary > 1 M€/year) is much less than that of people having average salary. For the C_Noise, in term of the feasibility, because the process of calculating aggregation is divided among connected TDSs in a distributed and parallel way, better balancing the loads between TDSs, this protocol is applicable not only for the queries where G is small (e.g., Q1, Q2) but also for those with big G, such as Q5: SELECT AVG(Cons) FROM Customer C WHERE C.Age>20 GROUP BY C.Age (because the Age's domain is 130 at maximum). However, considering the efficiency, because the number of fake tuples is proportional to G, this solution is inappropriate for the queries with very big G (e.g., Q4) when it has to generate and process a large amount number of fake tuples.

Equi-depth histogram-based protocol

Getting a prior knowledge of the domain extension of AG allows significant optimizations as illustrated by C_Noise. Let us go one step further and exploit the prior knowledge of the real distribution of AG attributes. The idea is no longer to generate noisy data but rather to produce a uniform distribution of true data sent to SSI by grouping them into equi-depth histograms, in a way similar to [START_REF] Hacigumus | Executing SQL over encrypted data in database service provider model[END_REF]. The protocol, named ED_Hist, works as follows. Before entering the protocol, the distribution of AG attributes must be discovered and distributed to all TDSs. This process needs to be done only once and refreshed from time to time instead of being run for each query. The discovery process is similar to computing a Count function on Group By AG and can therefore be performed using one of the protocol introduced above. During the collection phase, each TDS uses this knowledge to calculate nearly equi-depth histograms that is a decomposition of the AG domain into buckets holding nearly the same number of true tuples. Each bucket is identified by a hash value giving no information about the position of the bucket elements in the domain. Then the TDS allocates its tuple(s) to the corresponding bucket(s) and sends to SSI couples of the form (h(bucketId), nDet_Enc(tuple)). During the partitioning step of the aggregation phase, SSI assembles tuples belonging to the same buckets in the same partitions. Each partition may contain several groups since a same bucket holds several distinct values. The first aggregation step computes partial aggregations of these partitions and returns to SSI results of the form (Det_Enc(group), nDet_Enc(partial aggregate)). A second aggregation step is required to combine these partial aggregations and deliver the final aggregation.

Accuracy. Only true tuples are delivered by TDSs and they are grouped in partitions according to the bucket they belong to. Buckets are disjoint and partitions contain a small set of grouping values so that partial aggregations can be computed by TDSs.

Security. SSI only sees a nearly uniform distribution of h(bucketId) values and cannot infer any information about the true distribution of AG attributes. Note that h(bucketId) plays here the same role as Det_Enc(bucketId) values but is cheaper to compute for TDSs. Efficiency. TDSs do not need to materialize a large partial aggregate structure as in S_Agg because each partition contains tuples belonging to a small set of groups during the first phase and to a single group during the second phase. As for C_Noise, this property guarantees convergence of the aggregation process and maximizes the parallelism in all phases of the protocol. But contrary to C_Noise, this benefit does not come at the price of managing fake tuples. Suitable queries. This solution is suitable for both kinds of queries (i.e., with small G like Q1, Q2 and big G like Q4, Q5) both in terms of efficiency (because it does not handle fake data) and feasibility (because it divides the big group into smaller ones and assigns the tasks for TDSs).

This section shows that the design space for executing complex queries with Group By is large. It presented three different alternatives for computing these queries and provided a short initial discussion about their respective accuracy, security and efficiency. Sections 8 and 9 compare in a deeper way these alternatives in terms of performance while Section 7 summarizes a comparison of these same alternatives in terms of security. The objective is to assess whether one solution dominates the others in all situations or which parameters are the most influential in the selection of the solution best adapted to each context.

PRACTICAL ISSUES

This section discusses complementary issues that are not core of the protocols but play an important role in ensuring that the protocols work in practice. These issues include: (i) how to manage the shared keys among TDSs and Querier; (ii) how to enforce the access control in the TDSs context; and (iii) how to calibrate the dataset subset.

Key Management

Our protocols rely heavily on the use of symmetric key cryptography. This section explains how these keys (kQ for Querier-TDS communication and kT for inter-TDS communication) can be managed and shared in a secure way.

State-of-the-Art. Group key exchange (GKE) protocols can be roughly classified into three classes: centralized, decentralized, and distributed [START_REF] Rafaeli | A Survey of Key Management for Secure Group Communication[END_REF]. In centralized group key protocols, a single entity is employed to control the whole group and is responsible for distributing group keys to group members. In the decentralized approaches, a set of group managers is responsible for managing the group as opposed to a single entity. In the distributed method, group members themselves contribute to the formation of group keys and are equally responsible for the re-keying and distribution of group keys. Their analysis [START_REF] Rafaeli | A Survey of Key Management for Secure Group Communication[END_REF] made clear that there is no unique solution that can satisfy all requirements. While centralized key management schemes are easy to implement, they tend to impose an overhead on a single entity. Decentralized protocols are relatively harder to implement and raise other issues, such as interfering with the data path or imposing security hazards on the group. Finally, distributed key management, by design, is simply not scalable. Hence it is important to understand fully the requirements of the application to select the most suitable GKE protocol.

Overview of Key Management. There are numerous ways to share the keys between TDSs and Querier depending on which context we consider.

In the closed context, we assume that all TDSs are produced by the same provider, so the shared key kT can be installed into TDSs at manufacturing time. If Querier also owns a TDS, and only one key kQ is used per querier, then it can be installed at manufacturing time as well. Otherwise (i.e. if we want to support one kQ per query), Querier must create a private/public key and can use any GKE to exchange key kQ.

An illustrative scenario for the closed context can be: patients and physicians in a hospital get each a TDS from the hospital, all TDSs being produced by the same manufacturer, so that the required cryptographic material is preinstalled in all TDSs before queries are executed.

In an open context, a Public Key Infrastructure (PKI) can be used so that queriers and TDSs all have a public-private key pair. When a TDS or querier registers for an application, it gets the required symmetric keys encrypted with its own public key. Since the total number of TDS manufacturers is assumed to be very small (in comparison with the total number of TDSs) and all the TDSs produced by the same producer have the same private/public key pair, the total number of private/public key pairs in the whole system is not big. Therefore, deploying a PKI in our architecture is suitable since it does not require an enormous investment in managing a very large number of private/public key pairs (i.e., proportional to the number of TDSs). PKI can be used to exchange both keys kQ and kT for both Querier cases i.e. owning a token or not. In the case we want to exchange kT, we can apply the above protocol for kQ with Querier being replaced by one of the TDSs. This TDS can be chosen randomly or based on its connection time (e.g., the TDS that has the longest connection time to SSI will be chosen).

An illustrative scenario for the open context can be: TDSs are integrated in smart phones produced by different smart phone producers. Each producer has many models and we assume that it installs the same private/public key on each model. In total, there are about one hundred models in the current market, so the number of different private/public keys is manageable. The phone's owner can then securely take part in surveys such as: what is the volume of 4G data people living in Paris consume in one month, group by network operators (Orange, SFR…).

In PKI, only one entity creates the whole secret key, and securely transfers it to the others. In the distributed key agreement protocols, however, there is no centralized key server available. This arrangement is justified in many situationse.g., in peer-to-peer or ad hoc networks where centralized resources are not readily available or are not fully trusted to generate the shared key entirely. Moreover, an advantage of distributed protocols over the centralized protocols is the increase in system reliability, because the group key is generated in a shared and contributory fashion and there is no single-point-of-failure [START_REF] Lee | Distributed collaborative key agreement and authentication protocols for dynamic peer Groups[END_REF]. Group AKE protocols are essential for secure collaborative (peer-to-peer) applications [START_REF] Lee | Distributed collaborative key agreement and authentication protocols for dynamic peer Groups[END_REF]]. In these circumstances, every participant wishes to contribute part of its secrecy to generate the shared key such that no party can predetermine the resulting value. In other words, no party is allowed to choose the group key on behalf of the whole group. These reasons lead to another way to exchange the shared key between TDSs and

Querier in the open context. In this way, GKE protocols [START_REF] Wu | Two-round contributory group key exchange protocol for wireless network environments[END_REF][START_REF] Amir | On the performance of group key agreement protocols[END_REF][START_REF] Wu | A Survey of Key Management in Mobile Ad Hoc Networks[END_REF]] can be used so that Querier can securely exchange the secret contributive key to all TDSs. Some GKE protocols [START_REF] Amir | On the performance of group key agreement protocols[END_REF]] require a broadcast operation in which a participant sends part of the key to the rest. These protocols are not suitable for our architecture since TDSs communicate together indirectly through SSI. This incurs a lot of operations for SSI to broadcast the messages (i.e., O(n 2 ), with n is the number of participants). Other protocols [START_REF] Wu | A Survey of Key Management in Mobile Ad Hoc Networks[END_REF]] overcome this weakness by requiring that participants form a tree structure to reduce the communication cost. Unfortunately, SSI has no knowledge in advance about TDSs thus this tree cannot be built. The work in [START_REF] Wu | Two-round contributory group key exchange protocol for wireless network environments[END_REF]] proposes a protocol with two rounds of communications and only one broadcast operation. However, this protocol still has the inherent weakness of the GKE: all participants must connect during the key exchange phase. This characteristic does not fit in our architecture since TDSs are weakly connected. Finally, the Broadcast Encryption [START_REF] Castelluccia | Efficient Aggregation of Encrypted Data in Wireless Sensor Networks[END_REF] requires that all participants have a shared secret in advance, preventing us from using it in a context where TDSs are produced by different manufacturers.

In consequence, we propose an adaptive GKE scheme, fitting our architecture as follows.

The Adaptive Key Exchange Protocol.Based on the decisional and computational Diffie-Hellman (CDH) assumptions, we propose a GKE protocol in [To et al. 2015b] in which each participant contributes a secret to the shared key. In the first step, each TDS generates a secret and sends it to Querier. Then, Querier selects a random number and computes a secret. The shared key is generated using these contributive secrets and broadcast to TDSs. Finally, upon receiving the message, only the TDSs who can compute the secret can decrypt the message and compute the shared key.

The security of the proposed GKE comes from the difficulty of the CDH problem and the one-way hash functions. Formally, there are five notions of security [Bresson and Manulis 2007] used as the standards to evaluate the security of a GKE protocol: Authenticated key exchange (AKE), Forward/backward secrecy, Contributiveness, Universal Composability (UC), and Mutual Authentication (MA). As detailed in [To et al. 2015b], our proposed GKE satisfies AKE security, forward/backward secrecy, and contributiveness and can also achieve MA-security at an additional cost of only two communication rounds.

The resulting protocol has three advantages over other GKEs in literature. First, it does not require that all TDSs connect at the same time to form the group, the connection of a single TDS per manufacturer being enough. The encrypted kT could be stored temporarily on SSI so that the offline TDS can get it as soon as it comes online and still take part in the protocol (i.e., using its private key to compute the secret, then the shared key). Second, even if a TDS opts out of a SQL query in the collection phase, it can still contribute to the parallel computation in the aggregation phase. With a traditional distributed key exchange, any TDS disconnected during setup will require a new key exchange to take place. With our protocol, each TDS contributes to part of the shared secret key, the only requirement is that at least one TDS per manufacturer participates in step 1 to contribute to the secret value representing this manufacturer. Third, in terms of performance, this protocol requires only 2-round of communications. Interested readers can refer to technical report [To et al. 2015b] for detail analysis of the computation comparison of this GKE with other related works.

In conclusion, our way of managing encryption keys can accommodate any situation, open or closed context, central PKI or fully distributed GKE, making our protocols very versatile.

Enforcing Access Control

Contrary to statistical databases or PPDP works where the protection resides on the fact that aggregate queries or anonymized releases do not reveal any information linkable to individuals, we consider here traditional SQL queries and a traditional access control model where subjects (either users, roles or applications) are granted access to objects (either tables or views). In the fully decentralized context we are targeting, this impacts both the definition of the access control (AC for short) and its enforcement.

AC policies can be defined and signed by trusted authorities (e.g., Ministry of Health, bank consortium, consumer association). As for the cryptographic material, such predefined policy can be either installed at burn time or be downloaded dynamically by each TDS using the key exchange protocols discussed in section 6.1. In more flexible scenarios, users may be allowed to modify the predefined AC policy to personalize it or to define it from scratch. The latter case results in a decentralized Hippocratic database [START_REF] Agrawal | Hippocratic databases[END_REF] in the sense that tuples belonging to a same table vertically partitioned among individuals may be ruled by different AC policies. Lastly, each individual may have the opportunity to opt-in/out of a given query. Our query execution protocol accommodates this diversity by construction, each TDS checking the querier's credentials and evaluating the AC policy locally before delivering any result (either true or dummy tuples depending on the AC outcome).

But how can AC be safely enforced at TDS side? The querier's credentials are themselves certified by a trusted party (e.g., a public organization or a company consortium delivering certificates to professionals to testify their identity and roles). TDSs check the querier's credentials and evaluates the AC policies thanks to an AC engine embedded on the secure chip, thereby protecting the control against any form of tampering. Details about the implementation of such a tamper-resistant AC module can be found in [START_REF] Anciaux | Hardware Approach for Trusted Access and Usage Control[END_REF]].

Collecting Data

In scenarios where TDSs are seldom connected (e.g., TDSs hosting a PCEHR), the collection phase of the querying protocol may be critical since its duration depends on the connection rate of TDSs. However, many of these scenarios can accommodate a result computed on a representative subset of the queried dataset (e.g., if Querier wants to find out the average salary of people in France with the total population of 65 millions, it is reasonable to survey only a fraction of the population). The question thus becomes how to calibrate the dataset subset? Larger subsets slow down the collection phase while smaller subsets diminish the accuracy and/or utility of the results. To determine if a sample population accurately portrays the actual population, we can estimate the sample size required to determine the actual mean within a given error threshold [START_REF] Gemmell | Sampling Techniques[END_REF].

We propose to use the Cochran's sample size formula [START_REF] Gemmell | Sampling Techniques[END_REF] to calculate the required sample size as follow:

𝑠𝑝𝑜𝑝 𝑒𝑠𝑡 = 𝜑 2 * ζ 2 * ( 𝑝𝑜𝑝 𝑚 𝑝𝑜𝑝 𝑚 -1 ) 𝜆 2 + (𝜑 2 * ζ 2 𝑝𝑜𝑝 𝑚 -1 )
with popm the size of the actual population, λ the user selected error rate, φ the user selected confidence level, and ζ the standard deviation of the actual population. The meaning of each parameter in this formula is explained below.

The error rate λ (sometimes called the level of precision) is the range in which the true value of the population is estimated to be (e.g., if a report states that 60% of people in the sample living in Paris have salary greater than 1300 EUR/month with an error rate of ±5%, then we can conclude that between 55% and 65% of Parisian earn more than 1300 EUR/month).

The confidence level φ is originated from the ideas of the Central Limit Theorem which states that when a population is repeatedly sampled, the average value of the attribute obtained by those samples approaches to the true population value. Moreover, the values obtained by these samples are distributed normally around the real value (i.e., some samples having a higher value and some obtaining a lower score than the true population value). In a normal distribution, approximately 95% of the The degree of variability ζ of the dataset refers to the distribution of attributes in the population. A low standard deviation indicates that the data points tend to be very close to the expected value; a high standard deviation indicates that the data points are spread out over a large range of values. The more heterogeneous a population, the larger the sample size required to obtain a given level of precision and vice versa.

To take into account the fact that some TDS's holders may opt out of the query, let us call optout the percentage of TDSs that opt out of the survey. Then, the required sample size we need to collect in the collection phase is:

𝑆 = 1 1 -𝑜𝑝𝑡 𝑜𝑢𝑡 * 𝑠𝑝𝑜𝑝 𝑒𝑠𝑡
Among the three parameters, λ and φ are user selected but ζ is data-dependent.

Cochran [1977] listed four ways of estimating population variances for sample size determinations: (1) take the sample in two steps, and use the results of the first step to determine how many additional responses are needed to attain an appropriate sample size based on the variance observed in the first step data;

(2) use pilot study results;

(3) use data from previous studies of the same or a similar population; or (4) estimate or guess the structure of the population assisted by some logical mathematical results. Usually, φ = 1.96 (i.e., within two standard deviations of the mean of the actual population) is often chosen in statistics to reflect 95% confidence level. In the experiment, because ζ is data-dependent, we will vary this parameter to see its impact to S. We also vary the error rate reflecting Querier's preference.

INFORMATION EXPOSURE ANALYSIS

Security of Basic Encryption Schemes

In cryptography, indistinguishability under chosen plaintext attack (IND-CPA) [START_REF] Katz | Introduction to Modern Cryptography: Principles and Protocols[END_REF]] is considered as a basic requirement for most provably secure cryptosystems. While nDet_Enc is considered to be IND-CPA [START_REF] Arasu | Querying Encrypted Data (Tutorial)[END_REF]], the maximum level of security for Det_Enc is PRIV [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF], which is a weaker notion of security than IND-CPA, due to the lack of randomness in cipertext. Then, it is important to understand how much (quantitatively) less (more) secure the Noise_based and ED_Hist are, in compare with nDet_Enc (Det_Enc). To address this question, we use two ways to measure the security level of Noise_based and ED_Hist, given nDet_Enc as the highest bound of security level. Each way corresponds to each increasing level of adversary's knowledge. In the first level, we assume that adversary does not know the distribution within a bucket of equi-depth histogram but only the global distribution (section 7.2). In the higher level, we address stronger attackers with more knowledge in which he knows the probability distribution of the values within each bucket (section 7.3).

Information Exposure with Coefficient

To quantify the confidentiality of each algorithm, we measure the information exposure of the encrypted data they reveal to SSI by using the approach proposed in [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF]] which introduces the concept of coefficient to assess the exposure. To illustrate, let us consider the example in Fig. 7 where Fig. 7a is taken from [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF] and Fig. 7b is the extension of [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF] applied in our context. The plaintext table Accounts is encrypted in different ways corresponding to our proposed protocols. To measure the exposure, we consider the probability that an attacker can reconstruct the plaintext table (or part of the table) by using the encrypted table and his prior knowledge about global distributions of plaintext attributes. Although the attacker does not know which encrypted column corresponds to which plaintext attribute, he can determine the actual correspondence by comparing their cardinalities. Namely, she can determine that IA, IC, and IB correspond to attributes Account, Customer, and Balance respectively. Then, the IC (the table of the inverse of the cardinalities of the equivalence classes) is formed by calculating the probability that an encrypted value can be correctly matched to a plaintext value.

For example, with Det_Enc, P(α = Alice) = 1 and P(κ = 200) = 1 since the attacker knows that the plaintexts Alice and 200 have the most frequent occurrences in the Accounts table (or in the global distribution) and observes that the ciphertexts α and κ have highest frequencies in the encrypted table respectively. The attacker can infer with certainty that not only α and κ represent values Alice and 200 (encryption inference) but also that the plaintext table contains a tuple associating values Alice and 200 (association inference). The probability of disclosing a specific association (e.g., <Alice,200>) is the product of the inverses of the cardinalities (e.g., P(<α,κ> = <Alice,200>) = P(α = Alice)× P(κ = 200) = 1). The exposure coefficient Ԑ of the whole table is estimated as the average exposure of each tuple in it:

Here, n is the number of tuples, k is the number of attributes, and ICi,j is the value in row i and column j in the IC table. Let's Nj be the number of distinct plaintext values in the global distribution of attribute in column j (i.e., Nj≤ n). Using nDet_Enc, because the distribution of ciphertexts is obfuscated uniformly, the probability of guessing the true plaintext of α is P(α = Alice) = 1/5. So, ICi,j = 1/Nj for all i, j, and thus the exposure coefficient of S_Agg is:

For the nearly equi-depth histogram, each hash value can correspond to multiple plaintext values. Therefore, each hash value in the equivalence class of multiplicity m can represent any m values extracted from the plaintext set, that is, there are different possibilities. The identification of the correspondence between hash and plaintext values requires finding all possible partitions of the plaintext values such that the sum of their occurrences is the cardinality of the hash value, equating to solving the NP-Hard multiple subset sum problem [START_REF] Ceselli | Modeling and assessing inference exposure in encrypted databases[END_REF]. We consider two critical values of collision factor h (defined as the ratio G/M between the number of groups G and the number M of distinct hash values) that correspond to two extreme cases (i.e., the least and most exposure) of ɛED_Hist: (1) h = G: all plaintext values collide on the same hash value and (2) h = 1: distinct plaintext values are mapped to distinct hash values (i.e., in this case, the nearly equi-depth histogram becomes Det_Enc since the same plaintext values will be mapped to the same hash value).

In the first case, the optimal coefficient exposure of histogram is:

because ICi,j = 1/Nj for all i, j. For the second case, the experiment in [START_REF] Ceselli | Modeling and assessing inference exposure in encrypted databases[END_REF] (where they generated a number of random databases whose number of occurrences of each plaintext value followed a Zipf distribution) varies the value of h to see its impact to ɛED_Hist. This experiment shows that the smaller the value of h, the bigger the ɛED_Hist and ɛED_Hist reaches maximum value (i.e., max(ɛED_Hist) ≈ 0.4) when h = 1.

For Noise_based algorithms, when nf = 0 (i.e., no fake tuples), Rnf_Noise becomes Det_Enc and therefore it has maximum exposure in this case. If nf is not big enough, since each TDS generates very few fake tuples, the transformed distribution cannot hide some ciphertexts with remarkable (highest or lowest) frequencies, increasing the exposure. The bigger the nf, the lower the probability that these ciphertexts are revealed. Exceptionally, when the noise is not random (but controlled by domain cardinality of AG), C_Noise has better exposure since all ciphertexts have the same frequency (ICi,j = 1/Nj for all i, j):

𝜀 𝐶_𝑁𝑜𝑖𝑠𝑒 = 1 (𝑛 𝑓 + 1) * 𝑛 ∑ ∏ 𝐼𝐶 𝑖,𝑗 𝑘 𝑗=1 (𝑛 𝑓 +1) * 𝑛 𝑖=1 = 1 𝑛 𝑑 * 𝑛 ∑ ∏ 1 𝑁 𝑗 𝑘 𝑗=1 𝑛 𝑑 * 𝑛 𝑖=1 = 1/ ∏ 𝑁 𝑗 𝑘 𝑗=1
The exposure coefficient gets the highest value when no encryption is used at all and therefore all plaintexts are displayed to attacker. In this case, ICi,j = 1 ∀ i, j, and thus the exposure coefficient of plaintext table is (trivially): The information exposures among our proposed solutions are summarized in Fig. 8. In conclusion, S_Agg is the most secure protocol. To reach the same highest security level as S_Agg, other protocols must pay a high price. Specifically, Rnf_Noise has to generate a very large amount of noise regardless of the value of G; C_Noise also incurs large noise if G is big; and ED_Hist must have a significant collision factor. Hence, as usual, there exists a trade-off between security and performance and the expected balance can be reached in each protocol by tuning a specific parameter (i.e., amount of noise in Rnf_Noise and C_Noise or number of histograms in ED_Hist).

_ 1 1 1 1 1 1/ k k n S Agg j i j j j N n N         j N m       _ 1 min( ) 1/ k ED Hist j j N     _ 1 1 1 1 1 k n P Text i j n      

Privacy Measure using Variance

In this section, we propose a stronger assumption that the adversary A possesses more knowledge of encrypted dataset than the previous section: A knows the entire bucketization scheme and the exact probability distribution of the values within each bucket. For example, given that bucket B has 10 elements, we assume A knows that:

3 of them have value 85, 3 have value 87 and 4 have value 95, say. However, since the elements within each bucket are indistinguishable, this does not allow A to map values to elements with absolute certainty. Then, the A's goal is to determine the precise values of sensitive attributes of some (all) individuals (records) with high degree of confidence. Eg: What is the value of salary field for a specific tuple? [START_REF] Hore | A Privacy-Preserving Index for Range Queries[END_REF] proposes the Variance of the distribution of values within a bucket B as its measure of privacy guarantee. They first define the term Average Squared Error of Estimation (ASEE) as follows.

Definition ASEE: Assume a random variable XB follows the same distribution as the elements of bucket B and let PB denote its probability distribution. For the case of a discrete (continuous) random variable, we can derive the corresponding probability mass (density) function denoted by pB. Then, the goal of the adversary A is to estimate the true value of a random element chosen from this bucket. We assume that A employs a statistical estimator for this purpose which is, itself a random variable, X'B with probability distribution P'B.

In other words, A guesses that the value of X'B is xi, with probability p'B(xi). If there are N values in the domain of B, then we define Average Squared Error of Estimation (ASEE) as:

𝐴𝑆𝐸𝐸(𝑋 𝐵 , 𝑋 𝐵 ′ ) = ∑ ∑ 𝑝 𝐵 ′ (𝑥 𝑖 ) 𝑁 𝑖=1 𝑁 𝑗=1 * 𝑝 𝐵 (𝑥 𝑗 ) * (𝑥 𝑖 -𝑥 𝑗 ) 2
Theorem [START_REF] Hore | A Privacy-Preserving Index for Range Queries[END_REF]]: ASEE(X, X') = Var(X) + Var(X') + (E(X) -E(X')) 2 where X and X' are random variables with probability mass (density) functions p and p0, respectively. Also Var(X) and E(X) denote variance and expectation of X respectively.

Proof: refer to [START_REF] Hore | A Privacy-Preserving Index for Range Queries[END_REF] X'B) in two ways: 1) by reducing Var(X'B) or 2) by reducing the absolute value of the difference E(XB) -E(X'B). Therefore, the best estimator of the value of an element from bucket B that A can get, is the constant estimator equal to the mean of the distribution of the elements in B (i.e., E(XB)). For the constant estimator X'B, Var(X'B) = 0. Also, as follows from basic sampling theory, the "mean value of the samplemeans is a good estimator of the population (true) mean". Thus, A can minimize the last term in the above expression by drawing increasing number of samples or, equivalently, obtaining a large sample of plaintext values from B. However, note that the one factor that A cannot control (irrespective of the estimator he uses) is the true variance of the bucket values, Var(XB). Therefore, even in the worst case scenario (i.e., E(X'B) = E(XB) and Var(X'B) = 0), A still cannot reduce the ASEE below Var(XB), which, therefore, forms the lowest bound of the accuracy achievable by A. Hence, the data owners try to bucketize data in order to maximize the variance of the distribution of values within each bucket. These two cases corresponds to the two extreme cases of nearly equi-depth histogram (when h = 1 and h = G) as analyzed below.

When h = 1 (Det_Enc), since each bucket contains only the same plaintext values, and with the assumption above about additional knowledge of adversary, he can easily infer that the expected value of X'B equals to that of XB: E(X'B) = E(XB). For the variance, with h = 1, the variance of X'B gets the minimum value Var(X'B) = 0 (because variance measures how far a set of numbers is spread out, a variance of zero indicates that all the values are identical). In this case, the value of ASEE equals to the lowest bound Var(XB).

When h = G, since all plaintext values collide on the same hash value, the difference between E(X' 2 B) -(E(X'B)) 2 is big, leading to the big value of Var(X'B). So, the value of ASEE approaches highest bound.

As you can see, although the coefficient exposure and average squared error of estimation are different ways to measure privacy of equi-depth histogram depending on the adversary's knowledge, they give the same result.

ANALYTICAL COST MODEL

This section proposes an analytical cost model for the evaluation of our protocols. We calibrate this model with basic performance measurements performed on a real hardware platform (see section 8.3). We also show in section 9 that this model is accurate when compared to real measures on a real system composed of a set of TDSs. Thus the objective of this section is to provide an analytical model to assess the efficiency of the deployment of a TDSs based infrastructure for a given application without having to set up such a costly experiment.

Metrics of interest

The metrics of interest in this evaluation are the following:

 MaxPTDS: The maximum number of TDSs concurrently needed in the computation. In different phases of the protocol, the optimal number of TDSs needed for the parallel computation varies and can exceed the number of connected TDSs available at that time (i.e., demanding resource is greater than available resource), reducing the parallelism degree. Nonetheless, this value should be considered to measure the parallelism level of the protocol.

 LoadQ: Global resource consumption for evaluating a query Q, expressed as the total size of data that all TDSs and SSI have to process. This metric reflects the scalability of the solution in terms of capacity of the system to manage a large set of queries in parallel and/or a large set of TDSs to be queried. It also provides a global view of the resource consumption (i.e., the bigger LoadQ, the more resource spent to process that data).  LoadAVG: Average load of all participating TDSs in the computation. While LoadQ reflects the global resource consumption, this metric reflects the local resource consumption (i.e., how much load that each TDS has to incur locally in average).

 LoadMAX: Maximum load of participating TDSs in the computation. Each TDS that participates in the computation incurs different load because the same TDS can participate in different steps of the protocol if connection time of that TDS is long enough. LoadMAX reflects the possible worst case of load that a TDS can incur. This is important to measure the feasibility of the protocol.

If LoadMax is too large, maybe no TDS will ever connect for long enough.  LoadBL: Load balance among participating TDSs in the parallel computation.

It is measured as the ratio of LoadMAX/LoadAVG. It reflects the protocol's ability to evenly divide and deliver the parallel tasks to connected TDSs.

 TQ: query response time, reflecting the responsiveness of the protocol. Since the time in the collection phase is application-dependent and is similar for all protocols, and since the time in the filtering phase is also similar for all protocols, TQ focuses on the time spent on the aggregation phase, which is actually the most complex phase.

 Tlocal: Average time that each participating TDS spends to compute the query.

This metric reflects the feasibility of the solution because the longer this time, (1) the lower the probability that TDS stays connected during this time and (2) the higher the burden for an individual to accept participating in distributed queries.

 sRAM: Size of RAM required in each participating TDS for the computation.

The above metrics can be classified into: (i) Local resource consumption, reflecting the resource consumed locally in each TDS; (ii) Global resource consumption, reflecting the global resource needed for the whole system to answer a query. The weight associated to each of these metrics is context-dependent, as discussed in Section 8.6. These metrics are computed based on the following main parameters which reflect the characteristics and resources of the architecture:

 Nt total number of encrypted tuples sent to SSI by TDSs (without loss of generality, we consider in the model that each TDS produces a single tuple in the collection phase, hence Nt reflects also the number of TDSs participating in the collection phase);

 PTDS: total number of TDSs that participate in the computation (depending on the protocol, not all connected TDSs may be involved in a computation);

 G number of groups;  st size of an encrypted tuple (this size depends on the schema of the database, number of attributes needed in the query, and size of each attribute);

 Tt time spent by each TDS to process one tuple (including transfer, cryptographic and aggregation time);  N i TDS number of TDSs that participate in the i th partial aggregation phase (protocol dependent);  α, nNB, nED, reduction factors in the aggregation phase in S_Agg, Noise_based and ED_Hist respectively;  nf number of fake tuples per true tuple in Noise_based protocols;  h average number of groups corresponding to each hash value in ED_Hist.

Secure Aggregation protocol

Because the aggregation phase is iterative, the time spent in this phase is the total time for all iterative steps. In the first step of this phase, the time required to download data from SSI and return temporary result is:

𝑡 1 = 𝑁 𝑡 𝑁 1
𝑇𝐷𝑆 * 𝑇 𝑡 (since there are total Nt number of tuples which are evenly divided to 𝑁 1 𝑇𝐷𝑆 connected TDSs); 𝑡 1 ′ = 𝐺 * 𝑇 𝑡 (since each TDS returns at most G tuples). Similarly, in step i of the aggregation phase, we have:

𝑡 𝑖 = 𝑁 𝑖-1 𝑇𝐷𝑆 𝑁 𝑖 𝑇𝐷𝑆 * 𝐺 * 𝑇 𝑡 ; 𝑡 𝑖 ′ = 𝐺 * 𝑇 𝑡 (i = 2 -n),
with n is the total number of iterative steps in this phase.

For simplicity, we assume that the reduction factor α in every step is similar:

𝛼 = 𝑁 𝑡 /𝐺 𝑁 1 𝑇𝐷𝑆 = 𝑁 1 𝑇𝐷𝑆 𝑁 2 𝑇𝐷𝑆 = ⋯ = 𝑁 𝑛-1 𝑇𝐷𝑆 𝑁 𝑛 𝑇𝐷𝑆 .
Since 𝑁 𝑛 𝑇𝐷𝑆 = 1 (there is only one TDS who computes the final aggregation), the number of iterative steps is

𝑛 = ⌈log 𝛼 𝑁 𝑡 𝐺 ⌉
The computation time of S_Agg is the total time of all iterative steps:

𝑇 𝑄 𝑆_𝐴𝑔𝑔 = ∑(𝑡 𝑖 + 𝑡 𝑖 ′ ) = [(𝛼 + 1) log 𝛼 𝑁 𝑡 𝐺 ] * 𝐺 * 𝑇 𝑡 𝑛 𝑖=1
To find the optimal time for aggregation phase, let f(α) = (α + 1)logα(Nt/G) (if Nt and G are fixed, the computation time of S_Agg is a function of α and therefore its optimal value depends on α)

We have:

df dα = α*lnα-(α+1) α*(lnα) 2 *ln ( N t G )
Solving the equation 𝑑𝑓 𝑑𝛼 = 0 gives α ≈ 3.6.

We call αop = 3.6 the optimal reduction factor (i.e., 𝑇 𝑄 𝑆_𝐴𝑔𝑔 gets the minimum value when αop = 3.6).

These other metrics are calculated as follows:

In each step, the participating TDSs reduces α times:

𝑃 𝑇𝐷𝑆 𝑆_𝐴𝑔𝑔 = ∑ 𝑁 𝑖 𝑇𝐷𝑆 𝑛 𝑖=1 = 𝑁 𝑡 𝐺 * ∑ 𝛼 -𝑖 𝑛 𝑖=1
The first step requires the most number of TDSs: 𝑀𝑎𝑥𝑃 𝑇𝐷𝑆 𝑆_𝐴𝑔𝑔 = 𝑁 𝑡

𝛼𝐺

The total size of data in all iterative steps:

𝐿𝑜𝑎𝑑 𝑄 𝑆_𝐴𝑔𝑔 = (𝑁 𝑡 + 𝛼𝐺 ∑ 𝑁 𝑖 𝑇𝐷𝑆 𝑛 𝑖=2 + 𝐺 ∑ 𝑁 𝑖 𝑇𝐷𝑆 𝑛 𝑖=1 ) * 𝑠 𝑡 = (1 + 2 ∑ 𝛼 -𝑖 𝑛 𝑖=1
) * 𝑁 𝑡 * 𝑠 𝑡 The maximum load of the TDS that participates in all iterative steps:

𝐿𝑜𝑎𝑑 𝑀𝐴𝑋 𝑆_𝐴𝑔𝑔 = (𝑛 + 1)𝛼𝐺 × 𝑠 𝑡
The average load of each TDS can be calculated by dividing the total load of all TDSs by the total number of participating TDSs:

𝐿𝑜𝑎𝑑 𝐴𝑉𝐺 𝑆_𝐴𝑔𝑔 = { (𝑁 𝑡 + 𝛼𝐺 ∑ 𝑁 𝑖 𝑇𝐷𝑆 𝑛 𝑖=2 ) 𝑃 𝑇𝐷𝑆 𝑆_𝐴𝑔𝑔 × 𝑠 𝑡 , 𝑖𝑓 𝑃 𝑇𝐷𝑆 𝑆_𝐴𝑔𝑔 < 𝑁 𝑡 (𝑁 𝑡 + 𝛼𝐺 ∑ 𝑁 𝑖 𝑇𝐷𝑆 𝑛 𝑖=2 ) 𝑁 𝑡 × 𝑠 𝑡 , 𝑖𝑓 𝑃 𝑇𝐷𝑆 𝑆_𝐴𝑔𝑔 ≥ 𝑁 𝑡

Noise_based protocols

Because all tuples belonging to one group may spread over multiple partitions, the aggregation phase includes two steps.

In the first step, each group contains (nf + 1) * Nt / G tuples in average, and we assume that there are nNB TDSs handling tuples belonging to one group. The time required to download data from SSI and return temporary result in this step is:

𝑡 1 = (𝑛 𝑓 +1) * 𝑁 𝑡 𝑛 𝑁𝐵 * 𝐺 * 𝑇 𝑡 ; 𝑡 1 ′ = 𝑇 𝑡 ;
In the second step, each TDS receives nNB tuples belonging to one group to compute the final aggregation, so the time required is:

𝑡 2 = 𝑛 𝑁𝐵 * 𝑇 𝑡 ; 𝑡 2 ′ = 𝑇 𝑡 ;
The computation time of Rnf_Noise is:

𝑇 𝑄 𝑅 𝑛𝑓 _𝑁𝑜𝑖𝑠𝑒 = (𝑛 𝑁𝐵 + (𝑛 𝑓 + 1) * 𝑁 𝑡 𝑛 𝑁𝐵 * 𝐺 + 2) * 𝑇 𝑡
Apply the Cauchy's inequality, we have:

𝑛 𝑁𝐵 + (𝑛 𝑓 + 1) * 𝑁 𝑡 𝑛 𝑁𝐵 * 𝐺 ≥ 2 * √ (𝑛 𝑓 + 1) * 𝑁 𝑡 𝐺
The computation time of Rnf_Noise gets optimal value when the optimal reduction factor is:

𝑛 𝑁𝐵 = √ (𝑛 𝑓 +1) *

Histogram-based protocol

Let's h be the average number of groups corresponding to each hash value. By applying the Cauchy's inequality and the same mechanism as in Rnf_Noise, the optimal computation time is: Then, the other metrics are based on these factors as follows: (𝑛 𝐸𝐷 /ℎ + 𝑚 𝐸𝐷 + 1) * 𝐺 Note that this is just a subset of the complete cost model which can be found in the technical report [START_REF] To | Secure Global Protocol in Personal Data Server[END_REF].

𝑇 𝑄(𝑜𝑝) 𝐸𝐷_𝐻𝑖𝑠𝑡 = (3 * √ ℎ * 𝑁 𝑡 𝐺 3 + ℎ + 2) * 𝑇 𝑡
𝑃 𝑇𝐷𝑆 𝐸𝐷_𝐻𝑖𝑠𝑡 = ( 𝑛 𝐸𝐷 ℎ + 𝑚 𝐸𝐷 + 1) * 𝐺 𝑀𝑎𝑥𝑃 𝑇𝐷𝑆 𝐸𝐷_𝐻𝑖𝑠𝑡 = 𝑚𝑎𝑥 { 𝑛 𝐸𝐷 ℎ × 𝐺,

Sample size in the collection phase

Let us consider a nation-wide study, taking the population of France, popm = 65*10 6 , as a representative example. We fix φ = 1.96 for 95% confidence level (the most popular value used in statistics). We assume there are 10% people who do not want to answer the query (i.e., optout = 10%). We vary two parameters to see their impact to the sample size required in the collection phase: λ = 0.05, 0.01, 0.005, 0.002, 0.001; the variance ζ 2 = 5, 10, 20, 50, 100. As shown in Fig. 11, the higher the precision of the query result and the bigger the variability of the dataset, the higher the number of data we need to collect and therefore the longer the collection time that querier has to wait for and vice versa. For instance, if the querier wants 0.2% precision and the dataset has high variability, he has to wait until almost all the dataset is collected. However, if the querier queries low variable dataset, or if he does not want high precision, collecting only 10% or even 1% of the population is enough. Note that our system also supports opinion poll quota methods.

Unit test

To calibrate our model, we performed unit tests on the development board presented in Fig. 12a. This board exhibits hardware characteristics representative of secure tokens-like TDSs, including those provided by Gemalto (the smartcard world leader), our industrial partner. This board has the following characteristics: the microcontroller is equipped with a 32 bit RISC CPU clocked at 120 MHz, a cryptocoprocessor implementing AES and SHA in hardware (encrypting or decrypting a block of 128bits costs 167 cycles), 64 KB of static RAM, 1 MB of NOR-Flash and is connected to a 1 GB external NAND-Flash and to a smartcard chip hosting the cryptographic material. The device can communicate with the external world through USB full speed. The speed in theory is 12 Mbps but the real speed measured with the device is around 7.9 Mbps. We measured on this device the performance of the main operations influencing the global cost, that is: encryption, decryption, hashing, communication and CPU time, and put these numbers as constants in the formulas. Fig. 12b depicts the internal time consumption of this platform to manage partitions of 4KB. The transfer cost dominates the other costs due to the network latencies. The CPU cost is higher than cryptographic cost because (1) the cryptographic operations are done in hardware by the crypto-coprocessor and (2) TDS spends CPU time to convert the array of raw bytes (resulting from the decryption) to the number format for calculation later. Encryption time is much smaller than decryption time because only the result of the aggregation of each partition needs to be encrypted.

Other TDSs (e.g., smart meters) may be more powerful than smart tokens, although client-based hardware security is always synonym of low power. Anyway, as this section will make clear, the internal time consumption turns out not to be the limiting factor. Hence our choice of considering low-power TDSs in this experiment is expected to broaden our conclusions.

Performance comparisons

In this study, we concentrate on the performance of Group By queries since they are the most challenging to compute. We vary the dataset size (Nt varies from 5 to 65 million), the number of groups (G varies from 1 to 10 6 ) as well as the number of TDSs participating in the computation as a percentage of all TDSs connected at a given time (varying from 1% to 100%). For each study, we fix two parameters and vary the others. When the parameters are fixed, Nt=10 6 , G=10 3 ,st=16b, Tt=16μs, h=5 and the percentage of TDS connected is 10% of Nt. We also compute and use the optimal value for all reduction factors as well as for N i TDS . In the figures, we plot two curves for Rnf_Noise protocols, R2_Noise (nf = 2) and R1000_Noise (nf = 1000) to capture the impact of the ratio of fake tuples. We summarize below the main conclusions of the performance evaluation. A more detailed study is provided in a technical report [START_REF] To | Secure Global Protocol in Personal Data Server[END_REF].

In what follows, we study each of the aspects of the protocol that seem important. We draw conclusions on the use cases for each protocol in section 8.6.

Parallelism requirement (MaxPTDS).Fig. 13a presents MaxPTDS with varied G. Since S_Agg does not need too many TDSs for parallel computing, the demand of connected TDSs for computation is almost satisfied. Unlike S_Agg, the other solutions need a lot of TDSs for the parallel computation, and when G increases to a specific point, the available resource does not meet these demands, reducing the parallel deployment of these solutions. In Fig. 13b, when G is not too big (i.e., Resource consumption (LoadQ). Fig. 13c and13d show LoadQ respectively in terms of G and Nt. Not surprisingly, the total load of Noise_based protocols is highest because of the extra processing incurred by fake tuples. However, nf depends only on Nt, so when G increases, the total load of Noise_based protocols remains constant.

Other protocols generate much lower and roughly comparable loads. In general, in Maximum load (LoadMAX). The maximum load of a particular TDS is illustrated in Fig. 13e. In S_Agg, when G increases, due to the increasing size of partial aggregation, each TDS has to process bigger aggregation, resulting in the increase of LoadMAX. Also, when G increases, the number of participating TDSs decreases, so each participating TDS has to incur higher load. For others, when G increases, since Nt remains unchanged, the number of tuples in each group decreases and the number of participating TDSs increases. Consequently, each TDS processes less tuples, and thus LoadMAX decreases. In other words, the parallel level in this case is high, reducing the maximum load that a particular TDS incurs. In Fig. 13f, when Nt increases, the number of participating TDSs also increases proportionally. So, in general, the LoadMAX remains stable except a slight increase in R1000_Noise and C_Noise.

Average load (LoadAVG). Fig. 13g is the average load of every participating TDS. In S_Agg, since the total load stays almost constant and the number of participating TDSs declines steeply when G increases, the average load goes up. In the R1000_Noise and C_Noise, the high total load is constant and all available connected TDSs participate in the computation when G varies from 10 3 -10 6 , thus every TDSs incur the same amount of load. For the rest, LoadAVG decreases when G increases, because there is more number of participating TDSs but the total load is almost unchanged.

In Fig. 13h, although C_Noise has higher LoadQ than S_Agg, the number of participating TDSs in S_Agg is much less than that in C_Noise, and therefore the LoadAVG of C_Noise is less than that of S_Agg.

Load balance (LoadBL). than R2_Noise since each TDS has to process a partition including h groups while in R2_Noise a partition composes of only one group. Query response time (TQ). Fig. 13k shows the impact of G over TQ. In all protocols but S_Agg, TQ depends on the total number of tuples in each group (resp. bucket for ED_Hist) because all groups (resp. buckets) are processed in parallel. Hence, when G increases while Nt remains constant, the number of tuples in each group (resp. bucket) decreases and so does TQ. In S_Agg, when G increases, the size of each partial aggregation increases accordingly, and so does the time to process it and in consequence, so does TQ. Fig. 13l shows that, for ED_Hist, when Nt increases, the number of TDSs which can be mobilized for processing increases accordingly, leading to a minimal impact on execution time. This statement is true also for Rnf_Noise protocols with the difference that the greater number of fake tuples generates extra work which is not entirely absorbed by the increase of parallelism. For S_Agg, the number of iterative steps increases with Nt and so does TQ.

Local execution time (Tlocal). Fig. 13m and 13n plot the average execution time of every participating TDSs varying G and Nt respectively. It shows that all protocols benefit from an increase of G except S_Agg. This is due to the fact that, in S_Agg, less TDSs can participate in the parallel computation, and therefore each TDS has to process a higher load of bigger partial aggregations. Other protocols benefit from the fact that the computing load is shared evenly between TDSs. Fig. 13n shows that all protocols but Noise_based protocols are insensitive to an increase of Nt again thanks to independent parallelism. The bad behavior of Noise_based protocols is explained by the fact that the number of fake tuples increases linearly with Nt and this increased load cannot be entirely absorbed by parallelism because the number of TDSs available for the computation is bounded in this setting by 10% of the participating TDSs.

Throughput. In general, throughput is the amount of work that a computer can do in a given period of time. Applied in our case, throughput is measured as the number of queries that our distributed system can answer in a given time period, reflecting the efficiency of our protocols (cf., Fig. 13o and13p). In Fig. 13o, when G increases, the number of participating TDSs for each query increases and the execution time for each query does not reduce considerably, resulting in the reduction of throughput for all solutions. The throughput of S_Agg, however, increases because PTDS reduces much faster than the execution time for each query when G increases. In Fig. 13p, when Nt increases, the throughput remains constant for all solutions due to the proportional increase of participating TDSs. The ED_Hist solution has the highest throughput because it needs least participating TDSs and shortest execution time for each query. For S_Agg, although the response time for each query is long, the PTDS is very low, resulting in high throughput. For the R1000_Noise, since it not only demands very high number of PTDS (to process fake tuples), but also responses slowly for each query, its throughput is worst. Elasticity issues. A distributed and parallel system is said to be elastic if it can mobilize smoothly a variable part of its computing resources to meet run time requirements. Fig. 13q,r, k measures the elasticity of all protocols by varying the computing resource and assessing its impact on TQ. The computing resource is materialized here by the number of TDSs which can be mobilized to contribute to a given computation. It is expressed by a percentage of the TDSs contributing to the collection phase. Fig. 13q (resp. Fig. 13r, Fig. 13k) considers scarce (resp. abundant, intermediate) computing resource in the sense that only 1% (resp. 100%, 10%) of the TDSs contributing to the collection phase contributes to the rest of the query computation. Comparing these figures shows that, when the resource is scarce, the parallel computation is not completely deployed, resulting in a longer time to answer the query and vice-versa. Since S_Agg does not depend on the number of available TDSs (but on G and on the memory size of TDS), its performance is not impacted by a fluctuation of the resource available. In other words, S_Agg has lowest elasticity.

Memory size. Fig. 13s details the memory's size required for the computation in each TDS when G is varied. Because the only factor that impacts the memory's size requirement is G but not Nt, we assess this metric by varying only G. The Noise_based solutions require least memory because each partition sent to TDS contains tuples belonged to only one group due to the Det_Enc, and thus TDSs store only one group in memory regardless of the value of G. The ED_Hist requires more memory because each TDS needs to process the partition having the same hash value and each hash value corresponds to multiple (i.e., h) groups in the first aggregation phase. The S_Agg needs highest memory because each TDS has to store the whole partial aggregation (which includes many groups) in the RAM. So, when G increases, the memory needed for storing the whole aggregation also increases linearly. When G is too big (i.e., G >1000), the sRAM exceeds the actual RAM's size of TDS, and thus S_Agg is not feasible in this case 15 .

Comparison with State of the Art

In order to provide a baseline comparison in terms of performance (and not security), Fig. 13t compares the performance of S_Agg, our most secure solution, with serverbased solutions working on encrypted data. We consider the performance of two wellknown encryption schemes, a symmetric one (i.e., DES) and a homomorphic one (i.e., Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]]), as measured in [START_REF] Ge | Answering aggregation queries in a secure system model[END_REF]. In DES method, each value is decrypted on the server and the computation is performed on the plaintext. Clearly this method is not a viable solution in our security model, because the database server must have access to the secret key or plaintext to answer the query, violating the security requirements. In Paillier's method, the secure modern homomorphic encryption scheme, which typically operates on a much larger (encryption) block size (say 2K bits) than single numeric data values, is used to densely pack data values in an encryption block. Then, the database server performs the computation directly on ciphertext blocks which are then passed back to a trusted agent (i.e., the Key Holder) to perform a final decryption and simple calculation of the final result. The strength of this method is due to the dense packing of values to reduce the number of modular multiplications and the minimization of the number of expensive decryption operations. We refer to the author's experimentations, which were run on now outdated hardware 16 , since both methods were implemented in C-Store 17 which was run on a Linux workstation with an AMD Athlon-64 2Ghz processor and 512 MB memory [START_REF] Ge | Answering aggregation queries in a secure system model[END_REF]. We also compare its performance with C-Store using no encryption at all. We ran an AVG query varying G and the database size. The result (Fig. 13t) shows that, with homomorphic encryption scheme (generalized Paillier), C-Store runs slightly faster than using DES for encryption due to the saving in the decryption cost during execution. Although these algorithms are a little dated, the objective is simply to provide a baseline comparison, to show the effectiveness of our approach and demonstrates the strength of large-scale parallel computation even when modest hardware is available on the participant's side. Fig. 13t matches this objective explicitly.

8.6

Conclusion: Trade-off between criteria Fig. 14 summarizes and complements the experimental results described above through a qualitative comparison of our proposed protocols over all criteria of interest to perform a choice. Tlocal metrics and compares the protocols in terms of feasibility, i.e., is the resource consumed by a single TDS compatible with the actual computing power of the targeted TDSs. This question is particularly relevant for low-end TDSs (e.g., smart tokens) and of lesser interest for high-end TDSs. S_Agg is at the worst extremity of this axis because the final aggregation must be done by a single TDS while ED_Hist occupies the other extremity thanks to its capacity to evenly share the load among all TDSs. That also explains why in Load Balance axis ED_Hist better balances the load among TDSs than S_Agg. Noise_based protocols are in between because they also share the load evenly but at the price of managing a large number of fake tuples.

Note that the relative position of S_Agg and ED_Hist is reversed in the Global Resource Consumption and Satisfied Level of Parallel Deployment axis which refers to LoadQ and MaxPTDS metrics and compares the scalability of the protocols in terms of number of parallel queries which can be computed and their ability of fully parallel computation, respectively. Indeed, the total number of TDSs mobilized by S_Agg for one single query computation is much smaller than that of ED_Hist. This figure makes clear that Noise_based protocols are always dominated either by S_Agg or ED_Hist and should be avoided. However, choosing between the other two depends on the application's characteristics, and Fig. 14 should be used to decide. Let us consider a first scenario where individuals manage their data (e.g., their medical folder) using a secure Personal Data Server embedded in a smart token-like TDS [START_REF] Allard | Secure Personal Data Servers: a Vision Paper[END_REF]]. In such a scenario, individuals are likely to connect their TDS seldom, for short periods of time (e.g., when visiting a doctor) and would prefer to save resource for executing their own tasks rather than being slowed down by the computation of external queries. According to Fig. 14, ED_Hist best matches the above requirements. Conversely, let us consider a smart metering platform composed of power meter-like TDSs, connected all the time and mostly idle. In this case, TDSs' owners do not care how much resources are monopolized to compute queries and the primary concern is for the distribution company to maximize the capacity to perform global computation. S_Agg is more appropriate in this case. In short, ED_Hist and S_Agg are the two best solutions and the final choice depends on the weight associated to each axis for a given application.

PERFORMANCE MEASUREMENTS ON REAL HARDWARE

To test the accuracy of our proposed cost models given in previous section, we compare the values taken from experiments conducted on real hardware with that of the cost models.

Experiment Setting

This section experimentally verifies the proposed cost models using 20 ZED secure tokens18 (Fig. 15) playing the role of a pool of TDSs used during the processing phase (i.e., after the collection phase has been performed). The experiment is tested on a Centrino Core 2 Duo PC with 2.4 Ghz CPU and 4Gbytes RAM, playing the role of SSI. The 20 ZED tokens communicate with the PC through USB port (Fig. 16). We verify our cost models on (i) Query response time (TQ), (ii) Resource consumption (LoadQ), (iii) Local execution time (Tlocal) and (iv) Load balance (LoadBL) among tokens. The low number of tokens has an influence on a certain number of results, but overall our prototype demonstrates that the cost model is accurate. When Nt varies up to one million, G is fixed at 100, and when G varies from 50 to 400 groups, Nt is fixed to one million tuples.

Comparison

In the following figures, for each metric, the first graph represents the real absolute value measured using the 20 ZED tokens while the second graph represents the relative error between these real values and the values predicted by the cost model. This second graph captures the accuracy of our cost model. The first set of experiments verifies the correctness of the query response time.

Figure 17a plots TQ varying G. The Noise protocol has the longest execution time due to fake tuples, and S_Agg runs longer than ED_Hist since each token has to process large partial aggregation. This observation is similar to that in figure 13k, giving a maximum estimation error under 7% in figure 17b. When Nt varies, TQ increases linearly in figure 17c, similarly to figure 13l. However, the increase rate of figure 17c is bigger than that of figure 13l because in the case of 20 participating tokens, parallelism is not fully deployed due to the limited number of tokens. On the contrary, in figure 13l where we have many participating TDSs, the parallel computation is completely deployed, resulting in a lower increase rate when the data load increases. The maximum error is around 10% in figure 17d.

Figures 17 e-h show the resource consumption error rate. Similar to figure 13c, all protocols in figure 17e incur constant loads (except a very small increase in case of S_Agg) when G varies because the total number of tuples is fixed. This gives a very low error rate for ED_Hist and Noise protocols (around 2%) and a rather low error rate for S_Agg (less than 8%). Similarly, the variation of Nt yields the linear increase of LoadQ in both figures 13d and 17g, giving an accurate result (around 2%-3% error) in figure 17h. of the aggregations depends on G). In contrast, when G increases in figure 13m, the number of participating tokens also increases, reducing the average connecting time for each token to process less load. Notice that when G increases over 1000 in figure 13m, the Tlocal of C_Noise and R1000_Noise also remains constant since the number of connecting TDSs is less than the required TDSs to fully deploy parallel computation.

We believe this explanation reinforces the credibility of our cost model since this trend repeats in figure 17i. When varying Nt, all protocols increase linearly in the experiment (figure 17k), while they remain unchanged in the cost model (figure 13n), except for Noise protocols. The reason of this difference is that when the total load increases while the number of tokens remain fixed (figure 17k), or when the number of tokens increases but does not meet the demand for an optimal parallel computing (Noise protocols in figure 13n), each token has to connect longer to process a bigger load. This is not the case for S_Agg and ED_Hist in the cost model since the increase rate of total load is less than that of connecting TDSs (in the cost model we assume that the percentage of connected TDSs is 10% of Nt).

Figure 17m displays the error rate of load balance among tokens. Since the total load is divided evenly among twenty tokens, the load balance remains at approximately 1 because all twenty tokens incur nearly the same load, yielding extremely accurate prediction (with maximum error less than 2% in figure 17n, except for S_Agg). Similarly, when Nt varies in figure 17o, Noise and ED_Hist have better load balance than S_Agg since some tokens in S_Agg have to process big aggregations to produce the final result. This observation conforms to the figure 13j where S_Agg has also the most unbalanced load among protocols.

As a summary of this section, although we can measure some differences between the cost model predictions and the real measurements, the error rate remains around few percents and the trends of all graphs in figure 17 are similar to the trends observed in figure 13. We believe the differences arise mostly from the inability to fully deploy the parallel computation due to limited connecting TDSs in the experiments. We plan on experimenting on larger sets of tokens in the future.

Scalability of the System

To test the ability of our system to scale up to millions of tokens in real life applications, we measure its speedup when increasing the number of tokens. Specifically, the speedup of our system is measured as follow: S(n) = T(1)/T(n) with T(n)being the execution time using n tokens.

We vary the number of tokens to measure the execution time in figure 17q. From that, we calculate the speedup when doubling the number of tokens each time.

In figure 17r, the speedup approaches 12x when we use 16 tokens. When the number of tokens doubles, the average speedup ratios of S_Agg, Noise and EDHist are 1.82, 1.81 and 1.83 respectively. These speedup ratios let us expect that our system should be able to scale to millions of tokens (given an equivalent increase in power of the SSI) in real applications with reasonable execution time and speedup.

This result is not surprising considering that all protocols exhibit mainly independent parallelism.

CONCLUSION

An ever increasing amount of personal data is collected and ends-up on servers. Decentralized architectures, devised to help individuals better protect their privacy, hinder global treatments and queries, impeding the development of services of great interest. This article presents a first attempt to fill this gap. It capitalizes on secure hardware advances promising soon the presence of a Trusted Execution Environment at low cost in any client device (trackers, smart meters, sensors, cell phones and other personal devices).

Based on this statement, we have proposed new query execution protocols to compute general SQL queries while maintaining strong privacy guarantees. The objective was not to find the most efficient solution for a specific problem but rather to perform a first exploration of the design space. We proposed three very different protocols and compared them according to different axes. The encouraging conclusion is that a good performance/security trade-off can be found in many situations and that the proposed protocols can scale up to nation-wide contexts.

We expect that this work will pave the way for the definition of future fully decentralized privacy-preserving querying protocols. The main research directions we foresee are: (1) extend the threat model to (a small number of) compromised TDSs and (2) perform performance study on large scale TDS platforms. The on-going deployment of very large TDS platforms (e.g., the Linky power meters installed by EDF in France or the growing interest for PCEHR hosted in secure tokens) would enable point (2) while providing a strong motivation to investigate issue (1).

ELECTRONIC APPENDIX

The electronic appendix for this article can be accessed in the ACM Digital Library.

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

Fig. 1 .

 1 Fig. 1. Different scenarios of TDSs Consequently, we assume that the querier can issue the following form of SQL queries 8 , borrowing the SIZE clause from the definition of windows in the StreamSQL standard [StreamSQL 2015]. This clause is used to indicate a maximum number of tuples to be collected, and/or a collection duration. SELECT <attribute(s) and/or aggregate function(s)> FROM <Table(s)> [WHERE <condition(s)>] [GROUP BY <grouping attribute(s)>] [HAVING <grouping condition(s)>] [SIZE <size condition(s)>] For example, an energy distribution company would like to issue the following query on its customers' smart meters: "SELECT AVG(Cons) FROM Power P, Consumer C WHERE C.accomodation='detached house' and C.cid = P.cid GROUP BY C.district HAVING Count(distinct C.cid) > 100 SIZE 50000". This query computes

  Execution of SQL on a Secure Decentralized Architecture39:5 ACM Transactions on Database Systems, Vol. xx, No. xx, Article xx, Publication date: Month YYYY

Fig. 2 .

 2 Fig. 2. Trusted Data Servers

.

  Fig. 3. The Asymmetric ArchitectureSince TDSs have limited storage and computing resources and they are not necessarily always connected, an external infrastructure, called hereafter Supporting Server Infrastructure (SSI), is required to manage the communications between TDSs, run the distributed query protocol and store the intermediate results produced by this protocol. Because SSI is implemented on regular server(s), e.g., in the Cloud, it exhibits the same low level of trustworthiness, high computing resources, and availability.

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY the execution of general SQL queries, considers a traditional access control model and does not rely on a secure server.

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

Filtering

  phase: (step 5) SSI partitions the Covering Result with the objective to let several TDSs manage next these partitions in parallel. The Covering Result being fully encrypted, SSI sees partitions as uninterpreted chunks of bytes; (step 6) connected TDSs download these partitions. These TDSs may be different from the ones involved in the collection phase; (step 7) each of these TDS decrypts the partition and filters out dummy tuples; (step 8) each TDS sends back the true tuples encrypted with key kQ to SSI, which finally concatenates all results and informs the querier that she can download the result (step 9).

Fig. 4 .

 4 Fig. 4. Select-From-Where querying protocolInformally speaking, the accuracy, security and efficiency properties of the protocol are as follows:

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY produces a Covering Result containing a single (encrypted) aggregated tuple for each group.

Fig. 5 .

 5 Fig. 5. Group By querying protocol

ALGORITHM 1 .

 1 Secure Aggregation: S_Agg (kQ, kT, Q, α) Input: (TDS's side): The cryptographic keys (kQ, kT), query Q from Querier. (SSI's side): reduction factor α (α ≥ 2). Output: The final aggregation Ωfinal. Notations: encrypted partial aggregation Ω e ; Total number of partitions n e Ω Non-deterministic encryption/decryption with key kT nEkT()/nEkT -1 (); The aggregation operator ⨢ to aggregate tuples having the same AG; begin Collection phase Each connected TDS sends a tuple of the form tup e = nEkT(tup) to SSI end begin Aggregation phase SSI side repeatRandomly choose tup e or Ω e to form partitions repeat Send these partitions to connected TDSs until all partitions in SSI have been sentReceive Ω e from TDSs until n Decrypt partition: tup ← nEkT -1 (tup e ); (or Ω e ): Ω←nEkT -1 (Ω e ) Add to its partial aggregation: Ω = Ω⨢ tup ; or Ωnew = Ωold⨢ Ω Encrypt its partial aggregation: Ω e ← nEkT(Ω)Send Ω e to SSI endwhile end Filtering phase //evaluate HAVING clause return nEkQ(Ωfinal) by SSI to Querier;

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

Fig. 6 .

 6 Fig. 6. (iterative partial) aggregationSecurity. In all phases, the information revealed to SSI is a sequence of tuples or value pairs (i.e., tup e and Ω e ) encrypted non-deterministically (nDet_Enc) so that SSI cannot conduct any frequency-based attack.Efficiency. The aggregation process is such that the parallelism between TDSs decreases at each iteration (i.e., α = N 1 TDS N 2 TDS = ⋯ = N n-1 TDS N n TDS , with 𝑁 𝑖 𝑇𝐷𝑆 being the number of TDSs that participate in the i th partial aggregation phase), up to having a single TDS producing the final aggregation (i.e., 𝑁 𝑛 𝑇𝐷𝑆 = 1). The cost model is proposed in section 8 to find the optimal value for the reduction factor 𝛼. Note again that incoming partitions are managed in streaming because the cost to download the data significantly dominates the rest. Suitable queries. Because of the limited RAM size, this algorithm is applicable for the queries with small G such as Q1: SELECT AVG(Cons) FROM Power P, Customer C WHERE C.City='Paris' and C.cid=P.cid GROUP BY C.district (Paris has only 20 districts) or Q2: SELECT COUNT(*) FROM Customer C WHERE 25 < C.Age and C.Age < 45 GROUP BY C.Gender.

ALGORITHM 2 .

 2 Random noise: Rnf_Noise (kQ, kT, Q, nf) Input: (TDS's side): the cryptographic keys (kQ, kT), query Q from Querier. Output: The final aggregation Ωfinal. Notation: EkT()/EkT -1 () deterministic encryption/decryption with key kT begin Collection phase Each connected TDS sends (nf + 1) tuples of the form tup e = (EkT(AG),nEkT(ĀG) to SSI end begin Aggregation phase SSI side repeat Group data with the same EkT(AG) to form partitions repeat Send these partitions to connected TDSs until all partitions in SSI have been sent Receive [EkT(AG),nEkT(AGG)] from TDSs until n e Ω = 1 send term←true to TDS TDSs side term ← false while (term = false) Reset [AG, AGG] = 0 Receive partition from SSI Decrypt tupe: AG← EkT -1 (A e G); ĀG← nEkT -1 (Ā e G) Filter false tuples Compute aggregate for AG: [AG, AGG] Encrypt aggregate: [EkT(AG),nEkT(AGG)] Send [EkT(AG),nEkT(AGG)] to SSI endwhile end Filtering phase //evaluate HAVING clause return nEkQ(Ωfinal) to Querier by SSI;

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY potentially very high number of fake tuples (the value is algorithm and data dependent).

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

.

  Scheme (BES)[START_REF] Castelluccia | Efficient Aggregation of Encrypted Data in Wireless Sensor Networks[END_REF] requires that all participants have a shared

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY sample values are within two standard deviations of the true population value (e.g., mean).

Fig. 7 .

 7 Fig. 7. Encryptions and IC tables

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

  Fig 8. Information exposure among protocols

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY 8.1.1

Finally, the average

  time of each TDS is the division of total time by total number of TDSs:

  when the reduction factors in each step are:

Fig. 11 .

 11 Fig. 11. Estimated sample size

Fig. 12 .

 12 Fig. 12. Hardware device & its internal time consumption

.

  ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY G=1000), most of the protocols can fully deploy the parallel computation (except R1000_Noise).

Fig. 13d ,

 13d Fig. 13d, LoadQ increases steadily due to the increase of Nt.

Fig

  Fig. 13. Performance evaluations

.

  Fig. 13i and 13j presents the load balance of solutions. Because of the low parallelism, S_Agg is the most unbalanced protocol. R2_Noise divides the load evenly among participating TDSs. ED_Hist has worse load balance m) ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

Fig. 14 .

 14 Fig. 14. Comparison among solutions Each axis can be interpreted as follows. Local resource consumption axis refers to

Fig. 15 .Fig. 16 .

 1516 Fig. 15. ZED Token (front & back)

.

  Fig. 17. Performance and error rate

2 Select-From-Where statements

	], i.e., exploiting prior knowledge about the
	data distribution to infer the plaintext values of ciphertexts. Depending on the
	protocols (see later), two kinds of encryption schemes will be used to prevent
	frequency-based attacks. With non-deterministic (aka probabilistic) encryption,
	denoted by nDet_Enc, several encryptions of the same message yield different
	ciphertexts while deterministic encryption (Det_Enc for short) always produces the
	same ciphertext for a given plaintext and key [Bellare et al. 2007]. Whatever the
	encryption scheme, symmetric keys must be shared among TDSs: we note kQ the
	symmetric key used by the querier and the TDSs to communicate together and kT the
	key shared by TDSs to exchange temporary results among them. We can choose
	either a different kQ per querier, or a different kQ per query. Note that these keys
	may also change over time and the way they are delivered to TDSs (and how much
	this costs) is discussed more deeply in section 6.
	4.Let us first consider simple SQL queries of the form:
	SELECT <attribute(s)> FROM <Table(s)> [WHERE <condition(s)>] [SIZE <size
	condition(s)>]
	These queries do not have a GROUP BY or HAVING clause nor involve aggregate
	functions in the SELECT clause. Hence, the selected attributes may (or may not)

  Private and Scalable Execution of SQL on a Secure Decentralized Architecture39:17 ACM Transactions on Database Systems, Vol. xx, No. xx, Article xx, Publication date: Month YYYY ALGORITHM 3. Histogram-based: ED_Hist (kQ, kT, Q) Input: (TDS's side): the cryptographic keys (kQ, kT), query Q from Querier. Output: The final aggregation Ωfinal.

	Call distribution discovering algorithm to discover the distribution
	begin Collection phase
	Each connected TDS sends a tuple of the form tup e = (h(AG),nEkT(ĀG)) to SSI.
	// h(AG) is the mapping function applied on the AG.
	end
	begin First aggregation phase
	SSI side
	Group tup e with the same h(AG) to form partitions
	repeat
	Send these partitions to connected TDSs
	until all partitions in SSI have been sent
	send term←true to TDS
	TDSs side
	term← false
	while (term = false)
	Reset[AGi, AGGi] = 0
	Receive partition from SSI
	Decrypt tupe: AG← h -1 (A e G); ĀG← nEkT -1 (Ā e G)
	Compute aggregate for h(AG): [AGi, AGGi]
	Encrypt aggregate: [EkT(AGi),nEkT(AGGi)]
	Send [EkT(AGi),nEkT(AGGi)] to SSI
	endwhile
	end
	begin Second aggregation phase
	SSI side
	repeat
	Group data with the same EkT(AG) to form partitions
	repeat
	Send these partitions to connected TDSs
	until all partitions in SSI have been sent
	Receive [EkT(AG),nEkT(AGG)] from TDSs
	until n e Ω = 1
	send term←true to TDS
	TDSs side
	term ← false
	while (term = false)
	Reset[AG, AGG] = 0;
	Receive partition from SSI
	Decrypt tupe: AG← EkT -1 (A e G); AGG ← nEkT -1 (AGG e )
	Compute aggregate for only group AG: [AG, AGG]
	Encrypt aggregate: [EkT(AG),nEkT(AGG)]
	Send [EkT(AG),nEkT(AGG)] to SSI
	endwhile
	end
	Filtering phase //evaluate HAVING clause
	return nEkQ(Ωfinal) to Querier by SSI;

  ]. Note that unlike coefficient exposure, the smaller value of ASEE implies the

bigger security breach because the distance between guessed values and actual values is smaller, and vice versa. So the adversary tries to minimize ASEE as much as he can. From the theorem above, it is easy to see that A can minimize ASEE(XB, 39:26 . ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY

  It turns out that S_Agg outperforms DES and Paillier when the number of grouping attributes is (i.e., G ≤ 1000) since it can exploit the parallel calculation of TDSs to speed up the computation and becomes worse after this threshold.

15

Swapping between FLASH memory and RAM is used in this case

16

However, this hardware is still orders of magnitude superior to the secure tokens we use.

17

http://db.csail.mit.edu/projects/cstore/ 39:36 . ACM Transactions on Database Systems, Vol. xx, No. x, Article x, Publication date: Month YYYY small

  Regarding the Responsiveness axis, the relative ordering of S_Agg and ED_Hist actually differs According to Fig.13, S_Agg outperforms ED_Hist for small G (smaller than 10) and is dominated by ED_Hist for larger G. Finally, Elasticity axis is a direct translation of the conclusions drawn in Section 8.4 and Confidentiality axis recalls the conclusion of Section 7.

	depending on G.
	Load Balance
	worst				best
	S_Agg	R1000_Noise C_Noise	ED_Hist	R2_Noise
	Feasibility, Local Resource Consumption
	worst				best
	S_Agg, R1000_Noise	C_Noise	R2_Noise	ED_Hist
	Responsiveness (large G)
	worst				best
	S_Agg	R1000_Noise C_Noise	R2_Noise	ED_Hist
	Responsiveness (small G)
	worst				best
	R1000_Noise C_Noise	R2_Noise	ED_Hist	S_Agg
	Global Resource Consumption,Satisfied Level of Parallel Deployment
	worst				best
	R1000_Noise C_Noise	ED_Hist	R2_Noise	S_Agg
	Confidentiality
	worst				best
	Cleartext		Noise_based, ED_Hist	S_Agg
	Elasticity
	worst				best
	S_Agg	R2_Noise	ED_Hist	C_Noise	R1000_Noise

http://www.greenbuttondata.org/

http://healthit.gov/patients-families/your-health-data

This is the case in France for instance.

As stated in the introduction, we do not consider joins between data stored in different TDSs in this article, the solution to this specific problem being addressed in[To et al. 2015a]. However, there is no

For illustration purpose, the secure device considered in our experiments is made of a tamper-resistant microcontroller connected to a Flash memory chip.

Connected TDSs actually download all queries and decrypt them to check whether they can contribute to them or not. The SSI cannot perform this task since queries are encrypted.

The objective is to hide which TDSs satisfy the Where clause of the query in the case SSI and Querier collude.

The production of dummy tuples may slightly impact the evaluation of the SIZE clause. The Querier must thus oversize this parameter according to his perception of the selectivity of the query and the percentage of TDSs opting-out for the query. If this over sizing turns out to be insufficient, the query could need to be rerun. Note anyway that the SIZE limit is a coarse parameter in the open world assumption.

ACM Transactions on Database Systems, Vol. xx, No. xx, Article xx, Publication date: Month YYYY

These secure tokens are used in different universities and FabLabs in France and will be soon distributed under an openhardware license. In terms of hardware resources, they share many commonalities with the development board described in Section 8.3.

In general, the identifier can be implemented simply by letting secure devices generate a random number. It has to be big enough with respect to the number of tuples to collect in order to make collisions improbable so that in the rare collision cases the recipient simply keeps one of the colliding tuples. For example, around 5 billion numbers have to be generated to reach 50% chance collision with a 64-bits random number.

ACKNOWLEDGMENTS

The authors wish to thank Anne Cantaut from INRIA-SECRET team and Matthieu Finiasz from CryptoExperts for their help in defining and proving the security of our GKE protocol, and Philippe Bonnet from University of Copenhagen for fruitful discussions on this paper.

This work is partly supported by ANR Grant KISS (Keep your Information Safe and Secure) n° ANR-11-INSE-0005, by the Paris-Saclay Institut de la Société Numérique funded by the IDEX Paris-Saclay, ANR-11-IDEX-0003-02 and by INRIA Project Lab CAPPRIS..

A. SAFETY PROPERTIES AGAINST MALICIOUS ATTACKER

The protocols presented in this paper protect against confidentiality attacks conducted by honest-but-curious adversary. Additional counter-measures must be integrated in the protocols to defeat malicious attackers. Indeed, a malicious SSI could try to tamper with the intermediate results produced during the query execution, either to mislead the querier or to gain some benefit (e.g., save computing and storage resources) from skipping part of the computation. Hence, the integrity of the final result must be made controllable by the Querier. Checking the integrity of an outsourced query result sums up to checking data authenticity, data freshness and query completeness.

Authenticity means that the query result is generated from original database tuples. Authenticity is generally achieved by attaching a signature to a tuple or part of a tuple. As the signature is unforgeable by anyone who does not own the key, any TDS can check signatures produced by any other TDS.

Freshness means that the query result is computed over the latest version of the tuples. Since the query is executed directly in the client's side (TDS), the tuples returned in the collection phase are guaranteed to be up-to-date. However, SSI must be prevented from replacing fresh encrypted tuples sent by TDSs by old tuples resulted from previous queries by attaching the session id to the tuples.

Completeness means that all tuples participating to the collection phase are reflected once, and only once (hence completeness encompass accuracy in our definition), in the result. To ensure completeness, we must prevent duplicate and delete actions from malicious attackers. These actions are hard to detect since this requires having a global view of the dataset.

In order for the TDS and the querier to check authenticity, freshness and completeness, extra information, called hereafter security information, has to be produced by the TDSs and bind both to the tuples produced during the collection phase and to the partitions produced during the aggregation phase. We introduce below the set of properties required to enforce authenticity, freshness and completeness and detail the associated security information and security test performed on it.

Let us call Г e ← {tup e } the set of encrypted tuples collected in the collection phase. Each tuple tup e  Г e follows the format: tup e ← (c, id) with tup e .c ← nEk(tup), and tup e .id ← nEk(identifier) with tup is the plaintext tuple and identifier is the identity of tup. We assume that identifiers are unique in the whole system, e.g., by concatenated the local tuple identifier with the TDS identifier. Each encrypted partition/aggregation Ω e i contains a set of tuples' identifiers it is supposed to contain, called Ω-set, denoted as Ω e i.ID, and the total number of tuples contributed to that aggregation, denoted as Ω e i.ψ.

Definition 1 (Origin safety property). The Origin safety property guarantees that a tuple originates from a real TDS as target of a given query itself identified by Qid. Origin is considered as a proof of authenticity and freshness. To enforce this property, each tuple embeds a signature, denoted σ, which is the result of signing the encrypted tuple concatenated to its encrypted identifier and query identifier: tup.σ ← sign(tup e .c || tup e .id || Qid).

As previously said, completeness is significantly harder to achieve since it requires building a global view of the collected dataset and be able to detect any delete and copy action on it from an adversary.

Delete actions means removing encrypted tuples from partitions or even removing complete partitions during the execution, making the final result incomplete. These actions reduce the size of the encrypted dataset to be processed. We use the Quantity Preservation safety property to prevent this kind of attack. Basically, this safety property preserves the number of tuples to be processed from the beginning of the protocol until the final step.

Definition 2 (Quantity Preservation safety property). Aggregations or partitions respect Quantity Preservation if ∑ |Ω 𝑖 𝑒 . ψ| = 𝑆 𝑝 𝑖=1

with p being the total number of aggregations/partitions, and S the value in SIZE clause of the query.

Thank to this property, if SSI drops any tuple or partition during the execution, the total number of tuples for this query will be less than the required number, making this action detectable. Similarly, this property also prevents duplicate actions augmenting the number of tuples. However, it doesn't prevent a malicious SSI to delete arbitrary d encrypted tuples from a partition, and then copy another d existing encrypted tuples from this (or another) partition to replace them. This action satisfies both the Origin safety property (SSI does not forge any new tuples) and Quantity Preservation safety property (since the total number of tuples remains unchanged). However, it still makes the final result incorrect due to the difference between deleted tuples and duplicated ones. Replace actions (i.e., replacing a deleted tuple by a duplicated one) can be either intra-partition (tuples are replaced into their own partition) or inter-partition (the destination partition is different from the source partition). Intra-partition replace actions can be easily detected by checking the unicity of tuple identifiers within each partition. The Identifier Unicity safety property (Definition 3) serves this purpose. Definition 3 (Identifier Unicity safety property) Let tup e ∈ Ω e i be a tuple in the partition/aggregation Ω e i. Partition/Aggregation Ω e i respects the Identifier Unicity safety property if for every pair of tuples tup e j, tup e k∈Ω e i, tup e j.id = tup e k.id ⇒ j = k.

Detecting inter-partition replace actions is more difficult and requires organizing the set of tuples such that each identifier is authorized to be part of a single partition (partitions intersections are empty). To this end, we define for each partition the set of identifiers it is supposed to contain, called Ω-set, denoted by Ω e i.ID. The Mutual Exclusion safety property (Definition 4) ensures that no Ω e i.ID overlaps, and the Membership safety property (Definition 5) ensures that each identifier must appear in the partition to which it is supposed to belong. As a result, Mutual Exclusion and Membership together guarantee that each identifier actually appears within a single partition (as stated in the Lemma). Exclusion if for every pair of partitions Ω e i, Ω e j, i ≠ j ⇒ Ω e i.ID∩ Ω e j.ID = Ø. Definition 5 (Membership safety property) A partition respects Membership if for every tuple tup e j ∈ Ω e i, then tup e j.id ∈ Ω e i.ID.

Lemma. Enforcing together the Identifier Unicity, Mutual Exclusion, and Membership safety properties is necessary and sufficient to guarantee the absence of any (intra/inter-partition) replace action.

Proof We start by showing the sufficiency of these properties. First, Identifier Unicity is sufficient to preclude by itself intra-partition replace actions (recall that the authenticity of a tuple and its identifier is guaranteed by the Origin safety property). Second, assume that a given tuple tup e has been copied into two distinct partitions. Only the Ω-set of one of them contains tup e identifier because otherwise Mutual Exclusion would be contradicted. Consequently there must be one partition's Ω-set that does not contain tup e identifier. But this clearly contradicts the Membership safety property. As a result, Membership and Mutual Exclusion are together sufficient to preclude inter-partition replace actions.

We now show the necessity of these properties. First, since a distinct identifier is assigned to each tuple, the absence of intra-partition replace results immediately in the satisfaction of the Identifier Unicity property. Second, the absence of interpartition replace implies that the partitioning is correct so that: (1) the Mutual Exclusion property is satisfied in that Ω-sets do not overlap (recall that a distinct identifier is assigned to each tuple) and ( 2) the Membership property too in that each tuple appears in the partition which Ω-set contains its identifier. □ Implementation Sketches. The implementations of the Origin and Identifier Unicity safety properties are straightforward: when receiving a partition to compute, the given TDS simply checks the signatures of tuples and the absence of duplicate identifier 19 .

The other properties are harder to check because they concern the complete dataset. We thus add an header in each partition to contain the summary information of that partition.

First, the header contains Ω e i-ψ, the total number of tuples contributing to the aggregation Ω e i. Every times a TDS receives partitions from SSI and computes the new aggregation, it cumulates all Ω e i-ψ belonging to these partitions and stores the result in the header of the new aggregation. Note that only the TDS that combines the last partitions into the final result can check that ∑ |Ω 𝑖 𝑒 . ψ| = 𝑆 𝑝 𝑖=1

. But since a TDS does not know if he is calculating the final or intermediate result, he cannot check the Quantity Preservation safety property. Only when the final result is delivered to Querier, who knows for sure that he is obtaining the final result, this property (Ω e final.ψ = S) can be checked.

Second, the header also contains Ω e i.ID, the set of identifiers of all tuples in the partition Ω e i. In every step of the protocol, when the partitions are accumulated, TDS also makes a union between these lists. When making this union, TDS can detect only the partial inter-partition replace actions in which these actions happen among the partitions that TDS is handling. Similar to Ω e i-ψ, it is impossible for a TDS to detect the full inter-partition replace actions unless that TDS is handling the last ACM Transactions on Database Systems, Vol. xx, No. xx, Article xx, Publication date: Month YYYY partitions to create the Ω e final. Therefore, it is Querier, who obtains the Ω e final, which can check the full inter-partition replace actions.

While the extra-cost of these verifications has not been evaluated yet, it relies on rather simple tests compared to the usual complexity of checking the integrity of outsourced query results.