EPPP4SMS: Efficient Privacy-Preserving Protocol for Smart Metering Systems and Its Simulation Using Real-World Data

The main contribution of this paper is the construction of the efficient privacy-preserving protocol for smart metering systems (EPPP4SMS), which brings together features of the best privacy-preserving protocols in the literature for smart grids. In addition, EPPP4SMS is faster on the meter side—and in the whole round (encryption, aggregation, and decryption)—than other protocols based on homomorphic encryption and it is still scalable. Moreover, EPPP4SMS enables energy suppliers and customers to verify the billing information and measurements without leaking private information. Since the energy supplier knows the amount of generated electricity and its flow throughout electrical substations, the energy supplier can use this verification to detect energy loss and fraud. Different from verification based on digital signature, our verification enables new features; for example, smart meters and their energy supplier can compute the verification without storing the respective encrypted measurements. Furthermore, EPPP4SMS may be suitable to many other scenarios that need aggregation of time-series data keeping privacy protected, including electronic voting, reputation systems, and sensor networks. In this paper, we present theoretical results of EPPP4SMS and their validation by implementation of algorithms and simulation using real-world measurement data.

SECTION I. Introduction

Security and privacy in smart grids are becoming an increasingly important issue. An adversary may violate customers’ privacy in smart grids, because they are more than computerized power grids. They may monitor and manage energy usage by means of many sensors that collect information about the flow of electricity. They are in majority composed by smart meters installed at the customers’ household. Such meters are able to reveal customers’ habits, e.g., the specific pattern of power consumption can reveal the TV program that someone is watching [1]. Without security and privacy, it is infeasible to deploy smart meters, whose society can take many benefits, mainly environmental and economic.

On one hand, the transition from power grid to smart grid is driven by climate change and economic concerns, e.g., reducing CO₂ emissions and avoiding the need for backup power plants, respectively. The deployment of smart meters is essential to achieve continuous electrical load balance, which gives us these benefits and is considered the main aspect of smart grid [2]. On the other hand, many customers are against the installation of smart meters, they are inhibiting the migration from an old power grid to a smarter grid [3]. For such customers, the lack of satisfactory security and privacy in the use of smart meters is unacceptable.

In this paper, we present the efficient privacy-preserving protocol for smart metering systems (EPPP4SMS) to preserve customers’ privacy and security in the network data communication. Thus, EPPP4SMS releases energy suppliers from handling their customers’ private data. Therefore, energy suppliers might outsource some services. Besides the description of the EPPP4SMS and its theoretical analysis, we also present a simulation using real-world measurement data. The simulation validates the theory and gives us a more tangible comparison with other protocols.

EPPP4SMS runs in the communication between smart meters and their energy supplier. We use an additive homomorphic encryption to create a different cryptographic primitive. Similar to other protocols [4], EPPP4SMS also protects the privacy using aggregation of customer data. Nevertheless, our approach has many benefits. For example, homomorphic encryption allows the decryption of a single measurement, while EPPP4SMS allows only the decryption of the aggregated measurements. In other words, whoever holds the private key can decrypt only the sum of the measurements. Consequently, smart meters can send their signed and encrypted measurements directly to their energy supplier. Since the encryption is end-to-end, the smart meters and their energy supplier can directly identify troubles in the communication.

EPPP4SMS is scalable and faster in the whole round than others are. Since the energy supplier receives the encrypted measurements and computes their aggregation, each smart meter spends the same processing time, independent of the number of measurements considered in the aggregation. When we increase the size of the keys, EPPP4SMS becomes increasingly faster than others with equivalent key size. EPPP4SMS only requires that smart meters hold merely a permanent private key to protect customers’ privacy, i.e., smart meters encrypt their measurements with the same key during every new round of measurements. Moreover, customers and their energy supplier can verify measurements and invoices keeping the customers’ privacy secure. The possibility of verification is important because machines might fail, as we find in the dataset of the simulation. Smart meters send only one message per measurement and an extra message per verification. The energy supplier can ask for verification when the sum of the measurements is different from the expected. Since the energy supplier knows the amount of generation and consumption of its customers, its staff can detect energy loss and fraud, which has been a problem in power grids [5].

Currently, many areas need privacy-enhancing protocols. These areas may use EPPP4SMS and its ideas. It is a protocol to a smart grid scenario, but its features improve significantly the techniques found in the literature.

The remainder of this paper is structured as follows. Section II presents the background necessary to understand this proposed protocol—especially related work. After that, the construction of EPPP4SMS is described in Section III and, thereafter, protocol analysis in Section IV and comparison with related work is given in Section V. Section VI presents how the simulation with real-world data was developed and its results. Section VII presents the conclusion about this research.

SECTION II. Background

In this section, we present definitions for some terms and cryptographic primitives used in this paper. We also present a review of related work.

A. Definitions

In the description of related work and the remainder of this paper, we use the following nomenclature.

1. Supplier is responsible to manage the power grid.

2. Customer is a household buyer or seller of electricity.

3. Meter is a temper-resistant device installed in customer residence, and that measures the flow of electric energy.

4. Consolidated measurement is the sum of the measurements of $N$ meters, i.e., $m_{1}+m_{2}+\cdots +m_{N}$ .

B. Cryptographic Primitives

