Perturbation-Based Schemes with Ultra-Lightweight Computation to Protect User Privacy in Smart Grid

Abstract

In smart grid, smart meters are deployed to collect power consumption data periodically, and the data are analyzed to improve the efficiency of power transmission and distribution. The collected consumption data may leak the usage patterns of domestic appliances, so that it may damage the behavior privacy of customers. Most related work to protect data privacy in smart grid relies on cryptographic primitives, for example, encryption, which induces a large amount of power consumption overhead. In this paper, we make the first attempt to propose solutions without any cryptographic computation to protect user privacy. The privacy in smart grid is formally defined in the paper. Three schemes are proposed: random perturbation scheme (RPS), random walk scheme (RWS), and distance-bounded random walk with perturbation scheme (DBS). Three algorithms are also proposed in each scheme, respectively. All schemes are ultra-lightweight in terms of computation without relying any cryptographic primitive. The privacy, soundness, and accuracy of proposed schemes are guaranteed and justified by strict analysis.

1. Introduction

Smart grid is a typical application of Internet of Things, M2M, or IP-based sensor networks. It has been envisioned as a key method to reduce the emission of carbon dioxide and retard climate changes, by improving the efficiency of power distribution and transmission.

Smart grid relies on smart meters to collect power consumption data at user ends instantly. Smart meters report the power consumption data periodically to smart grid control center (SGCC). SGCC thus can allocate necessary power distribution and schedule required power transmission. In addition, the SGCC can relocate the power requirements at user ends by delivering power price to users. Users thus can schedule the usage of their household appliances according to the forthcoming price.

As smart meters report the power consumption data periodically, the data may leak user privacy in daily life. For example, the data may be used for deducing user behavior patterns, such as when she gets up according to the data of using microwave oven or toaster in the morning, when she goes back home according to the data of using electric stove for cooking at afternoon, or when she takes bath or goes to bed at night according to the data of using water heater or lamps. Such privacy concerns have already been acknowledged and reported by NIST [1] and significantly affect the deployment of smart meters.

Although there exist several privacy protection or security improvement for smart grid currently [2–6], most of them rely on cryptographic primitives, for example, encrypting the uploading data at smart meters. Cryptographic operations are usually not lightweight, so that they will induce extra power consumption at smart meters. In addition, the data uploading may occur frequently and periodically, so the computation for data encryption occurs extensively. For example, data are uploaded to SGCC once in 10 minutes. The encryption for the data has to be 144 times a day. Thus, the energy consumption for encryption computation would be large for a month even at single smart meter. Moreover, the extra power consumption will be accumulated to an unsatisfactory waste, because the number of smart meters in smart grid is huge. Furthermore, the decryption computation at SGCC has to be conducted if the uploading data are encrypted at smart meters. The energy consumption of decryption at SGCC will thus extremely increase. Last but not least, the smart meters usually have resource and power constraints, like traditional sensors. As the privacy protection must be conducted at smart meters, any computation for privacy protection should cost low energy to tackle these constraints. The frequent encryption operations are undesirable. Even though the encryption is lightweight in certain situations, the key management for encryption is also a difficult issue for deployment. Therefore, privacy protection by encryption unfortunately contradicts the intention of smart grid for saving energy; an ultra-lightweight method without any cryptographic computation for privacy protection is mandatory for a long run and a large scale.

In this paper, we propose perturbation-based schemes with ultra-lightweight computation without any cryptographic computation. Besides, we strictly and formally define and proof its privacy protection strength. We adapt a rigorous method to state, present, and analyze the privacy protection achievements. All our presentations strictly follow the formal expressions for better clarity and generality.

The contributions of the paper are listed as follows: (i) we propose ultra-lightweight privacy-protection schemes in terms of computation (and thus energy consumption) without any cryptographic computation; (ii) we strictly define the requirements on privacy, soundness, and accuracy in smart grid and proof the guarantee of those requirements.

The rest of the paper is organized as follows. In Section 2 we discuss the basic assumption and models used throughout the paper. Section 3 provides the detailed description of our proposed models and analysis. Section 4 gives an overview on relevant prior work. Finally, Section 5 concludes the paper.

2. Problem Formulation

2.1. Network Model

Two major entities exist in smart grid: smart meter (denoted by SM hereafter) and SGCC.

SM computes power consumption data and uploads them to SGCC periodically. The period for computing power consumption data at SM is called sensing period. The period for uploading power consumption data to SGCC is called uploading period. Without loss of generality, suppose the sensing period and uploading period are both t minutes. The sensing times and uploading times in a day will thus be $n=[\mathrm{24}*\mathrm{60}/t]$ . The total sensing data for a day are denoted as a set $DAT{A}_s=\{d{s}_{\mathrm{1}},\dots ,d{s}_n\}$ . The total uploading data for a day are denoted as a set $DAT{A}_u=\{d{u}_{\mathrm{1}},\dots ,d{u}_n\}$ . If SM does not hide $DAT{A}_s$ , $DAT{A}_s$ will be the same as $DAT{A}_u$ .

