Collusion-Tolerable and Efficient Privacy-Preserving Time-Series Data Aggregation Protocol

Abstract

Many miraculous ideas have been proposed to deal with the privacy-preserving time-series data aggregation problem in pervasive computing applications, such as mobile cloud computing. The main challenge consists in computing the global statistics of individual inputs that are protected by some confidentiality mechanism. However, those works either suffer from collusive attack or require time-consuming initialization at every aggregation request. In this paper, we proposed an efficient aggregation protocol which tolerates up to k passive adversaries that do not try to tamper the computation. The proposed protocol does not require a trusted key dealer and needs only one initialization during the whole time-series data aggregation. We formally analyzed the security of our protocol and results showed that the protocol is secure if the Computational Diffie-Hellman (CDH) problem is intractable. Furthermore, the implementation showed that the proposed protocol can be efficient for the time-series data aggregation.

1. Introduction

The security and privacy issue in pervasive computing applications, such as mobile cloud computing, crowd sourcing, and smart metering, has long been a hot research topic in the field of applied cryptography. An adversary may infringe customers' privacy in pervasive computing environment since they are “smart” enough to record one's preferences or habits. For example, smart meters report consumption for users at high frequency (e.g., once per minute) and in real time. This level of monitoring can reveal much private information about users' habits and subject the users to many loathsome outcomes [1, 2], for example, whether they often watch TV (discriminating pricing of health insurance), or even stealthy surveillance in general [3]. For another example, mobile users report their locations, speeds, and mobility to a GPS service provider at real time. The aggregated data, for instance, the number of users at each region during each time period, can be mined for congestion patterns on the roads [4, 5]. However, the individual information above needs to be protected in the privacy consideration.

In this paper, we focus on the privacy-preserving aggregation problem of time-series data without a trusted third party. We use a new additive homomorphic encryption as the cryptographic primitive to handle this aggregation problem. Jung et al. had pointed out that the trusted or semitrusted key issuers could be a security hole since the security of those schemes relies on the assumption that keys are disclosed to authorized participants only [6]. Therefore, the proposed scheme is not initialized by requesting keys from trusted or semitrusted key issuers via secure channel. Meanwhile, we do not require that participants be able to communicate with their neighbors via wireless communication channel. This requirement is expensive and somewhat difficult to actualize in large area situations, so we simply assume that each participant only has a bidirectional communication channel with the aggregator. Besides the aforementioned drawbacks, a large number of aggregation protocols are proposed under the weak security assumption that all the participants are semitrusted and do not collude with the aggregator. To sum up, the goal of this paper is to design a privacy-preserving time-series data aggregation protocol which is robust against up to k colluding passive adversaries that do not try to tamper the computation.

The main contributions of this paper are as follows. (1) We propose a privacy-preserving time-series data aggregation protocol without trusted central key issuer and it only needs one initialization for the participants to acquire their encryption keys. (2) Security and complexity analyses of the proposed protocol are given and the proposed protocol is shown to be efficient and scalable and also it is proved to tolerate up to k colluding passive adversaries. (3) A method which allows the participant and aggregator to verify any individual input or the accumulation of inputs is proposed and the performance evaluations are given in this paper.

The remainder of this paper is structured as follows. The related work is detailed in Section 2. We present the system model and necessary background in Section 3. Subsequently, the construction of our scheme is described in Section 4 and, thereafter, security analysis is in Section 5. The complexity analysis and performance evaluation are reported in Section 6. Section 7 presents the conclusions of this research.

2. Related Work

Many papers have been done in the fields of privacy-preserving data aggregation for many application scenarios. We present the most relevant work to our contribution in this paper. A Paillier's encryption scheme based privacy-enhancing protocol was proposed by Li et al. [10]. Subsequently, Li and Luo introduced the use of homomorphic signature allowing verification to confirm that the data aggregation was correct in [11]. Garcia and Jacobs proposed an aggregation scheme for secure communication with smart meters [12], where a combination of Paillier's additive homomorphic encryption and additive secret sharing has been used. Danezis et. al. [13] proposed an aggregation scheme based on secret-sharing and secure multiparty computation techniques. Shi et al. [14] proposed a Diffie-Hellman based encryption scheme where participants periodically upload encrypted values to an aggregator, and the aggregator computes the sum of those values without learning anything else. It uses brute-force search or Pollard's lambda method to find the exact sum. This kind of brute-force decryption limits its usage restricted to small plaintext spaces due to the hardness of the discrete logarithm problem. Joye and Libert [15] proposed a solution to efficiently decrypt the sum based on the idea of splitting the exponent. Leontiadis et al. [16] introduced a secure protocol for aggregation of time-series data that is based on Joye's scheme [15] and the requirements for key updates and for the trusted dealer are eliminated. The main idea of it is to introduce a semitrusted collector which plays the role of an intermediary between the users and the aggregator.

Recently, Li et al. [8] introduced an efficient protocol to obtain the sum aggregate, which employs an additive homomorphic encryption to support large plaintext space. But this scheme relies on trusted key dealers that distribute the keys via secure channel. Mármol et al. [7] proposed a protocol in which each participant adds its key to its measurement and sends the result to the aggregator, but their scheme needs a previous aggregation before getting the exact sum. In [9], Borges and Muhlhauser proposed an efficient privacy-preserving protocol for smart metering systems based on Paillier's scheme. However, they assume smart meters in the neighborhood communicate with a collector through a wireless mesh network and the collector further communicates with the central management facility through wired communication in the initial setup. Their scheme has the common problem that it will fail if the collector device colludes with the aggregator. Jung et al. [6] presented an advanced protocol which tolerates up to k passive adversaries that did not try to tamper the computation without secure channel. Their protocol needs to initialize for every round of aggregation, so both the communication and computation overheads are too extravagant in time-series data aggregation. Table 1 summarizes our protocol with major related protocols in the literatures. Besides, there are also several works [17–22] on privacy-preserving aggregation of time-series data. Some of them leverage the differential privacy [23] in various ways to achieve privacy as well as collusion (or fault) tolerance. Our scheme can also achieve differentially privacy by simply adding the noises that follow diluted geometric distribution to each meter's data [14].

Table 1

Comparison between the proposed protocols and related aggregation protocols.

	No trusted key dealer	No previous aggregation	Collusion-tolerable	No neighborhood communication	Setup once for all
Mármol et al. [7]	√	×	√	×	×
Li et al. [8]	×	√	√	√	√
Jung et al. [6]	√	√	√	√	×
EPPP4SMS [9]	√	√	×	×	√
Our scheme	√	√	√	√	√

In our scheme, the trusted key dealer in [8, 18, 21] is removed because of the aforementioned security loophole. Unlike [8, 17], we assume insecure channels between most participants, while the secure channels are established based on public key encryption among a small fraction of participants in the same subgroup, which enabled us to implement the proposed scheme in the real cloud environments easily. In this paper, we also take into consideration a small fraction of the participants colluding with the curious aggregator as [6, 17] do. Our scheme is also based on the hardness of the discrete logarithm problem like [14], and we employ an efficient method to calculate the sum instead of employing brute-force manner in decryption.