Many privacy-enhancing protocols use Paillier’s scheme [6] because it is an additive homomorphic encryption. Thus, if two meters encrypt their measurements, ${\mathsf {Enc}}(m_{1})$ and ${\mathsf {Enc}}(m_{2})$ , then applying the product, they have the encrypted sum, that is $$\begin{equation} {\mathsf {Enc}}(m_{1})\cdot {\mathsf {Enc}} (m_{2})= {\mathsf {Enc}}(m_{1}+m_{2}). \end{equation}$$

The encryption function Enc with the additive homomorphic property from (1) presented by Paillier is given by $$\begin{equation} \begin{split} {\mathsf {Enc}}\,:\,\mathbb {Z}_{n}\times \mathbb {Z}^{*}_{n} &\longmapsto \mathbb {Z}_{n^{2}} \\ {\mathsf {Enc}}(m,r) &\longmapsto g^{m}\cdot r^{n} \mod n^{2} \end{split} \end{equation}$$ where $m$ is a measurement, $n=p\cdot q$ with $p$ and $q$ safe primes such that $n$ divides the order of a random number $g\in \mathbb {Z}^{*}_{n^{2}}$ defined by the supplier, and $r$ is a random number chosen by the meter. Only the supplier knows the primes. The public key is composed of $n$ and $g$ . The private key is the Carmichael’s function $\lambda (n) = \operatorname {lcm}(p - 1, q -1)$ . The requirement that $n$ divides the order of $g\in \mathbb {Z}^{*}_{n^{2}}$ ensures that (2) is a bijection. From (2), the aggregation of encrypted measurements $c$ is given by $c= {\mathsf {Enc}}(m_{1},r_{1})\cdot {\mathsf {Enc}} (m_{2},r_{2}) = g^{m_{1}}r_{1}^{n}g^{m_{2}}r_{2}^{n} \mod n^{2} = g^{m_{1}+m_{2}}(r_{1}r_{2})^{n}\mod n^{2} = {\mathsf {Enc}}(m_{1}+m_{2},r_{1}r_{2})$ . The product is performed over $\mathbb {Z}_{n^{2}}$ and the addition over $\mathbb {Z}_{n}$ .

The decryption function Dec is given by $$\begin{equation} \begin{split} {\mathsf {Dec}}\,:\,\mathbb {Z}_{n^{2}} &\mapsto \mathbb {Z}_{n} \\ {\mathsf {Dec}}(c) &\mapsto \frac {L\left (c^\lambda \mod n^{2}\right )}{L\left (g^\lambda \mod n^{2}\right )} \mod n \end{split} \end{equation}$$ where $L(u)=(u-1)/n$ . Since, the denominator is constant, it can be precomputed to speed up the processing time. Thus, the decryption is practically one modular exponentiation.

Notice that Dec does not depend on the random numbers. Therefore, we can write ${\mathsf {Dec}}( {\mathsf {Enc}}(m_{1})\cdot {\mathsf {Enc}} (m_{2}) \mod n^{2})=m_{1}\,+\,m_{2} \mod n.$ EPPP4SMS is one novelty based on Paillier’s scheme [6].

C. Related Work

There is much related work in the literature. Here, we present the most relevant to our contribution in this paper. For simplicity, we show the protocols only for one round of measurements.

1) In-Network Aggregation:

Li et al. [7] introduced a privacy-enhancing protocol based on data aggregation, which uses Paillier’s scheme. To solve the malleability introduced by Paillier’s scheme, Li and Luo [8], introduced the use of homomorphic signature allowing verification to confirm the data aggregation was correct. In both papers, the protocols use in-network data aggregation, i.e., the data aggregation happens with participation of meters. Ruj and Nayak [9] presented a different case of in-network aggregation based on access control. The aggregation also uses Paillier’s scheme, but occurs in network devices, i.e., in home area network (HAN), building area network (BAN), and neighboring area network (NAN).

2) Measurements Directly to the Supplier:

Mármol et al. [10] presented a protocol in which each meter adds its key to its measurement and sends the result to the supplier. The result of the addition is the encrypted measurement, but the protocol also uses key agreement and authentication to establish a secure channel. After that, a meter aggregates all keys and sends their sum to the supplier. Such meter is called the key aggregator. The supplier decrypts the sum of all encrypted measurements, subtracting the value received from the key aggregator. Mármol et al. [10] emphasize that their work allows each meter to send its measurement directly to the supplier.

3) No Online Aggregator:

Erkin and Tsudik [11] presented a protocol based on Paillier’s scheme in which each meter sends a random number to each other meter. To avoid the overhead of messages, meters can share seeds to generate the numbers using a pseudorandom number generator. The main idea is that all random numbers can cancel each other when Paillier’s scheme is applied. For instance, if $r_{i\rightarrow j}$ is the random number that the meter $i$ sent to meter $j$ , then each meter $i$ computes the function $R(i)=n+\sum _{j=1,i\neq j}^{N} r_{i\rightarrow j}-\sum _{j=1,i\neq j}^{N} r_{j\rightarrow i},$ and apply the $R(i)$ to ${\mathsf {Enc}}(m_{i})=g^{m_{i}}r_{i}^{R(i)},$ which is similar to (2). After each meter encrypts its measurement and sends to each other, we have $\sum _{i=1}^{N}R(i)=\sum _{i=1}^{N}n=Nn,$ thus Paillier’s scheme gives the sum of all measurements to all meters $\prod _{i=1}^{N} {\mathsf {Enc}}(m_{i})= {\mathsf {Enc}}\left (\sum _{i=1}^{N} m_{i}\right )$ .

4) EPPA: Efficient and Privacy-Preserving Aggregation:

Lu et al. [12] presented a variation of Paillier’s scheme [6]. They join $l$ measurements $m_{i1}, m_{i2}, \dots , m_{il}$ in the same encrypted message $C_{i}$ of the meter $i$ . Their encryption is given by $C_{i} = g_{1}^{m_{i1}}g_{2}^{m_{i2}}\cdots g_{l}^{m_{il}}r_{i}^{n} \mod n^{2},$ where $g_{1},g_{2},\dots ,g_{l}{\,\in \,} \mathbb {Z}_{n^{2}}$ and $r_{i}\in \mathbb {Z}^{*}_{n}$ as Paillier’s scheme. Meters sign the encrypted measurements and send them to the local gateway that aggregates them. The gateways check the signatures, generate a previous aggregation, and send the result to the supplier. We can say that the aggregation is $C =\prod _{i=1}^{N} C_{i} \mod n^{2}=g^{M}R^{n} \mod n^{2},$ where $M = a_{1}\sum _{i=1}^{N} m_{i1}+ a_{2}\sum _{i=1}^{N} m_{i2}+\cdots +a_{1}\sum _{i=1}^{N} m_{il}$ and $R = \prod _{i=1}^{N} r_{i}.$ A trusted third party should set up the keys and initial parameters, such that $a_{1}{=}1$ and the other $a_{i}$ form an increasing sequence of primes. Hence, computing $M \mod a_{2}$ , we have $d_{1}=\sum _{i=1}^{N}m_{i1}$ . Computing $M-d_{1} \mod a_{3}$ , we have $d_{2}=\sum _{i=1}^{N}m_{i2}$ and so on.

5) Aggregation of Time-Series Data:

Recently, Joye and Libert [13] presented an interesting scheme based on the idea of splitting the exponent from [11], like EPPP4SMS. To encrypt the measurements, their scheme computes $c_{i,t} = (1 + m_{i,t}n) \cdot {\mathsf {H}} (t)^{s_{i}} \mod n^{2},$ where $m_{i,t}$ is the measurement of the meter $i$ in the time $t$ , $n$ is the product of two primes, ${\mathsf {H}}(t)$ is a hash function, and $s_{i}$ is the private key of the meter $i$ . The supplier has the private key $s_{0}=-\sum _{i=1}^{N}s_{i}.$ Thus, for every round of measurements, the supplier computes ${\left (\left ( {\mathsf {H}}(t)^{s_{0}}\prod _{i=1}^{N}c_{i,t} \mod n^{2}\right ) -1\right )}/{n}$ in order to obtain the consolidated measurement. A trusted third party generates initial parameters and keys during the setup phase.

Their paper was inspired by a nonscalable privacy-preserving aggregation of time-series data [14]. There is already a line of work on privacy-preserving aggregation of time-series data [7]–​[14]; compared to these approaches, our solution is novel because we address two dimensions [4], namely: consolidated consumption and billing information.

SECTION III. Our Construction: EPPP4SMS

We assume the existence of a public key infrastructure (PKI) in order for meters to sign their measurements. The signature Sign ensures that a message comes from a legitimate meter, and also ensures that no adversary changed the message. In summary, the signature is used for security reasons. The function Enc is responsible to ensure privacy.

In the initial set up, the supplier chooses two safe primes $p$ and $q$ , and a $g\in \mathbb {Z}^{*}_{n^{2}}$ such that the order of $g$ is high and is divisible by $n$ , where $n=p\cdot q$ . Each meter needs to choose two random numbers $k_{1}$ and $k_{2}$ as part of its permanent key. We assume that each meter $i$ chooses randomly a number $k_{1_{i}}{\,<\,}2^{L}$ , where $L=\max \,\{x\in \mathbb {Z}\mid x\le \log _{2}(\min (p,q))\}$ . Thus, they can aggregate their chosen numbers to determine their sum in many ways—for instance, using the scheme presented in [7]. After the meters aggregate their numbers $K_{1}=\sum _{i=1}^{N}k_{1_{i}}$ and send the result $K_{1}$ to their supplier that can determine an integer constant $d_{1}=n-K_{1}$ . Analogously, the meters can determine another random number $k_{2_{i}}$ such that $k_{1_{i}}\neq k_{2_{i}}$ and the supplier can determine $d_{2}=n-K_{2}$ . The values of $d_{1}$ and $d_{2}$ are important to the process of decryption.

Similar to Paillier’s scheme, the supplier public key is $n$ and $g$ . Nevertheless, each meter has also its permanent private key composed by $k_{1}$ and $k_{2}$ , instead of one public key. Likewise, (2), we define the encryption function Enc as $$\begin{align} {\mathsf {Enc}}_{i}\,:\,\mathbb {Z}_{n}\times \mathbb {Z}^{*}_{n^{2}}\times \mathbb {Z}^{*}_{n^{2}} \mapsto & \mathbb {Z}_{n^{2}} \notag \\ {\mathsf {Enc}}_{i}(m,h_{1_{t}},h_{2_{t}}) \mapsto & g^{m}\cdot h_{1_{t}}^{k_{1_{i}}}\cdot h_{2_{t}}^{k_{2_{i}}} \mod n^{2}\quad \end{align}$$ where $h_{1_{t}}$ and $h_{2_{t}}$ are nonces over $\mathbb {Z}^{*}_{n^{2}}$ . These nonces are created by a hash function to avoid relations between rounds of measurements.