In smart grid, utility price may vary in different time slots. The price information is delivered by SGCC in advance. Users use such information to guide the power consumption. SM receives such information to calculate utility charge in a month for users. Suppose the prices for n uploading periods in a day are denoted as a set $PRICE=\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_n\}$ . Thus, the total utility charge for a day is ${\sum }_{i=\mathrm{1}}^n‍d{u}_i*p_i$ . The total utility charge for a month is the summation of charges for all days in this month. If the sensing data are changed into the uploading data for protecting privacy, the total utility charge for a day should be remained correct.

2.2. Attack Model and Trust Model

Only adversaries who attack user privacy are considered in this paper. Adversaries can eavesdrop the channels between SM and SGCC; those are denoted as ${𝒜}_c$ . Adversaries at SGCC can access all uploading data by SM; those are denoted as ${𝒜}_s$ . Both adversaries desire to deduce the user behaviors in a day by analyzing the uploading data from SM, namely, $DAT{A}_u$ . As ${𝒜}_c$ and ${𝒜}_s$ have the same view on $DAT{A}_u$ , we further do not distinguish those two adversaries. Both are denoted by the same notation 𝒜.

SGCC is untrustworthy, as we assume adversaries at SGCC are interested in user privacy. SM should be trustworthy. It is a prerequisite for any further discussion, sensing data are at SM, and all possible solutions are conducted at SM. Besides, if SM is untrustworthy, users will not choose them. SM can be easily evaluated and authorized by a Trusted Third Party (TTP).

2.3. Security Definition and Design Goal

Informally speaking, the privacy is guaranteed if the adversaries (not only at SGCC but also at channels between SGCC and SM) cannot deduce the user activities in a day. More specifically, we formally state the privacy requirement definition as follows.

Definition 1.

User activities. They are the activities that damage user privacy and are related to using one or multiple household appliances in a daily life. They are denoted as a set $ACT=\{a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_m\}$ , where $a_i\hspace{0.17em}(i=\mathrm{1},\dots ,m)$ is an activity related to one or multiple appliances.

Definition 2.

Deduce. It means an activity in $ACT$ can be inferred by data in $DAT{A}_b$ . If an activity $a_j\in ACT$ is inferred by data $d_i\in DAT{A}_b$ , it is denoted as a relation $(d_i,a_j)\in R=DAT{A}_b\times ACT$ , where R is a deduction relationship set and defined previously and empirically; $DAT{A}_b$ is the set of “bad” data that can infer to at least one in $ACT$ .

Definition 3.

Perfect full privacy (denoted as $\text{Privac}{\text{y}}_{\text{full}}^p$ ). Simply speaking, any adversary 𝒜 cannot deduce from anyone in $DAT{A}_u$ to one in $ACT$ after viewing $DAT{A}_u$ . More specifically, given anyone $d{u}_i\in DAT{A}_u$ , it is impossible for any adversary 𝒜 to find $a_j\in ACT$ , such that $(d{u}_i,a_j)\in R$ . That is,

$$\begin{array}{l}\text{Pr}\left\{\forall d{u}_i\in DAT{A}_u,a_j⟸ACT,\text{s}.\text{t}.\left(d{u}_i,a_j\right)\in R:DAT{A}_u\right\}\\ \hspace{1em}\hspace{1em}=\mathrm{0},\end{array}$$

(1)

where $\text{Pr}\{A:B\}$ denotes after viewing “B”; the probability of event “A” happens; “⇐” means “is selected from”; “,” means two operations happen consequently; “ $\text{s}.\text{t}$ .” is a shorthand for “such that.”

Definition 4.

Computational full privacy (denoted as $\text{Privac}{\text{y}}_{\text{full}}^c$ ). Given anyone $d{u}_i\in DAT{A}_u$ , it is computationally infeasible for any Probabilistic Polynomial Turing Machine (PPTM) adversary 𝒜 to find $a_j\in ACT$ , such that $(d{u}_i,a_j)\in R$ . That is,

$$\begin{array}{l}\text{Pr}\left\{\forall d{u}_i\in DAT{A}_u,a_j⟸ACT,\text{s}.\text{t}.\left(d{u}_i,a_j\right)\in R:DAT{A}_u\right\}\\ \hspace{1em}\hspace{1em}<\text{negl}(z),\end{array}$$

(2)

where $\text{negl}(z)$ is a negligible function with security parameter z.

Claim 1.

Perfect (computational) full privacy can protect user privacy on all user activities in a day, as no activity can be deduced from data in $DAT{A}_u$ by any (PPTM) adversary.

In previous claim the content in “()” is corresponded with each other. Similarly, the perfect (computational) partial privacy can be defined in the following.

Definition 5.

Perfect (computational) partial privacy, denoted as $\text{Privac}{\text{y}}_{\text{partial}}^{p(c)}$ . Given at least one $d{u}_i\in DAT{A}_u$ , it is computationally infeasible for any (PPTM) adversary 𝒜 to find $a_j\in ACT$ ; such that $(d{u}_i,a_j)\in R$ after viewing $DAT{A}_u$ . Besides, given at least one $a_j\in ACT$ , it is computationally infeasible for any (PPTM) adversary 𝒜 to find $d{u}_i\in DAT{A}_u$ , such that $(d{u}_i,a_j)\in R$ after viewing $DAT{A}_u$ . That is,