3. System Model

3.1. Problem Definition and Threat Model

Assume that there are N participants with equivalent number of IDs $\{\mathrm{1,2},\dots ,N\}$ in the system considered in this paper and there is an aggregator that wants to get the sum aggregate of N participants periodically. In this paper, the aggregator may be the service supplier or the cloud. The system is shown in Figure 1. At a time stamp t, each participant i produces a privately known data point $x_i(t$ ) from ℤ. The privacy-preserving data aggregation problem is to compute the sum of $x_i(t)$ by the aggregator while preserving the data privacy; that is, the objective of the aggregator is to compute the following polynomial without knowing the value of $x_i(t)$ :

$$\begin{array}{cc}& \mathrm{S}\mathrm{U}\mathrm{M}\left(\mathbf{x}\left(\mathbf{t}\right)\right)={\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right),\end{array}$$

(1)

where vector $\mathbf{x}(\mathbf{t})=(x_{\mathrm{1}}(t),x_{\mathrm{2}}(t),\dots ,x_N(t))$ . Here, we assume that the final result SUM $(\mathbf{x}(\mathbf{t}))$ is positive and bounded from above by a large prime number p.

Figure 1

The system model.

We assume that participants have a bidirectional communication channel with the aggregator like [17]. The participants are not connected to each other directly, but they can exchange encrypted messages among themselves via the aggregator or intermediate routers. Similar to [6], the communication channels in the system are insecure. Anyone can easily eavesdrop them and/or intercept the data being transferred. In this paper, the aggregator is untrusted so that a curious aggregator may try to compromise someone's private information through the aggregation protocol. A small fraction of the participants may collude with the aggregator, say at most k participants. Similar to [14], we assume that the system has a priori estimate over the upper bound of k. Participants will in general hide the information they have before reporting it to the aggregator. To assist the curious aggregator, however, colluders may deviate from the protocol by providing their own information in the clear to the aggregator. We further assume the participants and aggregator may be passively adversarial; that is, they will not falsify the computation, but they may try to manipulate their calculation to infer others' private information.

3.2. Security Model

To address the challenges of insecure communication channel, we assume that the following CDH problem is computationally intractable; that is, any Probabilistic Polynomial Time Adversary has negligible chance to solve the following problem.

Definition 1 (CDH problem in G).

The Computational Diffie-Hellman problem in a multiplicative group G with generator g is defined as follows: given only $g,g^a,g^b\in \mathbf{G}$ , where $a,b\in \mathbb{Z}$ , compute $g^{ab}$ without knowing a or b.

According to [6], we define the security of our proposed scheme as follows.

Definition 2 (CDH-security in G).

We say our privacy-preserving sum calculation is CDH-secure in G if any Probabilistic Polynomial Time Adversary (PPTA) that cannot solve the CDH problem with nonnegligible chance has negligible chance to infer any honest participant's private value in G; that is, any PPTA's probability to solve the CDH problem ε satisfies $\epsilon <\left|\mathrm{1}/p(\kappa )\right|$ for any polynomial $p(·)$ , where κ is the order of group G defined in the CDH problem.

Informally, we opine that our calculation is CDH-secure in G if illegally inferring an honest participant's private value during our calculation is at least as hard as CDH problem in G.

3.3. Some Definitions

Group G is selected as follows. Two large prime numbers p and q are chosen such that $p=k_{c}q+\mathrm{1}$ , where $k_c$ is an integer. Then the q-order cyclic multiplicative group G is defined as $〈g〉$ , where the generator g is selected with a random number $r\in {\mathbb{Z}}_p$ as

$$\begin{array}{cc}& g=r^{p\left(p-\mathrm{1}\right)/q}\mathrm{mod}{p}^{\mathrm{2}}\hspace{1em}\text{s.t.\hspace{0.17em}\hspace{0.17em}}g\ne \mathrm{1}\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(2)

In this system, the aggregator intends to compute the sum ${\sum }_{i=\mathrm{1}}^n{x}_i(t)$ without knowing any individual $x_i(t)$ . For simplicity, we index the aggregator with number 0. In our scheme, the aggregator has the capability $k_{\mathrm{0,1}}$ and $k_{\mathrm{0,2}}$ to decrypt the encrypted sum. Nevertheless, each participant i has also its permanent private key $k_{i,\mathrm{1}}$ and time-dependent private key $k_{i,\mathrm{2}}$ to encrypt its data. Like [9], we define the encryption function Enc as

$$\begin{array}{cc}& {\mathbb{Z}}_{p^{\mathrm{2}}}\times \mathbf{G}\times \mathbf{G}⟶{\mathbb{Z}}_{p^{\mathrm{2}}},\\ \mathrm{E}\mathrm{n}{\mathrm{c}}_i\left(m,h,g\right)⟼\left(\mathrm{1}+mp\right)·h^{k_{i,\mathrm{1}}}·g^{k_{i,\mathrm{2}}}\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(3)

Here, h is nonce over ${\mathbb{Z}}_{p^{\mathrm{2}}}$ and $k_{i,\mathrm{1}},k_{i,\mathrm{2}}$ are nonces over ${\mathbb{Z}}_p^{\ast }$ . We can assume the existence of a secure hash function H and define $h=H(t)$ , $H:\mathbb{Z}\to \mathbf{G}$ , where t is the timestamp. The time-dependent private key $k_{i,\mathrm{2}}$ is defined on the base of a pseudorandom function (PRF) family $\mathbb{F}=\{f_k:\mathbb{Z}\to {\mathbb{Z}}_q{\}}_{k\in \mathbf{G}}$ with the seed k, and we set $k_{i,\mathrm{2}}=f_k(t)-f_{k^{\prime }}(t)$ , where $f_k,f_{k^{\prime }}\in \mathbb{F}$ . Note that the timestamp t cannot be repeated, so the hash function and the nonce $k_{i,\mathrm{2}}$ ensure that previous encrypted data points will not be correlated to obtain information.

Subsequently we introduce the decryption mechanism behind the encryption function. Obviously, the Enc function defined here is an additive homomorphic encryption; that is,

$$\begin{array}{cc}& {\mathrm{E}\mathrm{n}\mathrm{c}}_i\left(m_{\mathrm{1}},h,g\right)\mathrm{E}\mathrm{n}{\mathrm{c}}_j\left(m_{\mathrm{2}},h,g\right)=\mathrm{E}\mathrm{n}{\mathrm{c}}_{i+j}\left(m_{\mathrm{1}}+m_{\mathrm{2}},h^{\prime },g\right)\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(4)