We can assume the existence of a secure hash function H and define $h_{1_{t}}= {\mathsf {H}}(t||1)$ and $h_{1_{t}}= {\mathsf {H}}(t||2)$ , where $t$ is a timestamp for every round of measurements and the symbol $||$ represents the concatenation. The timestamp cannot be repeated and its values may be sequential and may be contained in the requests for new round of measurements.

The hash function ensures that previous encrypted measurements will not be correlated to obtain information from the measurements. We present in Section IV-B details about the importance of using a hash function, such that $h_{1}\neq h_{2}$ , and their modular exponentiations, such that $k_{1_{i}}\neq k_{2_{i}}$ .

Due to the exponents $k_{1_{i}}$ and $k_{2_{i}}$ , we have a family of functions ${\mathsf {Enc}}_{i}$ , instead of one encryption function. We also choose a hash instead of a random number among other changes; nonetheless, such choices do not change the additive homomorphic property inherited from Paillier’s scheme. Moreover, EPPP4SMS allows decryption, if and only if all encrypted messages were multiplied, which implies that all measurements were added up.

Given the family of functions from (4), each meter $i$ encrypts its measurement $m_{i}$ computing ${\mathsf {Enc}}_{i}(m_{i},h_{1_{t}},h_{2_{t}}) =g^{m_{i}}\cdot h_{1_{t}}^{k_{1_{i}}}\cdot h_{2_{t}}^{k_{2_{i}}} \mod n^{2}$ and sends the encrypted measurement directly to the supplier. For simplicity, we can denote ${\mathsf {Enc}}(m_{i})= {\mathsf {Enc}}_{i}(m_{i},h_{1_{t}},h_{2_{t}})$ .

To decrypt the consolidated consumption, the supplier needs to multiply all encrypted measurements, that is $$\begin{equation*} \prod _{i=1}^{N} {\mathsf {Enc}}(m_{i})= g^{m_{1}+m_{2}+\cdots +m_{N}}h_{1}^{n-d_{1}}h_{2}^{n-d_{2}} \mod n^{2} \end{equation*}$$ and multiply the result by $h_{1}^{d_{1}}h_{2}^{d_{2}}$ . Using the same decryption function Dec from Paillier’s scheme, we obtain $$\begin{equation*} {\mathsf {Dec}}\left (h_{1}^{d_{1}}h_{2}^{d_{2}}\prod _{i=1}^{N} {\mathsf {Enc}}(m_{i}) \mod n^{2} \right )= \sum _{i=1}^{N}m_{i} \mod n. \end{equation*}$$ To see that we can use the same decryption function Dec with $h_{1}^{d_{1}}h_{2}^{d_{2}}$ , in (3), remember the following property: $$\begin{equation*} \forall ~w\in \mathbb {Z}^{*}_{n^{2}},~\begin{cases} w^\lambda \equiv 1 \mod n,\\ w^{n\lambda }\equiv 1 \mod n^{2}. \end{cases} \end{equation*}$$ Therefore, $h_{1}^{n\lambda }h_{2}^{n\lambda }\equiv 1 \mod n^{2}.$ For this reason, the random number in Paillier’s scheme is not important in the decryption.

We show in Section IV that EPPP4SMS enables the verification of measurements. The same verification can be used to verify the invoice values. For example, the meters can send their billing information at the end of a period—perhaps a day or a week—and, then, the supplier and the meters can verify whether the sum of the measurements is right or wrong. If at the end of a day the electric energy has three different prices, the meters need to send their consumption for each price. Another option is to set up the meters to send the measurements in financial values instead of watts.

SECTION IV. Protocol Analysis

In this section, we present how meters and their supplier can use the property of verification. We also present analyses of privacy and security. We finish this section with a discussion about parameters that may be used in EPPP4SMS and their implications in the performance of processing time.

A. Verification Property

In case of defect, if a meter did not send its measurement or send an invalid-signed message, the supplier knows exactly which meter it is. Thus, the supplier can request the meter to resend the message or provide a fix to hardware problems. In the meantime, the supplier cannot read consolidated consumption. Nevertheless, meters can cooperate to disclose the key of the damaged meter. The meter cooperation can disclose the sum of the keys of others, but they cannot disclose individual keys, unless $N-1$ meters cooperate. A better solution is the generation of new keys for nondamaged meter.

If the supplier identifies that something is wrong and asks for verification, a meter $i$ can reveal its measurement $m_{i_{t}}$ of the round $t$ without disclosing its permanent key. To perform a verification over a sent encrypted value $c$ of the meter $i$ , the supplier sends a request to the meter, which might send $m_{i_{t}}$ and $v=h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}}$ to the supplier. Therefore, the sent encrypted value is verified if $c\stackrel {?}{=} g^{m_{i_{t}}}\cdot v.$ From the perspective of privacy, the verification should be based on the sum of all accumulated measurements, instead of disclosing individual measurements. The supplier and meters can verify the sum of all measurements, which is much more privacy-friendly than sharing individual measurements. Notice that billing information is shared with the supplier in nonsmart grids already. In the same way a measurement is proven, the meters can prove their billing information or the sum of measurements. They need to store the product $V=\prod v_{t}$ of all $v_{t}=h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}}$ , where $t$ is the round based on a sequential or chronological timestamp. For example, at the end of one day, the meter $i$ sends $V$ and the consumption of the day $M=\sum m_{i_{t}}$ to its supplier that has stored the product of all encrypted measurements $C=\prod g^{m_{i_{t}}}h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}}$ from the meter $i$ . If $C \stackrel {?}{=} g^{M}\cdot V,$ then the meter proves whether its billing information is correct or not. Moreover, the meter still can use its permanent key for every new round.