$$\begin{array}{l}\text{Pr}\left\{\exists d{u}_i\in DAT{A}_u,a_j⟸ACT,\text{s}.\text{t}.\left(d{u}_i,a_j\right)\in R:DAT{A}_u\right\}\\ \hspace{1em}\hspace{1em}=\mathrm{0}\left(<\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(z\right)\right),\\ \text{Pr}\left\{\exists a_j\in ACT,d{u}_i⟸DAT{A}_u,\text{s}.\text{t}.\left(d{u}_i,a_j\right)\in R:DAT{A}_u\right\}\\ \hspace{1em}\hspace{1em}=\mathrm{0}\left(<\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}\left(z\right)\right).\end{array}$$

(3)

Claim 2.

Perfect (computational) partial privacy can protect certain privacy-sensitive activities, as these activities cannot be deduced by $DAT{A}_u$ by any (PPTM) adversary.

Claim 3.

Full privacy has stronger strength than partial privacy in terms of the number of deducible data in $DAT{A}_u$ . Perfect privacy has stronger strength than computational privacy due to the adversary's ability. That is,

$$\begin{array}{cc}& \mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{a}\mathsf{c}{\mathsf{y}}_{\text{partical}}^c<\mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{a}\mathsf{c}{\mathsf{y}}_{\text{partical}}^p<\mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{a}\mathsf{c}{\mathsf{y}}_{\text{full}}^c<\mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{a}\mathsf{c}{\mathsf{y}}_{\text{full}}^p,\end{array}$$

(4)

where “ $A<B$ ” means that the privacy protection strength of “A” is weaker than that of “B”.

Roughly speaking, full privacy protects all activities; partial privacy protects partial activities. Perfect privacy defends against any adversary; computational privacy defends against any PPTM adversary. As perfect full privacy has the strongest privacy strength, we thus concentrate on the perfect full privacy protection in the following.

Definition 6.

Full privacy attacking experiment on the scheme Π defending against any adversary 𝒜- $\text{ExpPrivac}{\text{y}}_{\text{full}}^{p,𝒜,\Pi }$ is defined as follows:

• (1)

the scheme Π is executed in the presence of any adversary 𝒜;

(2)

𝒜 fully accesses $DAT{A}_u$ , $ACT$ , and R. Given any $d{u}_i\in DAT{A}_u$ , if 𝒜 can find $a_j\in ACT$ , such that $(d{u}_i,a_j)\in R$ , 𝒜 outputs 1, otherwise, outputs 0;

(3)

if and only if 𝒜 outputs 1, the experiment outputs 1.

Definition 7.

The scheme Π that can guarantee the perfect full privacy in presence of any adversary 𝒜 (denoted as $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,\Pi }=\mathrm{1}$ ) is defined as follows.

For any adversary 𝒜 that the scheme Π defends against, the probability that the output of the full privacy attacking experiment equals one is 0. That is, if and only if

$$\begin{array}{cc}& \text{Pr}\left[\mathsf{E}\mathsf{x}\mathsf{p}\mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{a}\mathsf{c}{\mathsf{y}}_{\text{full}}^{p,𝒜,\Pi }=\mathrm{1}\right]=\mathrm{0},\end{array}$$

(5)

  $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,\Pi }=\mathrm{1}$ .

Therefore, the design goal is to propose a scheme Π satisfying $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,\Pi }$ and importantly, with ultra-lightweight computation without any cryptographic computation.

3. Proposed Schemes

3.1. Problem Reduction

To protect the privacy of sensing data $DAT{A}_s$ , a naive method is encrypting them at SM and then uploading them to SGCC. As SGCC is untrustworthy, SGCC cannot decrypt them and has to consult a TTP. The TTP decrypts the data, and the result cannot be sent to SGCC. The TTP should compute accumulative values (or metadata) and send them to SGCC for further scheduling and charging. It obviously arises multiple overheads: a large volume of computation overhead at SM; extra communication overhead at SM and SGCC; extra entity TTP; key management overhead between SM and TTP.

As SM is trustworthy, SM is proposed to equip a trusted mixing layer between sensing layer and communication layer. That is, SM is modeled as three tuples: $〈L_s,L_m,L_c〉$ , where $L_s$ is a sensing layer computing the power consumption periodically. The output of layer $L_s$ is $DAT{A}_s$ ; $L_m$ is a mixing layer that transfers $DAT{A}_s$ into $DAT{A}_u$ ; $L_c$ is a communication layer that uploads $DAT{A}_u$ to SGCC. That is,

$$\begin{array}{cc}& \text{SM}::=〈L_s,L_m,L_c〉,\\ L_s\Rightarrow L_m:DAT{A}_s,\\ L_m::=\mathrm{\hspace{0.17em}\hspace{0.17em}}F:\mathrm{\hspace{0.17em}\hspace{0.17em}}DAT{A}_s\to DAT{A}_u,\\ L_m\Rightarrow L_u:DAT{A}_u,\end{array}$$

(6)

where “ $::=$ ” means “is defined as”; “⇒” means “data transferring between layers”; F is a data transforming function; “→” that means the input of the function F is transformed into the output of the function F. Therefore, it becomes the concentration to search an ultra-lightweight transformation function F with $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,F}=\mathrm{1}$ in the rest of the paper.

Definition 8.