Given the family of encryption functions from (3), each participant i encrypts its data $x_i(t)$ and gets $\mathrm{E}\mathrm{n}{\mathrm{c}}_i(x_i(t),h,g)$ . Then participant i sends $\mathrm{E}\mathrm{n}{\mathrm{c}}_i(x_i(t),h,g)$ to the aggregator. To decrypt the consolidated summation, the aggregator needs to multiply all encrypted data computing:

$$\begin{array}{cc}& {\displaystyle \prod }_{i=\mathrm{1}}^N\mathrm{E}\mathrm{n}\mathrm{c}\left(x_i\left(t\right),h,g\right)=\left(\mathrm{1}+p{\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right)\right)H{\left(t\right)}^{{\sum }_{i=\mathrm{1}}^N{k}_{i,\mathrm{1}}}{g}^{{\sum }_{i=\mathrm{1}}^N{k}_{i,\mathrm{2}}}\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(5)

If the aggregator has capability $k_{\mathrm{0,1}}$ and $k_{\mathrm{0,2}}$ , s.t. $k_{\mathrm{0},j}+{\sum }_{i=\mathrm{1}}^N‍k_{i,j}=\mathrm{0},\hspace{0.17em}\hspace{0.17em}j=\mathrm{1,2}$ , then the aggregator only needs to compute

$$\begin{array}{cc}& \frac{\left(H{\left(t\right)}^{k_{\mathrm{0,2}}}·g{\left(t\right)}^{k_{\mathrm{0,2}}}·{\prod }_{i=\mathrm{1}}^n\mathrm{E}\mathrm{n}\mathrm{c}\left(x_i\left(t\right),h,g\right)-\mathrm{1}\right)\mathrm{mod}{p}^{\mathrm{2}}}{p}\end{array}$$

(6)

to get the decryption sum ${\sum }_{i=\mathrm{1}}^N{x}_i(t)$ because $H(t)$ and g are cancelled when $H(t{)}^{k_{\mathrm{0,1}}}$ and $g(t{)}^{k_{\mathrm{0,2}}}$ are multiplied to the encryption result. The detailed construction of our aggregation scheme will be shown in the next section.

4. Our Construction

Jung and Li's scheme [6] includes an advanced protocol which tolerates up to k passive adversaries that do not try to tamper the computation. But the communication and computation overheads are large for participant since it needs to exchange $k+\mathrm{1}$ rounds of messages and to compute its private encryption key every time when a new sum is desired. In this section, we propose a secure key assignment protocol to initialize our scheme and to distribute secret keys among the participants and the aggregator. Even though the communication and computation overheads might be large in our initial setup, our aggregation scheme can perform effectively after setup for only one encryption and one communication with the aggregator in the following aggregations. Before detailing the description of our solution, we first give a brief overview of Jung and Li's scheme.

4.1. Jung and Li's Scheme

(i) Setup. The participant i picks a secret number $r_i\in {\mathbb{Z}}_p$ and calculates a public parameter $Y_i=g^{r_i}$ . Then, each participant i shares $Y_i$ with participants $i-k$ , $i+\mathrm{1}$ , and $i+\mathrm{2}$ . After a round of exchanges, the participant $i+\mathrm{1}$ computes $Y_{i=\mathrm{1}}^{\prime }=(g^{r_{i+k+\mathrm{1}}}/g^{r_{i-\mathrm{1}}}{)}^{r_{i+\mathrm{1}}}$ and sends $Y_{i+\mathrm{1}}^{\prime }$ to $i+\mathrm{2}$ . After the second round of exchanges, the participant $i+\mathrm{2}$ computes $Y_{i+\mathrm{2}}^{\prime }=(Y_{i+\mathrm{1}}^{\prime }{)}^{r_{i+\mathrm{2}}}$ and sends it to participant $i+\mathrm{3}$ . In general, when there are k colluding adversaries, it needs $k+\mathrm{1}$ rounds of exchanges such that i gets its randomizer $R_i=(g^{r_{i+k+\mathrm{1}}}/g^{r_{i-\mathrm{1}}}{)}^{r_{i+k}{r}_{i+k-\mathrm{1}}\cdots r_{i+\mathrm{1}}{r}_i}$ $\mathrm{mod}p$ .

(ii) Encrypt. Every participant i calculates $C_i=(\mathrm{1}+x_i(t)p)·R_i\mathrm{mod}{p}^{\mathrm{2}}$ . Then, it sends $C_i$ to the aggregator.

(iii) Sum. After receiving the ciphertexts from all of the participants, the aggregator calculates ${\prod }_{i=\mathrm{1}}^N‍C_i(t)\mathrm{mod}{p}^{\mathrm{2}}=(\mathrm{1}+p{\sum }_{i=\mathrm{1}}^N‍x_i(t))\mathrm{mod}{p}^{\mathrm{2}}$ . And the aggregator calculates $(C(t)-\mathrm{1})/p={\sum }_{i=\mathrm{1}}^N‍x_i(t)$ to recover the final sum.

It is obvious that the randomizer $R_i$ should change at every timestamp t, so Jung and Li's scheme has to set up for every aggregation request. The successive time-consuming setup phase makes the above scheme inapplicable for the aggregation of time-series data.

4.2. Protocol Description

Similarly, our scheme of privacy-preserving sum calculation for time-series data has the three phases: Setup, Encrypt, and Sum.

4.2.1. Setup

(A) Phase 1. In our construction, the aggregator needs to get the capability $k_{\mathrm{0,1}}=-{\sum }_{i=\mathrm{1}}^N‍k_{i,\mathrm{1}}$ such that $H(t)$ in the encrypted sum can be cancelled in decryption. Here we propose a secure and privacy-preventing sum aggregation protocol without trusted key dealers based on Shamir's secret sharing [24] and Diffie-Hellman key agreement protocol. As is assumed previously, the number of compromised nodes is at most k; thus we divide all N participants into a series of subgroups that contains at least $k+\mathrm{2}$ participants firstly. For simplicity, we set $n\ge k+\mathrm{2}$ . Here we consider the naïve division that every subgroup has n participants and the participant with identity number i belongs to the $[i/n]$ th subgroup (the participants in the first subgroup can be reused if there are no enough participants in the last subgroup). We assume the participant i has an auxiliary identity number $m_i\in [n]$ in its subgroup; that is, the participants will get an auxiliary identity number $m_i$ from 1 to n according to its identity number i in proper order.