B. Privacy Analysis

Suppose that an adversary has access to the private key $\lambda$ of the supplier. The adversary can intercept one message in the round $t$ and try to decrypt it ${\mathsf {Dec}}(g^{m_{i_{t}}}h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}})$ , but the adversary has no information about $m_{i_{t}}$ , neither $k_{1_{i}}$ , and neither $k_{2_{i}}$ , because $h_{1_{t}}$ and $h_{2_{t}}$ are cancelled when they are raised to the power of $n\lambda$ . Otherwise, the decryption returns no information, for the same reason that the random number $r$ is cancelled when we raise $r$ to the power of $n\lambda$ in Paillier’s scheme [6]. Showing details of this property inherited from Paillier’s scheme is beyond the scope of this paper, but we show what the adversary can see. Trying to decrypt an individual measurement leads to $$\begin{equation} \frac {L\left (\left (g^{m_{i_{t}}}h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}}\right )^\lambda \mod n^{2}\right )}{L(g^\lambda \mod n^{2})} \mod n \end{equation}$$ where $L(u)=(u-1)n^{-1}$ , which results in $m_{i_{t}}h_{1_{t}}^{k_{1_{i}}\lambda }h_{2_{t}}^{k_{2_{i}}\lambda } \mod n$ . The adversary only has success if the cancelling of $h_{1_{t}}$ and $h_{2_{t}}$ in (5) can be done in polynomial time, but this is considered an intractable problem. The adversary can also try to guess the value of $m_{i_{t}}$ and try to discover the values of $k_{1_{i}}$ and $k_{2_{i}}$ . Suppose that an adversary uses an intercepted encrypted measurement to disclose $k_{1_{i}}$ and $k_{2_{i}}$ , when the values $g$ , $n$ , $\lambda$ and $m_{i_{t}}$ are known by the adversary. Thus, this adversary can compute $$\begin{equation} \frac {L\left (\left (h_{1_{t}}^{k_{1_{i}}}h_{2_{t}}^{k_{2_{i}}}\right )^\lambda \mod n^{2}\right )}{L((h_{1_{t}}h_{2_{t}})^\lambda \mod n^{2})} \mod n. \end{equation}$$ However, (6) does not return the values of $k_{1_{i}}$ and $k_{2_{i}}$ , since $k_{1_{i}}\neq k_{2_{i}}$ and $h_{1_{t}}\neq h_{2_{t}}$ .

If some adversaries try to use encrypted measurements from the same meter $i$ in different measurement rounds, e.g., $t=1$ and $t=2$ , then they may find $$\begin{equation} g^{m_{i_{1}}+m_{i_{2}}}h_{1_{1}}^{k_{1}}h_{2_{1}}^{k_{2}}h_{1_{2}}^{k_{1}}h_{2_{2}}^{k_{2}} \end{equation}$$ or $$\begin{equation} g^{m_{i_{1}}-m_{i_{2}}}h_{1_{1}}^{k_{1}}h_{2_{1}}^{k_{2}}h_{1_{2}}^{-k_{1}}h_{2_{2}}^{-k_{2}} \end{equation}$$ which again returns no information because the values generated by H are not cancelled, unless $h_{1_{1}}=h_{1_{2}}^{-1}$ and $h_{2_{1}}=h_{2_{2}}^{-1}$ in (7) or $h_{1_{1}}=h_{1_{2}}$ and $h_{2_{1}}=h_{2_{2}}$ in (8). However, this possibility is negligible because the values come from a secure hash function.

The adversary can collect the encrypted measurements from all meters in the same round $t$ and discover the consolidated consumption, if and only if the adversary has the private key of the supplier. However, it is also possible to collect all encrypted measurements from the same round and leave out the encrypted measurement from a meter $i$ , that is $$\begin{equation} g^{m_{1}+m_{2}+\cdots +m_{N}-m_{i}}h_{1_{t}}^{n-d_{1}-k_{1_{i}}}h_{2_{t}}^{n-d_{2}-k_{2_{i}}} \end{equation}$$ which again does not cancel $h_{1_{t}}$ and $h_{2_{t}}$ .

Considering $k_{1_{i}}\neq k_{2_{i}}$ and $h_{1_{t}} \neq h_{2_{t}}$ , (9) shows that an individual measurement cannot be decrypted by an adversary. Equation (5) shows that $k_{1_{i}}$ and $k_{2_{i}}$ cannot be recovered from an encrypted measurement. Equations (7) and (8) show that there is no relation between the rounds. Equation (9) shows that an adversary cannot decrypt partial measurements, i.e., only the consolidated measurement, if the private key of the supplier is known.

C. Security Analysis

If an adversary cannot decrypt an individual measurement with the knowledge of the private key of the supplier, it is much harder to decrypt a measurement without the key. In addition, if a meter $i$ sends a message containing its encrypted measurements and its signature, i.e., ${\mathsf {Enc}}(m_{i})|| {\mathsf {Sign}}_{i}$ , then any adversary can compromise the message. As meters are temper resistant or they have trusted modules by definition, then only the meter can sign its measurements. The signature Sign also avoids malleability and allows the supplier to detect failures. Moreover, the invoice can be verified, even without signature.