“Bad” data set ( $DAT{A}_b)$ . It consists of all power consumption data that can deduce to one or multiple activities in $ACT$ . $DAT{A}_b=\{d{b}_{\mathrm{1}},d{b}_{\mathrm{2}},\dots ,d{b}_o\}$ , where o is the total number of $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ .

The characteristics of $DAT{A}_b$ , $ACT$ , and deduction relationship set R are as the following.

• (1)

Without loss of generality, $DAT{A}_b$ is a sorted set of positive numbers. That is, $d{b}_{\mathrm{1}}<d{b}_{\mathrm{2}}<\cdots <d{b}_o$ . $d{b}_{\mathrm{1}}$ is equal to or greater than the power consumption of the minimum power consumption appliance in a period. $d{b}_o$ is equal to or less than the power consumption of all appliances in a period.

(2)

Any $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ may represent the usage of one appliance in a period. For example, $d{b}_{\mathrm{1}}$ (30 wh) is the power consumption of a lamp for a period. $d{b}_{\mathrm{1}}$ is related to an event (e.g., $a_{\mathrm{1}}$ ) that means the lamp is on in the period.

(3)

Any $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ may also represent the usage of multiple household appliances. For example, $d{b}_{\mathrm{9}}$ represents two household appliances used simultaneously. $d{b}_{\mathrm{9}}=d{b}_{\mathrm{1}}+d{b}_{\mathrm{2}}$ , where $d{b}_{\mathrm{1}}$ is the power consumption of the lamp in a period; $d{b}_{\mathrm{2}}$ is the power consumption of the washing machine in the period. Thus, $d{b}_{\mathrm{9}}$ means using lamp and washing machine simultaneously in the period.

(4)

Similarly, any $a_j\in ACT\hspace{0.17em}\hspace{0.17em}(j=\mathrm{1},\dots ,m)$ may represent the usage of one appliance or multiple household appliances simultaneously.

(5)

Any $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ is related to at least one $a_j\in ACT,\hspace{0.17em}(j=\mathrm{1},\dots ,m)$ ; any $a_j\in ACT\mathrm{\hspace{0.17em}\hspace{0.17em}}(j=\mathrm{1},\dots ,m)$ is related to at least one in $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ .

(6)

Different $d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ cannot be related to the same $a_j\in ACT,\hspace{0.17em}(j=\mathrm{1},\dots ,m)$ , as any $a_j\in ACT\mathrm{\hspace{0.17em}\hspace{0.17em}}(j=\mathrm{1},\dots ,m)$ has single power consumption in a period.

(7)

$d{b}_i\in DAT{A}_b\mathrm{\hspace{0.17em}\hspace{0.17em}}(i=\mathrm{1},\dots ,o)$ may be related to multiple $a_j$ , because such $d{b}_i$ may be the power consumption for multiple appliances, and those appliances may have the same power consumption in total. For example, $d{b}_{\mathrm{9}}=d{b}_{\mathrm{1}}+d{b}_{\mathrm{2}}=d{b}_{\mathrm{3}}+d{b}_{\mathrm{4}}$ . $d{b}_{\mathrm{9}}$ is related to $a_{\mathrm{5}},a_{\mathrm{6}}\in ACT$ , where $a_{\mathrm{5}}$ means using lamp and washing machine simultaneously and $a_{\mathrm{6}}$ means the usage of the other two appliances.

In summary, the deduction relationship set $R=DAT{A}_b\times ACT$ can be further refined from a general relationship set to a relationship set with following properties:

$$\begin{array}{l}\text{Pr}\left\{\forall d{b}_i\in DAT{A}_b,\exists a_j\in ACT,\text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(d{b}_i,a_j\right)\in R\right\}=\mathrm{1},\\ \text{Pr}\left\{\forall a_j\in ACT,\exists d{b}_i\in DAT{A}_b,\text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(d{b}_i,a_j\right)\in R\right\}=\mathrm{1},\\ \hspace{1em}\hspace{1em}\hspace{1em}\text{Pr}\{\exists d{b}_i\in DAT{A}_b,a_{j\mathrm{1}}\in ACT,a_{j\mathrm{2}}\in ACT,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(d{b}_i,a_{j\mathrm{1}}\right)\in R,\left(d{b}_i,a_{j\mathrm{2}}\right)\in R\}>\mathrm{0},\\ \hspace{1em}\hspace{1em}\hspace{1em}\text{Pr}\{\exists d_{i\mathrm{1}}\in DAT{A}_b,d_{i\mathrm{2}}\in DAT{A}_b,a_j\in ACT,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{s}.\text{t}.\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(d_{i\mathrm{1}},a_j\right)\in R,\left(d_{i\mathrm{2}},a_j\right)\in R\}=\mathrm{0}.\end{array}$$

(7)

In other words, mapping $DAT{A}_b\to ACT$ is not a function, and mapping $ACT\to DAT{A}_b$ is a surjective and not a injective function.

Definition 9.

After transformation F, the privacy of $DAT{A}_u$ is guaranteed (denoted as $\text{Privac}{\text{y}}_{DAT{A}_u}^F=\mathrm{1}$ ). $\text{Privac}{\text{y}}_{DAT{A}_u}^F=\mathrm{1}$ , if

$$\begin{array}{cc}& \forall d{s}_i\in DAT{A}_s,\hspace{1em}\hspace{1em}d{u}_i=F\left(d{s}_i\right)\notin DAT{A}_b,\end{array}$$