At first, every participant and the aggregator choose a private number to set up the secure channel based on Diffie-Hellman key agreement protocol. Take participants in the mth subgroup as the example. Here each participant i has an auxiliary identity number $m_i\in [n]$ in this subgroup. At first, each participant i chooses a random number $r_i\in {\mathbb{Z}}_q$ computing its public parameter $g_i=g^{r_i}$ and sends $g_i$ to the aggregator. After receiving messages from participants, the aggregator uses its privately known number $r_{\mathrm{0}}$ to compute $s_{\mathrm{0},i}=g_i^{r_{\mathrm{0}}}=g^{r_{\mathrm{0}}{r}_i}$ and sends its public parameter $g_{\mathrm{0}}=g^{r_{\mathrm{0}}}$ and all the other $g_j$    $(i\ne j)$ to each participant i; here participant j is also in the mth subgroup. After that each participant i computes $s_{i,\mathrm{0}}=g_{\mathrm{0}}^{r_i}=g^{r_{\mathrm{0}}{r}_i}$ and all $s_{i,j}=g_j^{r_i}=g^{r_j{r}_i}\hspace{0.17em}\hspace{0.17em}(i\ne j)$ . Thus, all the participants in the mth subgroup and the aggregator share a private session key with each other in the above way.

After the session keys in the subgroup are established, each participant i chooses a private number $p_i$ and generates a random polynomial $w_i$ over ${\mathbb{Z}}_q^{\ast }$ of order $n-\mathrm{1}$ , such that $w_i(\mathrm{0})=p_i$ . Then each participant i computes the share of participant j which belongs to the same subgroup as $w_{i,m_j}=w_i(m_j)$ for $m_j\in [n]$ . Then, each participant i stores share $w_{i,m_i}$ itself and all the other shares $w_{i,m_j}$    $(m_j=\mathrm{1,2},\mathrm{3},\dots ,m_i-\mathrm{1},m_i+\mathrm{1},\dots ,n)$ are sent to the aggregator after being encrypted with the symmetric cryptography (e.g., AES in this paper and we use $\mathrm{A}\mathrm{E}\mathrm{S}(w_{i,m_j})$ to denote the ciphertext of $w_{i,m_j}$ under AES cryptography with symmetric key derived from $s_{i,j})$ . Then the aggregator distributes the encrypted $\mathrm{A}\mathrm{E}\mathrm{S}(w_{j,m_i})$ to participant i. After participant i gets all the encrypted shares $w_{j,m_i}\hspace{0.17em}\hspace{0.17em}(i\ne j)$ from participant j via the aggregator, it decrypts the messages with corresponding symmetric keys and computes the sum $W_i={\sum }_j‍w_{j,m_i}$ , where participant j is in the mth subgroup. After that participant i encrypts $W_i$ as $\mathrm{A}\mathrm{E}\mathrm{S}(W_i)$ with the secret key derived from $s_{i,\mathrm{0}}$ . Finally, the aggregator collects and decrypts the messages from the entire N participants, computes the sum $W_s={\sum }_{m_j=s}‍W_j$ for $s=\mathrm{1,2},\dots ,n$ , interpolates $n-\mathrm{1}$ -order polynomial ${\sum }_{i=\mathrm{1}}^N{w}_i$ , and gets the sum ${\sum }_{i=\mathrm{1}}^N‍p_i={\sum }_{i=\mathrm{1}}^N‍w_i(\mathrm{0})$ . Thus participant i's permanent private key $k_{i,\mathrm{1}}$ is selected as $p_i$ , and the aggregator's first capability $k_{\mathrm{0,1}}$ is equal to $-{\sum }_i‍p_i\mathrm{mod}q$ .

Here we do not use the method that participant i slices its private number $p_i$ into n pieces and sends the corresponding pieces to its subgroup mates in ciphertext, since the aggregator may use exhaustive search to find the unknown small pieces when k participants in this subgroup collude with him.

(B) Phase 2. The capability $k_{\mathrm{0,2}}$ is established in a simple way. As mentioned above, each participant $i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2},\dots ,N)$ has chosen a privately known number $r_i$ and its public parameter $g_i=g^{r_i}$ has been sent to the aggregator. Then, the aggregator distributes $g_{i-\mathrm{1}}$ and $g_{i+\mathrm{1}}$ (here $g_{N+\mathrm{1}}=g_{\mathrm{0}}$ ) to participant i and participant i computes $s_{i,i-\mathrm{1}}=g_{i-\mathrm{1}}^{r_i}$ and $s_{i,i+\mathrm{1}}=g_{i+\mathrm{1}}^{r_i}$ . Note that the process has been done partially in Phase 1 in each subgroup; therefore the aggregator only needs to distributes one message $g_{i-\mathrm{1}}$ or $g_{i+\mathrm{1}}$ to participant i if i and $i-\mathrm{1}$ (or $i+\mathrm{1}$ ) belong to different subgroups. Thus, the time-dependent private key $k_{i,\mathrm{2}}$ for participant i is

$$\begin{array}{cc}& k_{i,\mathrm{2}}=f_k\left(t\right)-f_{k^{\prime }}\left(t\right)=f_{s_{i,i-\mathrm{1}}}\left(t\right)-f_{s_{i,i+\mathrm{1}}}\left(t\right).\end{array}$$

(7)

Similarly, the aggregator's second capability $k_{\mathrm{0,2}}=f_{s_{\mathrm{0},N}}(t)-f_{s_{\mathrm{0,1}}}(t)$ .

4.2.2. Encrypt

The participants do not need to repeat the exchanges to get new random numbers to encrypt their data after setup, so our protocol is more communication and computation efficient than Jung and Li's scheme. For a queried timestamp t, each participant i calculates $\mathrm{1}+x_i(t)p$ firstly. Then, it multiplies the secret parameters $H(t{)}^{p_i}$ and $g^{f_{s_{i-\mathrm{1}}}(t)-f_{s_{i+\mathrm{1}}}(t)}$ with $\mathrm{1}+x_i(t)p$ to get the ciphertext $C_i(t)\in {\mathbb{Z}}_{p^{\mathrm{2}}}$ :

$$\begin{array}{cc}& C_i\left(t\right)=\left(\mathrm{1}+x_i\left(t\right)p\right)·H{\left(t\right)}^{p_i}·g^{f_{s_{i,i-\mathrm{1}}}\left(t\right)-f_{s_{i,i+\mathrm{1}}}\left(t\right)}\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(8)

Note that a small fraction of participants (reused participants) will be divided into two subgroups; thus it has two permanent private keys $p_i$ and $p_i^{\prime }$ . In order to get the right sum, these reused participants should compute the ciphertext $C_i^{\prime }(t)\in {\mathbb{Z}}_{p^{\mathrm{2}}}$ as

$$\begin{array}{cc}& C_i^{\prime }\left(t\right)=\left(\mathrm{1}+x_i\left(t\right)p\right)·H{\left(t\right)}^{p_i+p_i^{\prime }}·g^{f_{s_{i,i-\mathrm{1}}}\left(t\right)-f_{s_{i,i+\mathrm{1}}}\left(t\right)}\mathrm{mod}{p}^{\mathrm{2}}.\end{array}$$

(9)