As only the consolidated consumption can be decrypted, the supplier might outsource the aggregation. An adversary cannot use malleability to change the consolidated consumption, i.e., an adversary cannot aggregate twice the same encrypted measurement $m_{i}$ , because it leads to $g^{m_{1}+m_{2}+\cdots +m_{N}+m_{i}}h_{1}^{n-d_{1}+k_{1_{i}}}h_{2}^{n-d_{2}+k_{2_{i}}}$ , which shows that the consolidated consumption plus $m_{i}$ are encrypted, because $h_{1_{t}}$ and $h_{2_{t}}$ are not cancelled.

To obtain $k_{1_{x}}$ of a meter $x$ , the adversary needs to know the sum of all other keys $\sum _{i\neq x} k_{1_{i}}$ and $n-d_{1}$ . Similar reasoning is valid for $k_{2_{x}}$ . However, given $k_{1_{i}}$ or $k_{2_{i}}$ an adversary can use (6) to discover $k_{2_{i}}$ or $k_{1_{i}}$ , respectively. Other security issues are the same as Paillier’s scheme.

An important question may arise: is an adversary able to solve the discrete logarithm modulo a composite? That is $h^{k} \!\!\!\mod n$ . In the following, we show that solving composite discrete logarithms implies integer factorization, which is an intractable problem for a classical computer [15]. We may realize that given $y$ , $h$ , $n$ , and $y\equiv h^{k} \mod n$ is infeasible to determine $k$ . Indeed, finding $k$ is the discrete logarithm problem. Thus, given $h$ and $h^{\varphi (n)}\equiv 1 \mod n$ , where $\varphi (n)=(p-1)(q-1)$ , determining $\varphi (n)$ is as infeasible as $k$ . If we could find efficiently the exponents, we could choose different values of $y$ to find $\varphi (n)$ . Since, $\varphi (n)=n-(p+q)+1$ , hence $p+q=n-\varphi (n)+1$ . However, if the sum and the product of $p$ and $q$ are given, then we can easily find the prime factors in an intersection of the curve $x\cdot y=n$ with the curve $x+y=p+q$ .

One can argue that an adversary can select special values to $p$ and $q$ in order for a posteriori easily to solve the discrete logarithm problem. Nevertheless, the meters can verify whether $n$ is a product of two safe primes or not [16]. Other argumentation is that $h$ might have low order, and, thus, an adversary can find an exponent smaller than $k$ that is congruent to $k$ . However, meters can verity if $h$ has a high order because $n$ is a product of safe primes.

D. Parameters and Performance

Secure parameters that keep a good performance depend on the best algorithms to solve the integer factorization problem and the discrete logarithm problem. The first may be solving with general number field sieve (GNFS) [17]. The second may be solving with brute force attack, or with some algorithm that depends on the factors of $n$ , or that depends on the size of the fields [18]. However, to find $k$ given $h$ , $n$ , and $h^{k}\! {\,\mod \,} n$ , the algorithms try to solve a discrete logarithm problem with subexponential time on $n$ like the GNFS. If $k$ is too small, a brute force attack is much more efficient, although its complexity is $2^{k}$ . To search for the exponent, one may use Pollard’s rho or Baby-step giant-step algorithm for logarithms that has complexity $\sqrt {2^{o}}$ [19], where $o$ is the bit length of the order of $h$ . If we stipulate a maximal bit length of $k$ as standard, then this value may be attributed to $o$ . In this case, the complexity is $2^{k/2}$ . Thus, we can compare the complexity to find the exponent with the complexity of integer factorization. As result, we have the best parameters for EPPP4SMS, and we can compare them with the Paillier’s scheme.

Asymptotically, the GNFS still has the best heuristic time: $\exp \,\left ((64/9)^{1/3+O(1)}\log (n)^{1/3}\log (\log (n))^{2/3}\right )$ . The value of $O(1)$ tends toward zero when the processing time becomes faster. Thus, we can calculate the relation $$\begin{equation} \exp \,\left (\left (64/9\right )^{1/3}\log (n)^{1/3}\log (\log (n))^{2/3}\right )=2^{k/2} \end{equation}$$ between $n$ and $k$ , to keep the same level of security. We found the values of $n$ and $k$ from (10) and present them in Fig. 1 with $\lceil k \rceil =\min \,\{x\in \mathbb {Z}\mid x\ge k\}$ . They are close to twice the value of keys to symmetric algorithms and in the range for bit length of keys to algorithms based on elliptic curve cryptography (ECC) specified in the Federal Information Processing Standards Publications (FIPS 800-57 Part 1—Revision 3) by National Institute of Standards and Technology (NIST). The value 4096 does not appear in such FIPS.

Fig. 1.

Relation between the levels of security based on the bit length.