(8)

where $F:DAT{A}_s\to DAT{A}_u$ .

Definition 10.

After transformation F, the soundness of $DAT{A}_u$ is guaranteed ( $\text{Soundnes}{\text{s}}_{DAT{A}_u}^F=\mathrm{1}$ ). The utility summation remains unchanged. That is,

$$\begin{array}{cc}& \sum _{i=\mathrm{1}}^n‍d{s}_i*p_i=\sum _{i=\mathrm{1}}^n‍d{u}_i*p_i.\end{array}$$

(9)

Due to the concentration in the rest of the paper, the research problem is reduced to as follows: given $DAT{A}_s$ , find an ultra-lightweight transformation $F:DAT{A}_s\to DAT{A}_u$ , such that the privacy and soundness of $DAT{A}_u$ are both guaranteed. That is, given $DAT{A}_s$ , find $F:DAT{A}_s\to DAT{A}_u$ , s.t. $\text{Privac}{\text{y}}_{DAT{A}_u}^F=\mathrm{1}$ and $\text{Soundnes}{\text{s}}_{DAT{A}_u}^F=\mathrm{1}$ .

Next, we propose a family of schemes to solve the problem. We list all major notations used in the remainder of the paper in Table 1.

Table 1

Notation.

𝒜	Adversary
${DATA}_s=\left\{d{s}_{\mathrm{1}},\dots ,d{s}_n\right\}$	Sensing power consumption data set
${DATA}_u=\left\{d{u}_{\mathrm{1}},\dots ,d{u}_n\right\}$	Uploading power consumption data set
F	Transforming function from ${DATA}_s$ to ${DATA}_u$
$DAT{A}_b=\left\{d{b}_{\mathrm{1}},\dots ,d{b}_o\right\}$	“Bad” power consumption data set
$PRICE=\left\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_n\right\}$	Price set
$ACT=\left\{a_{\mathrm{1}},a_{\mathrm{2}},\dots ,a_m\right\}$	Activity set

3.2. Random Perturbation Scheme (RPS)

We firstly propose a basic scheme-random perturbation scheme (RPS) to illustrate our motivations. In RPS, any $d{s}_i\in DAT{A}_s$ is perturbed into a new value in the middle of $d{b}_j$ and $d{b}_{j-\mathrm{1}}$ or in the middle of $d{b}_j$ and $d{b}_{j+\mathrm{1}}$ . The two cases are selected randomly. A Random Perturbation Algorithm called RPA is proposed for transformation F as follows.

3.2.1. Analysis of Algorithm 1

Algorithm 1: Random Perturbation Algorithm—RPA.

Required: ${DATA}_s$ , ${DATA}_b$