We will omit $p_i^{\prime }$ in the following by adding $p_i^{\prime }$ to $p_i$ ; that is, $p_i\leftarrow p_i+p_i^{\prime }$ . After all, the participants send their ciphertexts to the aggregator. In addition, the Encrypt scheme can be efficiently encrypted “on-the-fly.” Namely, exponentiations $H(t{)}^{p_i}\mathrm{mod}{p}^{\mathrm{2}}$ and $g^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}\mathrm{mod}{p}^{\mathrm{2}}$ can be precomputed in such a way that when the plaintext $x_i(t)$ is known, the participant only has to compute a modular multiplication to get $C_i(t)$ .

4.2.3. Sum

The aggregator, after receiving the ciphertexts $C_i(t)$ from all participants, calculates $C(t)\in {\mathbb{Z}}_{p^{\mathrm{2}}}$ as

$$\begin{array}{cc}& C\left(t\right)=H{\left(t\right)}^{k_{\mathrm{0,1}}}·g^{k_{\mathrm{0,2}}}·{\displaystyle \prod }_{i=\mathrm{1}}^N{C}_i\left(t\right)\mathrm{mod}{p}^{\mathrm{2}}={\displaystyle \prod }_{i=\mathrm{1}}^N\left(\mathrm{1}+x_i\left(t\right)p\right)·H{\left(t\right)}^{p_i}·g^{f_{s_{i,i-\mathrm{1}}}\left(t\right)-f_{s_{i,i+\mathrm{1}}}\left(t\right)}\mathrm{mod}{p}^{\mathrm{2}}=\left(\mathrm{1}+p{\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right)\right)·H{\left(t\right)}^{k_{\mathrm{0,1}}+{\sum }_{i=\mathrm{1}}^N{p}_i}·g^{f_{s_{\mathrm{0},N}}\left(t\right)-f_{s_{\mathrm{0,1}}}\left(t\right)+f_{s_{\mathrm{1,0}}}\left(t\right)-f_{s_{N,\mathrm{0}}}\left(t\right)}\mathrm{mod}{p}^{\mathrm{2}}=\left(\mathrm{1}+p{\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right)\right)\mathrm{mod}{p}^{\mathrm{2}}\hspace{1em}\left(\text{Here\hspace{0.17em}\hspace{0.17em}}p>{\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right)\right).\end{array}$$

(10)

Then, the aggregator calculates $(C(t)-\mathrm{1})/p={\sum }_{i=\mathrm{1}}^N‍x_i(t)$ to recover the final sum.

4.2.4. Leaving of Existing Participant

Suppose that participant i decides to leave the network with effect at timestamp t. The aggregator should assign a reused participant $i^{\prime }$ to hold the auxiliary identity number $m_i$ in the corresponding subgroup at timestamp t. Then the aggregator sends $g_i$ and the public parameters of all the other $n-\mathrm{1}$ members in that subgroup to participant $i^{\prime }$ and vice versa. Therefore, the secure session keys are established among participant i, $i^{\prime }$ , and all the other $n-\mathrm{1}$ members of that subgroup. Each participant j (including participant $i^{\prime }$ ) in that subgroup generates a random number $r_{m_j}\in {\mathbb{Z}}_q^{\ast }$ and sends its encryption to participant i. Participant i uses respective session key to decrypt the received key $r_{m_j}$ and generates the equality using the received key and its permanent key randomly as $p_i+{\sum }_{m_j=\mathrm{1}}^n{r}_{m_j}={\sum }_{m_j=\mathrm{1}}^n{p}_{m_j}^i\mathrm{mod}q$ and then sends $p_{m_j}^i$ encrypted under the shared symmetric key. So, the reused participant $i^{\prime }$ updates $p_{i^{\prime }}$ as $p_{i^{\prime }}-r_{m_i}\mathrm{mod}q$ and sets the reused permanent key $p_{i^{\prime }}^{\prime }=p_{m_i}^i$ . The other member j of that subgroup updates its permanent private key by adding the previous one to the received number and subtracting its random number $r_{m_j}$ soon afterwards; that is, $p_j\leftarrow (p_j+p_{m_j}^i-r_{m_j})\mathrm{mod}q$ . To deal with the time-dependent private key, participant i should do nothing but the aggregator distributes the public parameters $g_{i-\mathrm{1}}$ and $g_{i+\mathrm{1}}$ to participant $i+\mathrm{1}$ and participant $i-\mathrm{1}$ correspondingly. When participants $i-\mathrm{1}$ and $i+\mathrm{1}$ receive $g_{i+\mathrm{1}}$ or $g_{i-\mathrm{1}}$ , they correspondingly compute $s_{i-\mathrm{1},i+\mathrm{1}}=g_{i+\mathrm{1}}^{r_{i-\mathrm{1}}}$ and $s_{i+\mathrm{1},i-\mathrm{1}}=g_{i-\mathrm{1}}^{r_{i+\mathrm{1}}}$ . So their time-dependent private keys are denoted as $k_{i-\mathrm{1,2}}=f_{s_{i-\mathrm{1},i-\mathrm{2}}}(t)-f_{s_{i-\mathrm{1},i+\mathrm{1}}}(t)$ and $k_{i+\mathrm{1,2}}=f_{s_{i-\mathrm{1},i-\mathrm{2}}}(t)-f_{s_{i-\mathrm{1},i+\mathrm{2}}}(t)$ .

4.2.5. Joining of New Participant

Assume that a participant, say i, joins just before time slot t and participants $i-\mathrm{1}$ and $i+\mathrm{1}$ hold their time-dependent private keys as $k_{i-\mathrm{1,2}}=f_{s_{i-\mathrm{1},i-\mathrm{2}}}(t)-f_{s_{i-\mathrm{1},i+\mathrm{1}}}(t)$ and $k_{i+\mathrm{1,2}}=f_{s_{i-\mathrm{1},i-\mathrm{2}}}(t)-f_{s_{i-\mathrm{1},i+\mathrm{2}}}(t)$ . Participant i has to share a session key $s_{i,\mathrm{0}}$ with the aggregator using Diffie-Hellman key agreement protocol at first. Then the aggregator should assign participant i an auxiliary identity number $m_i$ which holds by a reused participant j previously in the corresponding subgroup. The aggregator sends $g_i$ and $g_j$ to participants j and i, correspondingly. Hence, participants i and j share a secure session key by raising the message to the power of its private number. Then, participant j sends its reused permanent private key $p_j^{\prime }$ encrypted under the shared symmetric key to participant i. Participant i will get $p_j^{\prime }$ by decrypting the message of j. Then the aggregator sends $g_i$ to all the other $n-\mathrm{1}$ members within that subgroup and vice versa to establish the secure session key among i and all the others in that subgroup. Participant i slices $p_j^{\prime }={\sum }_{m_j=\mathrm{1}}^n{p}_{m_j}^i\mathrm{mod}q$ randomly and each participant j in this subgroup generates a random number $r_{m_j}$ simultaneously. Then participant i sends the slice $p_{m_j}^i\hspace{0.17em}\hspace{0.17em}(m_j\ne m_i)$ encrypted under the shared symmetric key between participants i and j to participant j and $r_{m_j}$ is sent to participant i in encryption as aforementioned. After decrypting the message $r_{m_j}$ , participant i gets its permanent private key $p_i=p_{m_i}^i+{\sum }_{m_j=\mathrm{1},j\ne i}^n{r}_{m_j}\mathrm{mod}q$ . Then, participant j in this subgroup updates its permanent private key as $p_j+p_{m_j}^i-r_{m_j}\mathrm{mod}q$ . To reassign the time-dependent private key, the aggregator distributes $g_{i-\mathrm{1}}$ and $g_{i+\mathrm{1}}$ to participant i and $g_i$ to participant $i+\mathrm{1}$ and $i-\mathrm{1}$ . By the way mentioned earlier, participants $i-\mathrm{1}$ , i, and $i+\mathrm{1}$ get their time-dependent private key as $f_{s_{i-\mathrm{1},i-\mathrm{2}}}(t)-f_{s_{i-\mathrm{1},i}}(t)$ , $f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)$ , and $f_{s_{i+\mathrm{1},i}}(t)-f_{s_{i+\mathrm{1},i+\mathrm{2}}}(t)$ , correspondingly.