The most costly operation in Paillier’s scheme and in EPPP4SMS is the modular exponentiation, which is processed in $O(\log _{2}(e))$ , where $e$ is the bit length of the exponent [20]. Thus, reducing the bit length of the exponents is equivalent to speeding up the processing time. Paillier’s encryption needs to raise a random number to the power of $n=pq$ , and EPPP4SMS needs to raise hashes to the power of $k_{1}$ and $k_{2}$ , in the encryption function. Discounting $g^{m}$ that is equal in both protocols, Paillier’s scheme has complexity $O(\log _{2}(n))$ to encrypt when EPPP4SMS has $2O(\log _{2}(\lceil k \rceil ))$ . Therefore, we can see in Fig. 1 that EPPP4SMS is faster to encrypt, and the difference of processing time increases significantly when the level of security increases. Contrarily, Paillier’s scheme is faster to decrypt than EPPP4SMS. The former needs only one modular exponentiation with the size closer to $n$ , namely $\lambda$ . The latter needs three modular exponentiations, namely $d_{1}$ , $d_{2}$ and the same as the former. The length of the two additional exponents depends on the number of aggregated meters, but generally they are closer to the length of $n$ . For example, if $p$ and $q$ have 1024 bits each, then $n$ is chosen with 2048 bits, $k_{1}$ and $k_{2}$ are chosen with 234 bits each. Thus, $d_{1}$ has $2^{2048} -N 2^{234}$ bits, where $N$ is the total number of meters in the aggregation. Therefore, the aggregation should have $2^{1814}$ meters to $d_{1}$ and analogously $d_{2}$ be equal to zero. Thus, we can say that Paillier’s scheme has complexity $O(\log _{2}(n))$ to decrypt when EPPP4SMS has $3O(\log _{2}(n))$ . However, the decryption is as fast as $\log _{2}(d_{1} \mod n)$ and $\log _{2}(d_{2} \mod n)$ are close to zero. For huge number of meters, the decryption might become $O(\log _{2}(n))$ .

On one hand, EPPP4SMS is much faster to encrypt on the meter side that has many meters with constrained hardware. On the other hand, EPPP4SMS is around three times slower to decrypt on the supplier side; nonetheless, such decryption happens only once for every round.

SECTION V. Relation to Previous Work

We present the best possibility for each protocol in Table I. The column setup presents the complexity of the number of messages necessary to establish the keys to provide privacy or authentication. The column key shows the total number of keys that each meter uses to encrypt its measurements to provide privacy. The column previous aggregation indicates if the protocol uses previous aggregation per round, i.e., before the protocol sends the measurements to the supplier. The column messages presents the total number of messages that the meters need to send by round. The column direct indicates whether the protocol sends messages directly to the supplier, or not. The column verification shows which protocols allow meters and their supplier to certify that their measurements are correct.

TABLE I Comparison With Related Work

Regarding the processing time, we classify the protocols in two sets, based on either modular exponentiation or ECC, which is normally faster. EPPP4SMS is based on modular exponentiation as well as [12], [13], and Paillier’s scheme [6] that is used in [7], [9], and [11]. A key exchange that might be modular exponentiation or ECC is used in [10]. A bilinear map is used in [8], namely, in ECC. Therefore, using the best configuration of other protocols, only two of them might be faster than EPPP4SMS for encrypting individual measurements. Nevertheless, we may see in Table I that EPPP4SMS has at least two advantages over the others.

EPPP4SMS is more robust than the others are. For example, in [7]–​[9] and [12], if an adversary has access to the private key of the supplier and can intercept encrypted measurements, the adversary can decrypt them. In [10], key agreement and authentication schemes are used to protect the communication channel, because if an adversary has access to the communication channel, all messages can be decrypted and disclosed. Another weakness is if an adversary has access to the key aggregator and to the messages sent to the supplier. In [11], it is only possible to reduce the huge number of keys, if we leave security behind and assume trust between the meters. The number of keys is huge because the total number of keys in the set of meters grows quadratically in relation to the number of meters $N$ , i.e., $O(N^{2})$ . As aforementioned, [12] and [13] are strongly based on TTP to set up the parameters.

Only [8] and EPPP4SMS provide verification. In [8], the verification is incremental; thus, it is necessary to store the messages and search them with complexity $O(\log _{2}(N))$ . EPPP4SMS is direct, i.e., the supplier verifies the signature generated by the meter and if necessary, the meter proves its measurements with complexity $O(1)$ in relation to the number of meters. Moreover, the verification of [8] is per round, i.e., it verifies if every meter aggregates correctly, while EPPP4SMS provides verification per single or multiples measurements without necessity of storing them.

Besides verification, we can detect energy loss in $\log _{2}(N)$ rounds, where $N$ is the number of meters. Salinas et al. [5] presented three protocols that need the expected consumption and communication between the meters to solve a linear system of equations in order for the supplier to receive an “honesty coefficient.” Since the system of equation generates a square matrix, the number of rounds should be equal to the number of measurements per round. To ensure linear independence, the number should be large. The supplier only receives the “honesty coefficients” from each meter, after meters communicate with each other to compute their “honesty coefficients.” Moreover, they can only compute their coefficients after a large number of rounds. In contrast, EPPP4SMS provides the consolidated consumption to the supplier, which can compare with the expected consumption without communication between the meters.

SECTION VI. Simulation With Real-World Data

Though there is a discussion about the complexity of EPPP4SMS in relation to Paillier’s scheme in Section IV-D, and though there is a comparison with related work in Section V, we cannot estimate in seconds the difference in processing times, which depends on the measurements, number of meters, rounds and other factors. For this reason, we present the performed simulation with real-world data and the obtained results in this section.

The dataset used in the simulation has 157 992 996 measurements, which were collected from 6435 meters. They reported consumption with intervals of 30 min. The measurements start to register the consumption from 00:00:00 to 00:29:59 on Tuesday on July 14, 2009, and the last consumption from 23:30:00 to 23:59:59 on Friday on December 31, 2010. The meters that reported the measurements were installed in Irish homes and businesses.

A. Verification

We constructed a protocol that enables verification of measurements because machines might fail. Indeed, we detected in the dataset that two meters presented errors. They sent two measurements in the same round for six times. Moreover, the values of the reported measurements are different from each other in the same round. Thus, the problem was not only a duplicated message, and each of the two meters repeats the same error in six rounds. In total, we have 24 measurements in which at least 12 are certainly wrong, but we cannot verify from the dataset which one is correct or wrong. If the meters were running EPPP4SMS, we could verify. As we cannot verify or ask for new measurements, we decided to eliminate these 24 measurements.