Ensure: ${\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u$ ,Privacy ${}_{{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u}^{\text{RPA}}$ =1,Soundness ${}_{{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u}^{\text{RPA}}$ = 1.

  $d{s}_i\Leftarrow GetData({DATA}_s)$ //Get a data from ${DATA}_s$ .

 for $i=\mathrm{1}$ to $n-\mathrm{1}$ do

  if (( $d{s}_i==d{b}_{\mathrm{1}})$ .OR. $(d{b}_{\mathrm{1}}<d{s}_i<d{b}_{\mathrm{2}}$ )) then

    $d{u}_i\Leftarrow (d{b}_{\mathrm{1}}+d{b}_{\mathrm{2}})/\mathrm{2}$

    $\delta \Leftarrow d{s}_i-d{u}_i$

    $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

  end if

  if (( $d{s}_i==d{b}_o)$ .OR. $(d{b}_{o-\mathrm{1}}<d{s}_i<d{b}_o$ )) then

    $d{u}_i\Leftarrow (d{b}_{o-\mathrm{1}}+d{b}_o)/\mathrm{2}$

    $\delta \Leftarrow d{s}_i-d{u}_i$

    $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

  end if

  for $j=\mathrm{2}$ to $o-\mathrm{1}$ do

   if ( $d{s}_i==d{b}_j$ ) then

     $d{u}_i\Leftarrow iff(random()\mathrm{\%}\mathrm{2},(d{b}_j+d{b}_{j+\mathrm{1}})/\mathrm{2},(d{b}_j+d{b}_{j-\mathrm{1}})/\mathrm{2})$

     $\delta \Leftarrow d{s}_i-d{u}_i$

     $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

   end if

    if ( $d{b}_j<d{s}_i<d{b}_{j+\mathrm{1}})$ then

      $d{u}_i\Leftarrow (d{b}_j+d{b}_{j+\mathrm{1}})/\mathrm{2}$

      $\delta \Leftarrow d{s}_i-d{u}_i$

      $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

    end if

  end for

 end for

$d{u}_n\Leftarrow d{s}_n+BIAS/p_n$ //For soundness

Proposition 11.

After the transformation of algorithm RPA, the soundness of $DAT{A}_u$ is guaranteed. ( $\text{Soundnes}{\text{s}}_{DAT{A}_u}^{RPA}=\mathrm{1}.)$

Proof.

The biases of $d{u}_i\hspace{0.17em}(i=\mathrm{1},\dots ,n-\mathrm{1})$ comparing to $d{s}_i(\mathrm{1},\dots ,n-\mathrm{1})$ are accumulated into a total value $BIAS$ . $BIAS$ is changed into extra power consumption and added to the last one $d{u}_n$ . Thus, ${\sum }_{i=\mathrm{1}}^n‍d{s}_i*p_i={\sum }_{i=\mathrm{1}}^n‍d{u}_i*p_i$ . The total cost of power consumption in a day maintains the correct value, so $\text{Soundnes}{\text{s}}_{DAT{A}_u}^{\text{RPA}}=\mathrm{1}$ .

Proposition 12.

The scheme RPS is ultra-lightweight.

Proof.

As algorithm RPA is ultra-lightweight, the number of loops is $(n-\mathrm{1})*(o-\mathrm{2})$ . The computation in each loop is only simple operations such as modulo, minus, plus, division, and multiplication. The computation complexity of algorithm RPA is $O(n*o)$ .

Proposition 13.

The scheme RPS can guarantee the perfect full privacy. ( $\text{Privac}{\text{y}}_{full}^{p,𝒜,RPS}=\mathrm{1}$ .)

Proof.

It is clear that $\text{for all}\mathrm{\hspace{0.17em}\hspace{0.17em}}d{s}_i\in DAT{A}_s,d{u}_i=F(d{s}_i)\notin DAT{A}_b$ . Thus, $\text{Privac}{\text{y}}_{DAT{A}_u}^{\text{RPA}}=\mathrm{1}$ . According to the definition of the perfect full privacy, $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,\text{RPS}}=\mathrm{1}$ .

3.3. Random Walk Scheme (RWS)

If the gap between $d{b}_j$ and $d{b}_{j+\mathrm{1}}$ ( $j=\mathrm{1},\dots ,o-\mathrm{1}$ ) is small, the perturbation (namely, δ) in RPS will be small. It can be proofed as a claim in the following.

Claim 4.

If the gap between $d{b}_j$ and $d{b}_{j+\mathrm{1}}$ ( $j=\mathrm{1},\dots ,o-\mathrm{1}$ ) is small, the perturbation in RPS will be small.

Proof.

Suppose $\max (|d{b}_j-d{b}_{j+\mathrm{1}}|)=g(j=\mathrm{1},\dots ,n-\mathrm{1})$ . If $d{s}_i=d{b}_j\in DAT{A}_b$ ) in RPA, $\max (\delta )\le g/\mathrm{2}$ . If $d{s}_i\ne d{b}_j\in DAT{A}_b$ , $\max (\delta )<g/\mathrm{2}$ . Thus, the perturbation δ is small if g is small.

If the perturbation is small, adversaries may guess the $d{s}_i$ correctly, and adversaries can guess the activity is either of two activities. To address this issue, we propose a random walk scheme called RWS in which $d{s}_i\in DAT{A}_s$ randomly jumps to a value in $DAT{A}_b$ . In this case, the privacy definition is extended to include unlinkability, in which the possibility of $d{b}_j\in DAT{A}_b$ for $d{s}_i$ is equal. Thus, the revealed user activity occurs with equal possibility.

Definition 14.

After transformation F, the privacy of $DAT{A}_u$ is guaranteed (denoted as $\text{Privac}{\text{y}}_{DAT{A}_u}^F=\mathrm{1}$ ), if

$$\begin{array}{l}\forall d{s}_i\in DAT{A}_s,\hspace{1em}d{u}_i=F\left(d{s}_i\right)\in DAT{A}_u,\\ \forall d{b}_p,\hspace{1em}d{b}_q\in DAT{A}_b,\hspace{1em}d{b}_p\ne d{b}_q,\\ \hspace{1em}\hspace{1em}\text{Pr}\left\{d{u}_i=d{b}_p\right\}=\text{Pr}\left\{d{u}_i=d{b}_q\right\}.\end{array}$$

(10)

The definition for privacy is thus extended to include the definition here and Definition 9.

In RWS, any $d{s}_i\in DAT{A}_s\hspace{0.17em}(i=\mathrm{1},\dots ,n-\mathrm{1})$ is perturbed to a value $d{b}_j\in DAT{A}_b$ ( $j=\mathrm{1},\dots ,o$ ), which is randomly selected. This algorithm is thus, especially, ultra-lightweight in terms of computation. A random walk algorithm (RWA) is proposed for the transformation function F as follows.

3.3.1. Analysis of Algorithm 2

Algorithm 2: Random Walk Algorithm (RWA).

Required: ${DATA}_s$ , ${DATA}_b$

Ensure: ${\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u$ ,Privacy ${}_{{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u}^{\text{RWA}}$ = 1,Soundness ${}_{{DATA}_u}^{\text{RWA}}$ = 1.

  $d{s}_i\Leftarrow GetData({DATA}_s)$

 for $i=\mathrm{1}$ to $n-\mathrm{1}$ do

   $j\Leftarrow (random()\mathrm{\%}o+\mathrm{1})$

   $d{u}_i\Leftarrow d{b}_j$

   $\delta \Leftarrow d{s}_i-d{u}_i$

   $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

 end for

  $d{u}_n\Leftarrow d{s}_n+BIAS/p_n$

Proposition 15.

After the transformation of algorithm RWA, the soundness of $DAT{A}_u$ is guaranteed. ( $\text{Soundnes}{\text{s}}_{DAT{A}_u}^{RWA}=\mathrm{1}$ .)

Proof.

The proof is similar to the proof of Proposition 11. As ${\sum }_{i=\mathrm{1}}^n‍d{s}_i*p_i={\sum }_{i=\mathrm{1}}^n‍d{u}_i*p_i$ , the total cost of power consumption in a day maintains the correct value. Thus, the soundness of RWA is guaranteed.

Proposition 16.

The scheme RWS is ultra-lightweight.

Proof.

The number of loops is $n-\mathrm{1}$ , so algorithm RPA is ultra-lightweight. The computations in loops are only simple operations such as modulo, minus, plus, and multiplication. Moreover, algorithm RWA is more lightweight than algorithm RPA. Thus, scheme RWS is ultra-lightweight.

Proposition 17.

The scheme RWS can guarantee the perfect full privacy. ( $\text{Privac}{\text{y}}_{full}^{p,𝒜,RWS}=\mathrm{1}$ .)

Proof.

According to the algorithm, for for all $d{s}_i\in DAT{A}_s$ , if $d{u}_i=F(d{s}_i)\in DAT{A}_u$ , we have $\forall d{b}_p,d{b}_q\in DAT{A}_b,\mathrm{\hspace{0.17em}\hspace{0.17em}}d{b}_p\ne d{b}_q$ , and $\text{Pr}\{d{u}_i=d{b}_p\}=\text{Pr}\{d{u}_i=d{b}_q\}$ . Thus, $\text{Privac}{\text{y}}_{DAT{A}_u}^{\text{RWA}}=\mathrm{1}$ . According to the definition of the privacy in Definition 14, $\text{Privac}{\text{y}}_{\text{full}}^{p,𝒜,\text{RWS}}=\mathrm{1}$ .

3.4. Distance-Bounded Random Walk with Perturbation Scheme (DBS)

In smart grid, the uploading data will be used as a feedback for future scheduling of distribution and transmission. It thus requires the uploading data can accurately present the power consumption (namely, sensing data). However, thanks to the power distribution and transmission serve not for a single SM, but a large number of SMs (e.g., a campus, a community, or a county scale), only the accuracy for a scale of SMs is sufficient for scheduling.

In RPS and RWS, although the bias exists (that is, uploading data is not equal to sensing data) at single SM, the uploading data for a large number of SMs can still represent power consumption in a scale. More specifically, the deviation between the summation of uploading data and the summation of sensing data is randomly positive or negative in one SM, thus the overall summation remains almost unchanged in expectation in a large scale. It is explained as follows.

Definition 18.

After the transformation F, the accuracy of $DAT{A}_u$ is guaranteed in expectation for a scheduling area (denoted as $\text{Accurac}{\text{y}}_{DAT{A}_u}^F=\mathrm{1}$ ). The summation of $DAT{A}_u$ equals the summation of $DAT{A}_s$ , in scheduling area and scheduling period. More specifically, suppose that each scheduling period consists of x sensing (uploading) period and each scheduling area consists of y SMs. The uploading data for them is $\text{SU}{\text{M}}_u={\sum }_{t=\mathrm{1}}^y‍\text{S}{\text{M}}_t,\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{S}{\text{M}}_t={\sum }_{i=\mathrm{1}}^x‍d{u}_i$ . The sensing data for them is $\text{SU}{\text{M}}_s={\sum }_{t=\mathrm{1}}^y‍\text{S}{\text{M}}_t,\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{S}{\text{M}}_t={\sum }_{i=\mathrm{1}}^x‍d{s}_i$ . The accuracy of $DAT{A}_u$ is guaranteed, if and only if $\text{SU}{\text{M}}_s=\text{SU}{\text{M}}_u$ .

Proposition 19.

After the transformation $RPA$ or $RWA$ , the accuracy of $DAT{A}_u$ is guaranteed in expectation for a scheduling area. ( $\text{Accurac}{\text{y}}_{DAT{A}_u}^{RPA\parallel RWA}=\mathrm{1}$ .)

Proof.

In each sensing (uploading) period, $d{s}_i$ is changed into $d{u}_i$ at single SM. $\delta =d{s}_i-d{u}_i$ . Suppose that each scheduling period consists of x sensing (uploading) period and each scheduling area consists of y SMs. The uploading data for them is $\text{SU}{\text{M}}_u={\sum }_{t=\mathrm{1}}^y‍\text{S}{\text{M}}_t,\text{S}{\text{M}}_t={\sum }_{i=\mathrm{1}}^x‍d{u}_i$ ; the sensing data for them is $\text{SU}{\text{M}}_s={\sum }_{t=\mathrm{1}}^y‍\text{S}{\text{M}}_t,\text{S}{\text{M}}_t={\sum }_{i=\mathrm{1}}^x‍d{s}_i$ . The expectation of both is equal, as the expectation of δ is 0 in a scheduling area. That is, $\overline{\text{SU}{\text{M}}_s}=\overline{\text{SU}{\text{M}}_u}$ , as $\bar{\delta }=\mathrm{0}$ , where $\bar{H}$ means the expectation of H.

To further guarantee the scheduling accuracy, we propose a distance-bounded scheme, in which the perturbation value (i.e., δ) is bounded. The accuracy is thus guaranteed within a threshold value. It takes the advantages of former two algorithms RPA and RWA. A distance-bounded algorithm (DBA) for the transformation F is proposed as follows.

3.4.1. Analysis of Algorithm 3

Algorithm 3: Distance-Bounded Algorithm (DBA).

Required: ${DATA}_s,{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_b$ , BOUND

Ensure: ${\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u$ ,Privacy ${}_{{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u}^{\text{DBA}}$ = 1,Soundness ${}_{{\mathrm{D}\mathrm{A}\mathrm{T}\mathrm{A}}_u}^{\text{DBA}}$ = 1

  $d{s}_i\Leftarrow GetData({DATA}_s)$

 for $i=\mathrm{1}$ to $n-\mathrm{1}$ do

  WHILE (1)

  {

   $j\Leftarrow (random()\mathrm{\%}(o-\mathrm{2})+\mathrm{2})$

   $\delta \Leftarrow iff(random()\mathrm{\%}\mathrm{2},(d{s}_i-(d{b}_j+(d{b}_{j+\mathrm{1}}-d{b}_j)/\mathrm{2})),(d{s}_i-(d{b}_j+(d{b}_j-d{b}_{j-\mathrm{1}})/\mathrm{2})))$

  if ( $abs(\delta )\le BOUND$ ) then

    $d{u}_i\Leftarrow d{s}_i-\delta$

    $BIAS\Leftarrow BIAS+\delta \mathrm{*}{p}_i$

   EXIT;

  else

   CONTINUE;

  end if

  }

 end for

  $d{u}_n\Leftarrow d{s}_n+BIAS/p_n$

Proposition 20.

After the transformation of algorithm DBA, the soundness of $DAT{A}_u$ is guaranteed. ( $\text{Soundnes}{\text{s}}_{DAT{A}_u}^{DBA}=\mathrm{1}$ .)

Proof.

The proof is similar to the proof of Propositions 11 and 15.

Proposition 21.

The scheme DBS is ultra-lightweight.

Proof.

The proof can be reduced to the proof of Propositions 12 and 16.

Proposition 22.

The scheme DBS can guarantee the perfect full privacy. ( $\text{Privac}{\text{y}}_{full}^{p,𝒜,DBS}=\mathrm{1}$ .)

Proof.

The proof is similar to the proof of Propositions 13 and 17.

Proposition 23.

After the transformation $DBA$ , the accuracy of $DAT{A}_u$ is guaranteed in expectation for a scheduling area. $(\text{Accurac}{\text{y}}_{DAT{A}_u}^{DBA}=\mathrm{1}.)$

Proof.

The proof is reduced to the proof of Proposition 19.

Proposition 24.

The summation of uploading data equals the summation of the sensing data with deviation bounded by $\alpha *\beta *BOUND$ , where α is the number of SMs in a schedule area, β is the number of sensing (uploading) period in a schedule period. (That is, $|SU{M}_u-SU{M}_s|\le \alpha *\beta *BOUND$ .)

Proof.

The schedule accuracy is the deviation between the summation of uploading data and the summation of sensing data. As it is proofed in Proposition 19, it depends on the number of SMs in the schedule area and the number of sensing (uploading) period in the schedule period. The expectation value is proofed to be 0, as the expectation of δ is 0. Concerning the accuracy of one schedule period, the maximal bias between the summation of uploading data and the summation of sensing data is bounded by $\alpha *\beta *BOUND$ .

4. Related Work

The security architectures and overall security requirements in smart grid were discussed in the recent years [3, 7]. Currently, the privacy issue in smart grid starts to attract more attentions. The requirements of privacy were explored in some previous works [8–11]. They pointed out the importance and urgency of privacy issues. Efthymiou and Kalogridis proposed a privacy protection scheme via anonymization of data [12]. Their work relied on Escrow and Public Key Infrastructure (PKI); thus the flexibility and scalability may be tampered. Tomosada and Sinohara proposed to use virtual energy demand to estimate the energy load and protecting consumer privacy [13], but the estimation may take much computation overhead, and accuracy may be damaged. Lu et al. [10] proposed an efficient and privacy-preserving aggregation scheme (EPPA). Their scheme relied on homomorphic Paillier cryptosystem and induces much computation overhead. Cheung et al. [14] proposed a credential-based privacy-preserving power request scheme for smart grid, which relied on an advanced cryptographic primitive-blind signature. He et al. [15] proposed to use homomorphic encryption for smart grid communications. Comparing with all aforementioned related work, our final scheme does not rely on any cryptographic primitive but fulfils provable privacy and restrains ultra-lightweight in computation.

5. Conclusions

In this paper, we proposed three schemes to protect user privacy in smart grid without any cryptographic primitive and with ultra-lightweight computation. They are random perturbation scheme (RPS), random walk scheme (RWS), and distance-bounded random walk with perturbation scheme (DBS). We also proposed three algorithms for three schemes, respectively. Our schemes do not rely on any cryptographic computations, are sound in terms of maintaining the correct utility charge, can guarantee the privacy that were strictly proofed, and can ensure the scheduling accuracy in power transmission and distribution. All proposed schemes and algorithms were extensively analyzed, which justified their applicability.