5. Protocol Analysis

When p is chosen large enough to hold the inequality $p>{\sum }_{i=\mathrm{1}}^N‍x_i(t)$ , the correctness of the proposed scheme is proven in Section 4.2.3. In this section, we present the property of verification which can be used by the participants and the aggregator. The analyses of privacy and security about our aggregation scheme are also presented.

5.1. Verification Properties

If a participant did not send its data or sent an invalid message, the aggregator cannot read consolidated summation, that is, the exact sum. Obviously, neighboring participants and participants in the same subgroup can cooperate to disclose the key of the damaged participant. But this can result in the privacy disclosure of the damaged one. A better solution is to generate new keys for nondamaged participants. As the benefits of our subgroup method, the aggregator can know the exact sum of one subgroup's permanent private keys. Therefore, only n participants need to change their permanent private keys and two participants need to regenerate their time-dependent private keys.

The aggregator can ask for verification when the sum is different from the expected. If the aggregator asks for verification to identify that something is wrong, a participant i can reveal its proof of the timestamp t without disclosing its actual reading. To perform verification over a sent encrypted value $C_i$ of participant i, the aggregator sends a request to i, and then the participant might send $R_i(t)=(\mathrm{1}+x_i(t)p)·H(t{)}^{p_i}\mathrm{mod}{p}^{\mathrm{2}}$ and $V_i(t)=g^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}\mathrm{mod}{p}^{\mathrm{2}}$ to the aggregator. Therefore, the sent encrypted value can be verified by $C_i(t)?=R_i(t)·V_i(t)\mathrm{mod}{p}^{\mathrm{2}}$ . Note that the accumulation of participant's inputs during the time period from $t_{\mathrm{0}}$ to $t_{\mathrm{0}}+d$ (e.g., one day) can be verified in the following way. The aggregator computes $O{C}_i(t)={\prod }_{t=t_{\mathrm{0}}}^{t_{\mathrm{0}}+d}‍C_i(t)\mathrm{mod}{p}^{\mathrm{2}}$ by multiplying all the $d+\mathrm{1}$ encrypted inputs and participant i sends the sum $O{R}_i(t)={\prod }_{t=t_{\mathrm{0}}}^{t_{\mathrm{0}}+d}‍x_i(t)$ and the product $O{V}_i(t)={\prod }_{t=t_{\mathrm{0}}}^{t_{\mathrm{0}}+d}‍H(t{)}^{p_i}{g}^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}\mathrm{mod}{p}^{\mathrm{2}}$ to the aggregator. If $O{C}_i(t)=(\mathrm{1}+O{R}_i(t)·p)·O{V}_i(t)\mathrm{mod}{p}^{\mathrm{2}}$ , then the participant proves the accumulation result is correct. The later verification property can be used to invoice the billing information in many realistic applications, such as smart grids.

5.2. Security Analysis

Since our aggregator scheme includes three steps: Setup, Encrypt, and Sum, and the Setup is the foundation of our construction, we will give the security proof of Setup at first.

Theorem 3.

Our Phase 1 of Setup in the aggregation scheme is CDH-secure in G.

Proof.

The symmetric cryptography AES is used in our Setup phase as well as Shamir's secret sharing scheme and Diffie-Hellman key agreement protocol. As mentioned in [25], a 128-bit AES key demands a DH key size of 3072 bits for equivalent security. Thus, the security level mainly depends on the DH key agreement protocol. In a nutshell, we show that any PPTA that has significant chance to infer private values in our Setup phase has nonnegligible advantage to solve the CDH problem, which is a contradiction to our security assumption that CDH problem is intractable.

Since the communication channel is insecure, any adversary has the same view unless it can collude with some adversarial participants. In the worst case, the aggregator can collude with $n-\mathrm{2}$ adversarial participants in one subgroup and at least participants i and j are uncompromised. If the aggregator wants to infer the permanent private key $p_i$ of participant i, it has to get $w_{i,m_j}$ and $w_{i,m_i}$ , because even if the aggregator gets another $n-\mathrm{2}$ shares of i, it cannot reconstruct the $n-\mathrm{1}$ -order polynomial $w_i$ to get $p_i$ . If all the symmetric session keys are gotten by the aggregator, it can recover $w_{i,m_j}$ by decrypting the corresponding message and $w_{i,m_i}$ by subtracting ${\sum }_k‍w_{k,m_i}\hspace{0.17em}\hspace{0.17em}(k\ne i)$ from $W_i$ . When the aggregator gets all the n shares of participant i, it interpolates $n-\mathrm{1}$ -order polynomial $w_i$ to calculate $p_i=w_i(\mathrm{0})$ . Note that any PPTA is only given $g_i=g^{r_i}$ and $g_j=g^{r_j}$ from the insecure communication channel, so a PPTA has to solve the CDH problem in G to get the unknown symmetric session keys. However, this is exactly the CDH problem, which is assumed to be intractable. That is, inferring permanent private key during Setup is at least as hard as a CDH problem in G for any Probabilistic Polynomial Time Adversary.

The time-dependent private key in Phase 2 of Setup is aimed not only at enhancing the security but also at reducing the probability that aggregator can get the sum of one subgroup. Without the time-dependent private key, it is easy for aggregator to compute the sum of one subgroup. As Enc is constructed, aggregator can get the sum of a subgroup only if the first and the last participants in its neighboring subgroups are colluded with the aggregator with a probability of $(n-\mathrm{2})(n-\mathrm{3})/N^{\mathrm{2}}$ . The time-dependent private key can confuse the outside adversaries but will fail in collusion attacks. The security of our scheme mainly depends on the permanent private key. Then we will give the security proof of the proposed aggregation process.