We also detected some issues in the timestamp. The firsts 30 min are coded as 1 in the dataset, namely, the interval from 00:00:00 to 00:29:59 is coded as 1. The interval from 00:30:00 to 01:00:00 is coded as 2, and so on. As the day has 24 h, the time code of a normal day goes from 1 to 48. We also detected 25 002 messages with time code bigger than 48. The majority, i.e., 24 462 measurements were coded as 49 and 50. We detected that 12 568 and 11 874 messages are due to daylight saving time on last Sundays of October 25, 2009, and October 31, 2010. However, 20 measurements were coded as 49 and 50 on normal days. Moreover, we found 540 messages with time code from 51 to 95 that may be errors. No time code was coded as zero. Again, we cannot verify, thus we decide to erase the messages with errors and code time bigger than 48 from the dataset.

Although the total number of error seems to be big, it is small in relation to the total number of measurements. These failures in the collected data are very important to recall our attention to the fact that machines might fail and a real-world dataset guides us to develop protocols with verification.

B. Complementation and Privacy

To preserve privacy, every one of the 6435 meters in the set should report its consumption in every new round. If a meter did not send its consumption because the value is zero, an adversary can know when there is consumption or not.

After we eliminate the lines with problems in the dataset, we have 1 557 216 measurements reporting zero consumption. However, not all meters send their consumption in all rounds. For this reason, we complement the missing measurements with zero. In the total, we insert 7 578 840 new zeros, reaching a total of 9 136 056 zeros.

C. Implementation of the Core Algorithms

We implemented the source code for EPPP4SMS and Paillier’s scheme that is used in many protocols. Both implementations were written in C and compiled with GCC version 4.4.6 for GNU/Linux with Red Hat distribution. We also used the GNU multiple precision arithmetic library (GMP) to manipulate big numbers and the open multi processing (OpenMP) to parallelize the encryption.

The computer used was an Intel^® Xeon^®, CPU E5-2620 of 2.00 GHz, 12 recognized cores, and 70 Gigabytes of shared memory.

D. Simulation Parameters

After we sanitized the dataset, we have 6435 meters times 25 726 timestamps that gives us 165 546 810 measurements. While we should aggregate the measurements of 6435 meters per round, we decided to parallelize the encryption in 11 threads and leave the aggregation and decryption in one thread.

Since we used real-world data, we only needed to determine the primes, $g$ , and the exponents $k_{1_{1}},k_{1_{2}},\dots ,k_{1_{N}}$ and $k_{2_{1}},k_{2_{2}},\dots ,k_{2_{N}}$ that the other parameters are defined in the protocols. We used a pseudorandom number generator to select values with 174 bits for the exponents in EPPP4SMS and primes with 512 bits for both schemes; thus, $n$ has 1024 bits, which is equivalent to the level 1 of security in Fig. 1. Notice that level 1 provides the smallest difference in processing time between the protocols.

E. Simulation Results

We collected the processing time of the encryption, aggregation, and decryption. With their data and the programming language R, we present box plots of the observed processing time in Fig. 2.

Fig. 2.

Box plots of the processing time spent in parallelized encryption, aggregation, and decryption of the consolidated consumption.

As expected, EPPP4SMS is much faster in encryption than many protocols that use Paillier’s scheme. The simulation of EPPP4SMS ran in a mean time of 1284 ms, while the Paillier’s scheme ran in 3514 for encryption. The cost of the aggregation is equivalent in both protocols, namely, 35.08 against 36.88 ms on average. For decryption, Paillier’s scheme is around three times faster than EPPP4SMS. The mean time of the former was 13.47 ms, and for the latter was 4.71 ms. Nevertheless, the encryption should run on the meter with constrained resources and the decryption should run on the supplier side. Moreover, the benefit of around 2230 ms using 11 threads in the encryption is much bigger than the drawback of around 9 ms using 1 threads in the decryption.

SECTION VII. Conclusion

EPPP4SMS has three important results. First, it simultaneously provides the best features of many protocols. Second, it provides verification, i.e., the supplier can verify the measurements and the customers can prove whether their invoices are correct or not. An adversary cannot decrypt or falsify an encrypted measurement. Moreover, this is the only one that provides verification of the measurements without digital signature. Third, it is scalable—the processing time of the encryption does not depend on the number of meters—and faster than other protocols. Moreover, the difference of performance increases significantly with the level of security. Decryption is slightly slow in the simulation. However, the decryption might be as fast as other protocols, depended on the number of meters, i.e., for huge numbers.

To provide privacy, EPPP4SMS requires only a permanent key per meter, sends only a message per measurement and an extra message per verification, when the supplier requires proves. Meters might send the messages directly to their supplier or an outsourced service provider.

Similar approaches can also be used in many applications of additive homomorphic encryption—for instance: mobile sensing, sensor networks, and e-cash.

ACKNOWLEDGMENT

The authors would like to thank the Irish Social Science Data Archive and “The Commission for Energy Regulation, Electricity Customer Behaviour Trial” for the source of the dataset smart meter electricity trial data, issued by The Research Perspective Ltd., on 12-03-2012. They also thank the editor and anonymous reviewers for their helpful comments, and R. and L. Hamtil for proofreading.