Theorem 4.

Our proposed aggregation protocol is CDH-secure in G.

Proof.

To infer $x_i(t)$ given $C_i(t)=(\mathrm{1}+x_i(t)p)·H(t{)}^{p_i}·g^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}\mathrm{mod}{p}^{\mathrm{2}}$ , any adversary has to solve the secret randomizer $H(t{)}^{p_i}·g^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}\mathrm{mod}{p}^{\mathrm{2}}$ . In the worst case, the participants $i-\mathrm{1}$ and $i+\mathrm{1}$ collude with the aggregator and there are also another $n-\mathrm{4}$ participants which are compromised. Thus, the aggregator knows the participant $i^{\prime }s$ time-dependent private key $f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)$ . It has been shown that inferring permanent private key during Setup is at least as hard as a CDH problem in G for any PPTA; thus the aggregator has to solve the secret randomizer $H(t{)}^{p_i}\mathrm{mod}{p}^{\mathrm{2}}$ . Denote $H(t)=g^h$ ; the aggregator has to compute the discrete logarithms to get h and $h{p}_i$ . Assume that there is a PPTA that can solve the discrete logarithm problems, so it also solves the CDH problem defined in our group G. However, the CDH problem is intractable; therefore the adversary has a negligible advantage to solve the secret randomizer $H(t{)}^{p_i}\mathrm{mod}{p}^{\mathrm{2}}$ . That is, inferring private values during the aggregation scheme is at least as hard as a CDH problem in G for any PPTA.

Theorem 5.

Our proposed aggregation protocol is aggregator obliviousness; that is, a party without the aggregator capability learns nothing.

Proof.

To infer ${\sum }_{i=\mathrm{1}}^N‍x_i(t)$ given

$$\begin{array}{cc}& C^{\prime }\left(t\right)=\left(\mathrm{1}+p{\displaystyle \sum }_{i=\mathrm{1}}^N{x}_i\left(t\right)\right)H{\left(t\right)}^{{\sum }_{i=\mathrm{1}}^N{p}_i}{g}^{f_{s_{\mathrm{0,1}}}\left(t\right)-f_{s_{\mathrm{0},N}}\left(t\right)}\mathrm{mod}{p}^{\mathrm{2}},\end{array}$$

(11)

any PPTA has to solve the secret randomizer $H(t{)}^{{\sum }_{i=\mathrm{1}}^N‍p_i}{g}^{f_{s_{\mathrm{0,1}}}(t)-f_{s_{\mathrm{0},N}}(t)}$ firstly. Note that any PPTA is only given $H(t)$ and g from the insecure communication channel; the PPTA has to compute the discrete logarithms to cancel the exponent of g. That is, inferring the aggregation results without the aggregator capability is at least as hard as a CDH problem in G for any PPTA.

The security proof of the Leaving or Joining process is omitted. However, these two processes are CDH-secure in G.

6. Performance Evaluation

6.1. Complexity

In this section, we will discuss the computation and communication complexities of the proposed aggregation scheme. For the sake of simplicity, we denote that the computation complexity of encryption or decryption in 128-bit AES is $O(\mathrm{1})$ and we also assume that there are no reused participants.

6.1.1. Setup Process

In Phase 1, it is easy to see that the participant needs to compute one public parameter, n symmetric session keys, and n secret shares and to encrypt and decrypt $n-\mathrm{1}$ shares. Therefore, the computation complexity of each participant is $O(\mathrm{4}n-\mathrm{1})$ . Since the aggregator needs to compute one public parameter, N symmetric session keys, N decryption, and n Lagrange basis polynomials, the computation complexity of the aggregator is $O(\mathrm{2}N+n+\mathrm{1})$ . In addition, participant i in subgroup boundary (i.e., $i=kn$ and $i=kn+\mathrm{1}$ , $i\ne \mathrm{1},N$ ) will need extra computation of symmetric session key in Phase 2, while others do not need any computations.

In Phase 1, every participant exchanges public parameter with its groupmates in the subgroup via the aggregator, which incurs communication of $O(\mathrm{2}|p|)$ bits, where $\left|p\right|$ represents the bit length of p. The participant needs to exchange the secret shares with its partners and the communication overhead is $O(n|q|)$ . Since the aggregator needs to send all messages to N participants, its communication overhead is $O(\mathrm{2}N(n-\mathrm{1})|q|+N(n-\mathrm{1})|p|)$ . In Phase 2, there is no extra communication overhead for the participants, and the aggregator only needs to send about $O(\mathrm{4}|q|N/n)$ messages.

6.1.2. Encrypt and Sum Processes

In Encrypt process, it is easy to see that every participant has a communication overhead of $O(\mathrm{2}|p|)$ and a computation complexity of $O(\mathrm{1})$ . In Sum process, the aggregator's computation overhead is $O(N+\mathrm{1})$ .

6.1.3. Leaving of Existing Participant

In this process, the assigned participant $i^{\prime }$ needs to compute n symmetric session keys and every participant in this subgroup has a computation overhead of $O(\mathrm{2})$ to compute the symmetric session key with $i^{\prime }$ and to update its permanent private key. Moreover, each one of these participants should compute one AES encryption and decryption. The leaving participant needs to compute one symmetric session key, one equality, and n 128-bit AES encryptions and decryptions, so its computation overhead is $O(\mathrm{4}n+\mathrm{1})$ . In addition, each adjacent neighbor of i (e.g., participant $i+\mathrm{1}$ or participant $i-\mathrm{1}$ ) has to change its time-dependent private key with the computation overhead of $O(\mathrm{2})$ . As we can see, the leaving participant i has a communication overhead of $O(\mathrm{2}n|q|)$ and the reused participant $i^{\prime }$ has that of $O(\mathrm{2}(n+\mathrm{1})|p|+\mathrm{2}|q|)$ . The aggregator sends $\mathrm{2}n$ public parameters and $\mathrm{2}n$ encrypted messages to the subgroup and two public parameters to the adjacent neighbors of leaving participant; therefore the communication overhead of the aggregator is about $O(\mathrm{4}n|p|+\mathrm{4}n|q|)$ .

6.1.4. Joining of New Participant

The joining participant has to compute its public parameter at first, and then it needs to compute n session keys and to decrypt and encrypt n messages. In addition, the joining participant needs to compute two equalities and two session keys to get its time-dependent private key. Thus, the computation complexity of i is $O(\mathrm{4}n-\mathrm{1})$ . Other members in its subgroup need to compute one session key to decrypt and encrypt a single message and to update the permanent private key. So, the computation complexity is $O(\mathrm{4})$ . Note that the adjacent neighbors of joining participant need to take extra computation to update their time-dependent private key. To our understanding, the joining participant has a communication overhead of $O(\mathrm{2}n|p|+\mathrm{2}(n-\mathrm{1})|q|)$ and the reused participant has that of $O(\mathrm{2}|p|+\mathrm{2}|q|)$ . And we conclude that the aggregator's communication overhead is also $O(\mathrm{4}n|p|+\mathrm{4}n|q|)$ . Thus, the total complexities of aggregator and participants are summarized in Table 2.

Table 2

Complexity of our scheme.

Per meter	Computation	Communication
Setup	$$O(n)$$	$$O(n|p|+n|q|)$$
Encrypt	$$O(\mathrm{1})$$	$$O(|p|)$$
Aggregator	Computation	Communication
Setup	$$O(N)$$	$$O(Nn|q|+Nn|p|)$$
Sum	$$O(N)$$	$$O(N|p|)$$
Meter leaving	∖	$$O(n|p|+n|q|)$$
Meter joining	$$O(\mathrm{1})$$	$$O(n|p|+n|q|)$$
Leaving/joining meter	Computation	Communication
Meter leaving	$$O(n)$$	$$O(n|q|)$$
Meter joining	$$O(n)$$	$$O(n|p|+n|q|)$$
Subgroup mates	Computation	Communication
Meter leaving	$$O(\mathrm{1})$$	$$O(|p|+|q|)$$
Meter joining	$$O(\mathrm{1})$$	$$O(|p|+|q|)$$
Reused meter	Computation	Communication
Meter leaving	$$O(n)$$	$$O(n|p|)$$
Meter joining	$$O(\mathrm{1})$$	$$O(|p|+|q|)$$

6.2. Evaluation by Implementation

The Encrypt process may be run by the participant with constrained resources and the sum is run on the aggregation side. So the performance of encryption is more important in the aggregation protocols. As is pointed out, EPPP4SMS is much faster in encryption than many protocols that use Paillier's scheme [7]. Therefore, in this simulation, we only compare the performance of our protocol with other two existing aggregation protocols in [6] (specifically, Jung's advanced protocol) and [7] (EPPP4SMS). To simulate and measure the computation overhead, the aggregation protocols are all implemented in Java in a computer with Intel i3-2100 CPU @ 3.10 GHz and 3 GB of RAM, and each result is the average time measured in the 1,000 times of executions. Also, the input data $x_i$ is a random number less than 100,000. In our protocol and Jung's advanced sum protocol, q is of 512-bit length, and p is roughly of 520-bit length, while EPPP4SMS uses 512 bits for the exponents and primes with 512 bits. Thus, the ciphertexts in these protocols are roughly of 1024-bit length.

First of all, we compared the participant's computation overhead in setup of our sum protocol and Jung's protocol. We do not simulate the setup phase of EPPP4SMS for the reason that it does not cover the same security assumption with ours and Jung's protocol. It is clear that the computation overhead of each participant in Setup phase only depends on the number of colluders if the length of ciphertext is fixed. We measured the total computation time of each participant spent in calculating its final encryption keys with different number of colluders and the results are shown in Figure 2. As we can see in Figure 2(a), the setup time for each participant of our protocol in the first aggregation is almost the same as Jung's protocol. However, as aforementioned, Jung's protocol needs to set up for every round of aggregations, while our scheme only needs one setup during all of the aggregations. Obviously, our protocol is much more efficient for the time-series data aggregation and the conclusion is in accordance with the simulation results in Figure 2(b).

Figure 2

The time spent in setup phase. (a) The dependence of number of colluders and setup time for each participant in the first aggregation. (b) The dependence of number of aggregations and the total time for setup for each participant (here the number of colluders is set to 800).

The independence of computation time of encryption (decryption) for each participant (aggregator) and the number of colluders is shown in Figure 3. In Figure 3, we set the total number of participants to 2,000, while the number of colluders ranges from 50 to 400. Figure 3(a) suggests that the number of colluders has a negligible influence on the computation times of each participant spent in encryption and Figure 3(b) indicates that the number of colluders does not affect significantly the decryption time of aggregator. In addition, Figure 3 shows that the encryption efficiency can be improved by around 300 times (from about 15 ms to 0.05 ms) when exponentiations $H(t{)}^{p_i}\mathrm{mod}{p}^{\mathrm{2}}$ and $g^{f_{s_{i,i-\mathrm{1}}}(t)-f_{s_{i,i+\mathrm{1}}}(t)}$ are precomputed. Thus, we assume the number of coconspirators is 50 for our protocol and Jung's protocol in the following simulations. The independence of total number of participants and encryption time for each participant is shown in Figure 4. As suggested in Figure 4, our protocol is faster than EPPP4SMS in encryption if both our protocol and EPPP4SMS have the same length of ciphertexts. The simulation of our protocol ran in a mean time of 15.69 ms, while the EPPP4SMS ran in 17.30 for encryption. Because Jung's protocol only computes two modular multiplications in encryption, it has the most efficient encryption ran in about 0.016 ms. Moreover, our protocol takes 0.05 ms after deploying the “on-the-fly” method and EPPP4SMS has that of 0.38 ms in average. Nevertheless, Jung's protocol needs to recall time-consuming initialization for every aggregation; it turns out to be the most inefficient one for the time-series data aggregation. The dependence of total number of participants and decryption time for aggregator is shown in Figure 5. It indicates that the decryption time for the aggregator grows linearly with the number of participants. We can also see that EPPP4SMS has the most inefficient decryption when the total number of participants is small and these three schemes have an almost similar decryption time for large number of participants.

Figure 3

The independence of computation time of encryption (decryption) for each participant (aggregator) and the number of colluders. (a) encryption; (b) decryption.

Figure 4

The dependence of total number of participants and decryption time for aggregator.

Figure 5

The independence of the total number of participants and encryption time for each participant. (a) The encryption time of our scheme and EPPP4SMS. (b) The “on-the-fly” encryption time and the encryption time of Jung's protocol.

7. Conclusion

In this paper, we proposed a privacy-preserving aggregation scheme for time-series data without trusted key dealers. Our proposed scheme is experimentally shown to be scalable and faster in the encryption and decryption compared to some Paillier's cryptosystem based protocols. The reason of the outwardly inefficient setup in our scheme is that no trusted or semitrusted key dealer is assigned in the system and the communication channels between the participants and the aggregator are not secure. However, our scheme is shown to be much more efficient than Jung and Li's protocol in [6] with the same security assumption because Jung and Li's protocol is not the time-series data and its initialization should be repeated every time when a new sum is desired. In the proposed scheme, the aggregation results can be calculated efficiently after setup and each participant takes the same processing time independent of the number of participants considered in the aggregation.

The scheme is proposed to tolerate up to k collusive adversaries that will not tamper the computation but try to manipulate their parameters to infer others' private values. And the security of our scheme is formally analyzed and it is shown that the scheme is secure if the CDH problem is assumed to be intractable. Our proposed scheme provides verification as well as scalable encryption because the processing time of the encryption does not depend on the number of participants. The implementations of our scheme suggest that the proposed aggregation protocol is efficient for time-series data.