zhang MASS 2018

LPDA-EC: A Lightweight Privacy-Preserving Data Aggregation Scheme for Edge Computing Jiale Zhang† , Yanchao Zhao†‡ , Jie...

0 downloads 182 Views 738KB Size
LPDA-EC: A Lightweight Privacy-Preserving Data Aggregation Scheme for Edge Computing Jiale Zhang† , Yanchao Zhao†‡ , Jie Wu§ and Bing Chen†‡ † College

of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China Innovation Center of Novel Software Technology and Industrialization, Nanjing, China § Center for Networked Computing, Temple University, Philadelphia, USA Email:{jlzhang, yczhao, cb china}@nuaa.edu.cn; [email protected]

‡ Collaborative

Abstract—Edge computing has emerged as the key enabling technology that empowers the IoT with intelligence and efficiency. In this data enriched infrastructure, privacy-preserving data aggregation (PPDA) is one of the most critical services. However, the security and privacy-preserving requirements and online computational cost still present practical concerns in edge computing for resource-constraint edge terminals. To cope with this challenge, we present a lightweight privacy-preserving data aggregation scheme named LPDA-EC for edge computing system by employing the online/offline signature technique, Paillier homomorphic cryptosystem, and double trapdoor Chameleon hash function in this paper. The proposed LPDA-EC scheme can achieve data confidentiality and privacy-preserving, ensuring that the edge server and control center are agnostic of the user’s private information during the whole aggregation process. Through detailed analysis, we demonstrate that our scheme is existentially unforgeable under chosen message attack (EUCMA) and ensures data integrity with formal proofs under qStrong Diffie-Hellman (q-SDH) assumptions. Numerical results indicate that the LPDA-EC scheme has less computational and communication overheads. Index Terms—Edge computing, Privacy-preserving, Data aggregation, Homomorphic cryptosystem, Chameleon hash function, Online/offline signature.

I. INTRODUCTION A. Background With the explosive growth of Internet of Things (IoT) devices and wide deployment of IoT infrastructure, all IoT-based typical applications, such as smart grid [1], smart healthcare [2], smart city [3], and vehicular sensing system [4], are interconnected via a network and operate on a number of IoT devices that frequently collect and transmit data to the cloud center for observing the real-time and intelligent decisions. For example, in the smart grid application system, data reports generated from distributed smart meters are transmitted to the remote control center via the Internet for further analysis, and the control center can monitor the power delivery and electricity consumption information periodically to make realtime decisions. Note that these IoT-based smart applications generate massive volumes of data and transfer the data to the remote cloud center for big data analytics. In this situation, the traditional IoT data processing architecture has come to the bottleneck and cannot handle the IoT big data transmission and processing due to the bandwidth limitation and resources constraint [5].

Edge computing [6] is a promising distributed model that allows storing and processing data at the edge of the network with the edge server, which will not only reduce the transmission overhead but also improve the real-time processing capability. Through the combination of edge computing and cloud computing, the real-time data can be collected and aggregated by the edge server and then forwarded to the cloud computing for further analysis, as shown in Fig. 1, thereby overcoming the shortcomings of traditional IoT architecture such as bandwidth limitation and resources constraint [7]. However, the security and privacy issues still present practical concerns for edge computing, since the edge server deployed at the network edge cannot be fully trusted. For example, in order to obtain services and benefits, users need to share their collected data with the edge server, and these sensed data (e.g., electricity consumption in the smart grid) may contain users’ private information, that may be eavesdropped upon untrusted edge servers [8]. Thus, the idea of privacy-preserving data aggregation (PPDA) transmission has emerged to solve the privacy leakage problem in IoT-based application scenarios, and many PPDA schemes [9–15] have been proposed. However, most of them are not suitable for the edge computing system due to the high computational costs and the frequent data transmission. Therefore, we present a lightweight data aggregation scheme for edge computing in this paper that can simultaneously achieve privacy-preserving and lightweight aggregation. B. Related Work and Motivations Due to the frequency of data transmission and the importance of personal privacy, many data aggregation schemes have been proposed recently. Li et al. [9] proposed an in-network incremental data aggregation scheme by using the Paillier additive homomorphic cryptosystem. The data can be aggregated following a network topology-based aggregation tree. Lu et al. [10] presented an efficient and privacy-preserving aggregation scheme named EPPA for smart grids, which utilized the extended Paillier cryptosystem to achieve secure data aggregation. This scheme also exploits the super-increasing sequence to structure multidimensional data into one dimensional, which can reduce the communication overhead. Later, Li et al. [11] presented EPPDR by combining homomorphic encryption and key evolution technique, which supports the adaptive private

Control Center (services) Save bandwidth, reduce communication overheadĊĊ

• Edge server at network edge

Local process (aggregation) Report

Local storage (sharing) Report

Response

Encrypted Data

Local decision (mining) Report

II. PRELIMINARIES

Response

Encrypted Data

Encrypted Data

Fig. 1. Edge computing enhanced privacy-preserving data aggregation

key evolution and forward secrecy of users’ session keys. In the same year, Fan et al. [12] proposed the first privacyenhanced aggregation scheme named PEDA against internal attackers by injecting blinding factors in the report generation phase, which can resist the formidable attackers. In 2015, Ni et al. [13] presented a security-enhanced data aggregation scheme for smart grid communications based on homomorphic encryption, homomorphic authenticators, and trapdoor hash function, which can achieve data confidentiality and integrity against malicious aggregator during the aggregation process. Later, the authors in [13] further designed an efficient data aggregation scheme [14] to resist privacy exposure without any trusted third party by using the random noisy technique. Recently, Lu et al. [15] designed an efficient data aggregation scheme for fog-enhanced IoT applications to aggregate hybrid data into one, while can early filter false data at the fog nodes. Notice that the schemes above all consider the aggregation scheme to protect data privacy and reduce communication overhead simultaneously, while the computational complexity is still an urgent problem to be solved during the frequent aggregation requests in edge computing system. Specifically, in a certain aggregation scheme, the time-consuming operations (e.g., paring and exponentiation operation) are mainly concentrated on the signature and verification processes due to the data integrity requirement. Therefore, there is a critical need to design a lightweight privacy-preserving data aggregation framework for complicated edge computing system.

In this section, we briefly review the bilinear pairing technique [16], Paillier Cryptosystem [17], online/offline signatures [18][19], and security definitions [20], which will facilitate the understanding of our LPDA-EC scheme. A. Bilinear Pairing Setting Let G and GT be two multiplicative cyclic groups of prime order p, and g be a generator of G. Consider a bilinear map e : G × G → GT satisfies the following properties [16]: •

• •

Bilinear: For all u, v ∈ G and a, b ∈ Z∗p , we have e(ua , v b ) = e(u, v)ab . Nondegenerate: g should satisfy e(g, g) 6= 1GT . Computable: e(u, v) should be computable.

Definition 1. q-Strong Diffie-Hellman Problem (q-SDH) [18]: Solving the q-SDH problem in G is to compute a pair (m, σx ) where (m, x) ∈ Z∗p , given a (q + 1)-tuple 2 q (g, g x , g (x ) , ..., g (x ) ). We say that the q-SDH problem is (q, t, )-hard to solve, for any t-time adversary A, the following probability is negligible in . 2

q

P r[A(g, g x , g (x ) , ..., g (x ) ) = (m, σx ), m ∈ Z∗p ] < .

(1)

Theorem 1. We say that the (q, t, )-SDH assumption holds in G if no t-time algorithm has advantages at least  in solving the q-SDH problem in G. B. Paillier Homomorphic Cryptosystem For concreteness and without loss of generality, our LPDAEC scheme is based on the Paillier cryptosystem. The concrete description of Paillier cryptosystem is shown as follows: •

C. Our Work In this paper, we design a Lightweight Privacy-preserving Data Aggregation scheme for Edge Computing system (LPDA-EC) which can achieve data confidentiality, privacypreserving, and lightweight aggregation simultaneously to address the above challenges. Specifically, our contributions can be summarized in the following three aspects: • Lightweight Aggregation: In our LPDA-EC scheme, the time-consuming online signature computational cost is transferred to the offline phase by employing the online/offline signature technique and double trapdoor Chameleon hash function. The users only need a small number of operations for the online computation. • Privacy-Preserving: We give the detailed analysis to show that our proposed LPDA-EC scheme can achieve

confidentiality and privacy-preserving under our defined security model. Unforgeability Signature: The online/offline signature in our LPDA-EC scheme is proved existentially unforgeable under chosen message attacks.





KeyGen: Given two large primes (p, q), the RSA modulus n = pq and the Carmichael function λ = (p − 1)(q − 1) are computed. g is a generator of Z∗n2 with an order n, meaning that g n mod n2 = 1. Define a function L(u) = −1 u−1 λ mod n2 ) . The n and further calculate µ = L(g public key is pk = (n, g) and the corresponding private key is sk = (λ, µ). ENC: Given a plaintext message m ∈ Zn and the random number r is chosen such that gcd(r, n) = 1. The ciphertext can be computed as c = g m · rn mod n2 . DEC: Given the ciphertext c ∈ Z∗n2 , the corresponding plaintext message can be recovered as m = L(cλ mod n2 )µ mod n.

The Paillier homomorphic cryptosystem can be proved to be semantically secure against chosen plaintext attack based on decisional composite residuosity problem, and the correctness and security proof can be found in [17].

C. Online/Offline Signatures An online/offline signature scheme can split a signing algorithm into two phases. The first phase is performed in the offline phase before a message to be signed is presented and the highest complexity operations are accomplished in this phase. The second phase is performed in the online phase after the massage is given. It is very lightweight and can be calculated easily by a resource-constraint end device. Besides message signature, the verification of signature can be also separated into offline and online phases by using the Double Trapdoor Chameleon Hash (DTCH) function [21]. In our edge computing system, the offline phase of signature and verification can be executed as a background computation in edge server. The DTCH function is a very useful method to construct an online/offline signature scheme, which can achieve the fully adaptively secure one-time signature property. The DTCH function used in our work can be described as follows: Let G be a group generated by prime order p1 , and let g1 ∈ G be a generator. Choose two random elements (trapdoor keys) y, z from Z∗p1 and compute g2 = g1y , g3 = g1z . The public key is pk = (g1 , g2 , g3 ) and the corresponding private key is sk = (y, z). For the given input elements of chameleon hash (r, s, u) from Zp , the output is a hash value of G, which can be defined as Hch (r, s, u) = g1r · g2s · g3u . D. Security Definitions Definition 2. Unforgebility: For an online/offline signature scheme, the existential unforgeability under chosen message attacks (EU-CMA) is defined in the following game [20]. This game is carried out between a challenger C and an adversary A. The adversary is allowed to make queries to an offline signing oracle sig of f (sk) and an online signing oracle sig on (sk, Sti , mi ) where sti means the state information of singer. We assume that the adversary A is able to make the t-th online signature query after the i-th offline signature query has been made, which is reasonable since the signer always executes his i-th offline signing before his i-th online signing. The advantage in existentially forging a signature of the adversary A is:   V eron (pk, m∗ , σ ∗ ) = 1 : (pk, sk) ← AdvA = P r . (2) of f on KeyGen(1k ); (m∗ , σ ∗ ) ← A(σ ,σ ) III. MODELS AND DESIGN GOALS In this section, we formalize the system model, security requirements, and identify our design goals. A. System Model In our system model, we formalize the communications among all entities as depicted in Fig. 2. Specifically, there are four entities that include a trusted authority, a control center, an edge server, and edge terminals in the system model of the proposed scheme. • Trusted Authority (TA): The TA is a fully trusted third party whose duty is to bootstrap the whole system and distribute the key materials. We assume that there are

Control Center (CC)

Trusted Authority (TA)

Aggregated Data

Response

Registration

Edge Server (ES) System Parameters

Encrypted Data

Encrypted

Encrypted Data

Data

Encrypted Data

Encrypted Data

Edge Terminals (ETs)

Fig. 2. Architecture of our proposed data aggregation scheme

secure channels between the TA and other entities, which support the transmission of these key materials. In general, after bootstrapping the system, the TA will not be involved in the subsequent process. • Control Center (CC): The CC’s duty is to collect all users’ data from the edge server and make some analytics according to the realistic requirements. • Edge Server (ES): ES is a core entity for edge computing system with certain computation capability, which is deployed at the edge of the network and serves as a relay and aggregator role between the CC and edge terminals. • Edge Terminal (ET): ET represent a set of devices owned by users. Each terminal ETi is equipped with sensing and communication module, which enables ETi to collect the private data mi and transfer its report Pi to the control center via ES. Since ET’s computational resources are usually constrained, the security algorithms with high computational complexity (or time-consuming) cannot be deployed. The shortcoming of ET motivates us to design a lightweight security mechanism for edge computing system. B. Security Requirements In our security model, we assume that the TA and CC are fully trusted, while ES is honest-but-curious. On the one hand, they faithfully follow the designated aggregation protocol. On the other hand, they are curious and attempt to disclose users’ sensitive information. In addition, there exists an adversary A residing in edge computing communication channels to intercept the transmission of reports from aggregator and users. The adversary A could also launch some activity attacks or intrude the internal database to threaten the data integrity and privacy. Therefore, to ensure the safe transmission of reports and preserve the privacy of users, the following security requirements should be satisfied. • Confidentiality: Confidentiality is a fundamental requirement that prevents the unauthorized parties from accessing the users’ private data even if this adversary can eavesdrop the communication channels.

TABLE I T HE D ETAILED D ESCRIPTION OF R EGISTRATION P HASE Edge Server

Edge Terminal Choose Xi ∈ Z∗p1 , IDi , T Si • Calculate X (Sigsk , V erpk ) = (Xi , Yi = g1 i ) H1 (IDi ||T Si ||ki ) ri = g1 αi = g 1

Control Center



βi = ri − Xi H2 (αi )

Y ,α ,β

i −−i−−i−−→

Registration Phase

• • •



Maintain Tiof f



T

of f

=(IDi ||T Si ||σ

of f

)

i i ←− −−−−−−−−−−−−− −−−

Choose y, z, si , ui ∈ Z∗p1 Calculate g2 = g1y , g3 = g1z u s r Hchi = g1i · g2i · g3 i X σiBLS = H0 (Hchi ) i of f σi = (σiBLS , Hchi )

Authentication and Integrity: Authentication ensures the identity of a user is authorized, which is to guarantee the encrypted report is truly generated by a legal user. Then, the integrity is to prevent the encrypted reports from being modified by the adversary A during the transmission. Any unauthorized and modified report can be detected by the CC when reading the report. • Privacy-preserving: As long as the aforementioned security requirements can be guaranteed, the private information of users including sensitive data, personal identities, and real-time location information can achieve the privacy-preserving requirement. C. Design Goals Our design goal is to propose a lightweight privacypreserving data aggregation scheme for edge computing under the aforementioned system model and security requirements. Specifically, our scheme should capture the following objectives: • Security and Privacy: As stated above, all security requirements (i.e, confidentiality, authentication, and integrity) should be guaranteed for our LPDA-EC scheme, that is, the CC and ES can detect the illegal operations from adversaries and the reliable reports can be received by the CC and ES in a trusted way. Meanwhile, the users’ privacy should be protected as well in our proposed scheme, which means that no one can read any individual user’s data and the aggregation results can only be obtained by the trusted CC. • Efficiency: The proposed aggregation scheme should be efficient. This means that the computation cost at ET should be as less as possible, since the ET are resourceconstrained devices. In addition, the communicationeffectiveness should also be achieved in our proposed scheme to support the frequent aggregation requests in a certain period and the simultaneous transmission of large amounts of reports. •

IV. PROPOSED LPDA-EC SCHEME In this section, we present our lightweight privacypreserving data aggregation scheme for edge computing system (LPDA-EC) by utilizing the online/offline signature and

(g1 ,g2 ,g3 )

−−−−−−−→

β

H (αi )

Verify αi = g1 i Yi 2 Publish (Yi , αi , βi )

• Publish (g1 , g2 , g3 ) Offline Signature Generation

verification technique, homomorphic cryptosystem, and double trapdoor hash functions, which mainly consists of five phases: system initialization, registration, report generation, report aggregation, and report reading. A. System Initialization In our edge computing system, there exists a single TA who can bootstrap the whole system. Specifically, in the system initialization phase, on input the security parameters (k, k1 ), TA first randomly chooses two distinct larger primes (p, q), and computes the RSA modulus n = pq and the Carmichael’s function λ = lcm(p − 1, q − 1), where |p| = |q| = k. Then, TA defines a function L(x) = µ−1 n where µ can be calculated −1 as µ = L(pλ mod n2 ) . TA also chooses a generator g ∈ Z∗n2 . Thus, the Paillier Cryptosystem’s public key is P KP = (n, g), and the corresponding private key is SKP = (µ, λ). Then, the TA generates two multiplicative cyclic groups G and GT of the same prime order p1 , where |p1 | = k1 , and a bilinear map e : G × G → GT . The TA further chooses a generator g1 ∈ G and three secure cryptographic hash functions ∗ ∗ H0 : {0, 1} → G, H1 : {0, 1} → Z∗p1 , H2 : G → Z∗p1 and a Chameleon hash function Hch : Z∗p1 → G. In addition, we assume that the number of ET in a certain aggregation time slot is ω. After the above parameter settings, the TA releases the system parameters as SPpub = {p1 , n, g, G, GT , e, g1 , ω, H0 , H1 , H2 , Hch } , (3) and the master keys will be assigned to the CC via a secure channel as msk = (λ, µ, p, q). (4) B. Registration When a user terminal ETi joins the edge computing system, it needs to register to the CC and then send the offline signature to ES. The whole registration and offline signature generation phase is shown in table I. • User Registration: ETi first chooses a secure signature scheme Sigsk ()/V erpk () and generates a random value Xi ∈ Z∗p1 as the signature private key. Then ETi calculates the corresponding verification public key as

TABLE II T HE D ETAILED D ESCRIPTION OF R EPORT G ENERATION P HASE

• •



If it does hold:



Maintain Pi







Edge Server Check the time stamp: T Si Verify the offline signnature σiof f with:  e(g1 , σiBLS ) = e Yi , H0 (Hchi )

Edge Terminal

accept

−−−→

Pi =IDi ||ci ||T si ||σ on

←−−−−−−−−−−−−−i−− reject

−−−→

Else:

Yi = g1Xi , where (Sigsk , V erpk ) = (Xi , Yi ). ETi also chooses a larger random integer ki ∈ Z∗p1 as the binding factor and computes ri = H1 (IDi ||T Si ||ki ), where IDi is the identifier of the ETi and T Si is the current time stamp, which can resist the potential replay attack. At last, ETi computes the knowledge of registration {αi , βi }, where αi = g1ri , βi = ri − Xi H2 (αi ) and sends {Yi , αi , βi } to CC. Authentication: After receiving the registration message {Yi , αi , βi } from ETi , CC verifies αi by checking αi = H (α ) g1βi Yi 2 i based on discrete logarithm problem. Then, it publishes {Yi , αi , βi }. Offline Signature Generation: In order to generate the offline signature, ETi first chooses two random values y, z ∈ Z∗p1 and sets g2 = g1y , g3 = g1z . Without loss of generality, our LPDA-EC scheme would select the BLS short signature [22] σBLS as the secure signature scheme to generate the offline signature. ETi also chooses two integers (si , ui ) ∈ Z∗p1 and stores St = (ri , si , ui ) as the state information, where ri = H1 (IDi ||T Si ||ki ). Then, the value of DTCH function can be calculated as Hchi = g1ri · g2si · g3ui , and ETi further makes a signature on Hchi as X i σiBLS = H0 (Hchi )

Data encryption: Choose vi ∈ Z∗n2 Calculate ci = g mi · vin mod n2 • Online signature generation: Choose si 0 ∈ Z∗p1 •



Revoke the aggregation command

If it does hold, the algorithm outputs accept; otherwise, it outputs reject. In order to make the offline verification efficiently, the ES can perform the batch offline verification and the correctness of verification will be presented later. Data Encryption: In our edge computing system, the ETi will report its sensing data at every certain time slot t, e.g., t = 10 minutes. After the offline verification has been successfully accepted, ETi collects the sensitive data mi and executes the Paillier cryptographic algorithm to generate the report as ci = g mi · vin

mod n2 ,

(8)

Z∗n2 .



where vi is a random integer in Online Signature Generation: Upon the data encryption phase has finished, ETi chooses a random number si 0 ∈ Z∗p1 and uses the state information St = (ri , si , ui ) to compute the online signature as  ui 0 = (ri − ci ) + (si − si 0 )y + ui z z −1 , (9) where σion = (si 0 , ui 0 ). At last, ETi sends its data report Pi = IDi ||ci ||T St ||σion to the ESj , where T St is the current aggregation time stamp, which can resist the replay attack.

(6)

Upon receiving the offline tag Tiof f = (IDi ||T Si ||σiof f ) from ETi , the ES first checks the time stamp T Si and the offline signature σiof f to verify its validity. Meanwhile, ETi needs to generate its sensing data at every certain time slot t, e.g., t = 10 minutes, and sends the data report to the ES. The whole offline signature verification and report generation phase includes the following steps and the detailed description is shown in Table II. • Offline Signature Verification: On input the verification public key V erpk and the offline signature σiof f =



(σiBLS , Hchi ), the offline verification algorithm is to verify whether  e(g1 , σiBLS ) = e Yi , H0 (Hchi ) . (7)

(5)

by using the signature private key Xi . At last, ETi sends the offline tag Tiof f = (IDi ||T Si ||σiof f ) to the ES, where σiof f = (σiBLS , Hchi ) and publishes the online verification key V eron = (g1 , g2 , g3 ) to the CC. C. Report Generation

Calculate σion = (si 0 .ui 0 )

D. Report Aggregation After ESj receives the total ω individual reports {P1 , · · · , Pω } from the ET in a certain time slot t, ESj needs to check the time stamp T St and the online signature σion to verify its validity, and generate the aggregation result. The detailed description of report aggregation phase is shown in Table III. •

Online Signature Verification: On input the online signature σion and the online verification key V eron , the online verification algorithm is to verify whether Hch (ri , si , ui ) = Hch (ci , si 0 , ui 0 ).

(10)

TABLE III T HE D ETAILED D ESCRIPTION OF R EPORT AGGREGATION P HASE Edge Server Check the time stamp: T St • Verify the online signnature σ on with: i Hch (ri , si , ui ) = Hch (ci , si 0 , ui 0 ) • If it does hold: Q 2 Report aggregation:c = ω i=1 ci mod n Aggregation signature generation: Choose Xj ∈ Z∗p1 X Calculate σAgg = H0 (IDj ||c||T St ) j

Control Center







Pi =IDj ||c||T St ||σAgg

−−−−−−−−−−−−−−−−→ reject

−−−→

Else:

If it does hold, the algorithm outputs accept; otherwise, it outputs reject. Report Aggregation: After the validity checking, the ES computes the aggregation results for encrypted report data as ω Y c= ci mod n2 . (11)

i=1

=g



i=1

i=1 mi

·

ω Y

vin

mod n2 = g m ·

i=1

ω Y

vin

mod n2

i=1

and then obtains the aggregated plaintext as m=

ω X i=1

mi =

L(cλ L(g λ

mod n2 ) mod n2 )

mod n.

(13)

F. Correctness The correctness of user authentication, offline signature verification, and online signature verification are presented as

Revoke the aggregation command

H2 (αi )

g1βi Yi

(ri −Xi H2 (αi ))

= g1

X H2 (αi )

· g1 i

= g1ri = αi •

Offline Batch Verification: ω Y

Aggregation Signature Generation: Then, the ESj chooses a random number Xj ∈ Z∗p1 as the aggregation signature private key, and makes an aggregation signature as Xj σAgg = H0 (IDj ||c||T St ) , (12)

where IDj is the identifier of the ESj . At last, ESj sends the aggregated report P = IDj ||c||T St ||σAgg to the CC. E. Report Reading Upon receiving P = IDj ||c||T St ||σAgg , CC performs the following steps to read the aggregated result and finally sends the response information to each ET. • Aggregation Signature Verification: CC first verifies the validity of the aggregation signature σAgg  , i.e., whether e(g1 , σAgg ) = e Yj , H0 (IDj ||c||T St ) , where Yj = X g1 j . If it does hold, the verification algorithm outputsaccept, since e(g1 , σAgg ) = e g1 , (H0 (IDj ||c||T St ))Xj =   X e g1 j , H0 (IDj ||c||T St ) = e Yj , H0 (IDj ||c||T St ) . Otherwise, it outputs reject. • Report Reading and Decryption After the aggregation signature verification, CC reads the aggregated ciphertext c as ω ω Y Y c= ci mod n2 = g mi · vin mod n2

Maintain P



follows. • User Authentication:

i=1 •



ω  Y  e Yi , H0 (Hchi ) = e g1Xi , H0 (Hchi )

i=1

=

i=1

ω Y

ω  Y e g1 , (H0 (Hchi ))Xi = e(g1 , σiBLS )

i=1

= e(g1 ,

i=1 ω Y

σiBLS )

i=1 •

Online Signature Verification: 0

0

Hch (ci , si 0 , ui 0 ) = g1ci · g2si · g3ui = = =

0



0 z (ri −ci )+(si −si 0 )y+ui z z −1 · (g1y )si · g1 0 0 · (g1y )si · g1ri · g1−ci · g1y·si · (g1y )−si · g1z·ui (g1 )ri · (g1y )si · (g1z )ui = g1ri · g2si · g3ui

g1ci g1ci

= Hch (ri , si , ui ) V. SECURITY ANALYSIS In this section, we will discuss the security properties of our LPDA-EC scheme. In particular, following the security requirements and design goals described in section III, our analysis will focus on the authentication, confidentiality, privacy-preserving, integrity, and unforgeability. A. Authentication In our LPDA-EC scheme, the extended Schnorr’s signature method is utilized to realize the secure authentication in registration phase. Since the Schnorr’s signature method is provably secure under the discrete logarithm assumption, the ET’s identity can be efficiently authenticated, where CC was assumes to be fully trusted. Specifically, we claim that an attacker cannot find a collision ri 0 to forge the knowledge of registration {αi , βi } without obtaining IDi of ETi , while the ETi ’s real identifier IDi is hidden in ri by using a secure one-way hash function H1 . Even if the attacker successfully finds out the ETi ’s real identifier IDi in the process of offline

signature transmission, he also cannot obtain the hash function value ri because the blinding factor ki has been selected and kept secretly. Without the value of ri , the success probability of an attacker getting the signature private key Xi in polynomial time is negligible, unless the discrete logarithm problem can be solved. Therefore, the secure authentication between ET and CC can be guaranteed. Meanwhile, the forgery attack can be resisted efficiently, which means the signatures and reports forged by attackers can be easily detected by CC in our LPDA-EC scheme. B. Confidentiality and Privacy-Preserving In the report generation phase, each user’s private data mi sensed by ET are encrypted as the individual ciphertext ci = g mi · vi n mod n2 by using Paillier homomorphic cryptosystem. Meanwhile, the aggregation operation uses the additive homomorphic property to aggregate the individual ciphertext ci , which can be generically formed as Pω

c = g(

i=1

mi )

·(

ω Y

vi ) n

mod n2 .

i=1



Qω Let m = i=1 mi and v = i=1 vi , then the aggregated ciphertext c = g m · v n mod n2 is still a valid ciphertext of Paillier cryptosystem. Since the Paillier cryptosystem is semantically secure against the Chosen Plaintext Attack (CPA) [17], the confidentiality of both individual private data mi and aggregated data m can be guaranteed. Specifically, even if an attacker can monitor the whole communication channel from ET to CC, which means both the individual ciphertexts ci and the aggregated result c can be eavesdropped by the attacker, he still cannot identify any related private information. On the one hand, after collecting all the reports from ET, the ES cannot decrypt the individual ciphertext without the private key (λ, µ) of Paillier cryptosystem, instead, it is only Q required to aggregate the reports directly ω 2 by computing c = i=1 ci mod n and transmitting the aggregated results to the CC. Thus, although ES is the honestbut-curious entity and the attacker may intrude the database of the ES, the ET’s privacy can be protected perfectly. On the other hand, upon receiving c from ES, the PωCC recovers it as the sum of each ET’s private data m = i=1 mi and stores the compressed plaintext result in the database. Even if the attacker steals this compressed plaintext result, he still cannot obtain the individual data mi . From the analytics above, the confidentiality and privacy of each individual ET’s report can be protected. C. Integrity and Unforgeability The proposed LPDA-EC scheme is existentially unforgeable under the chosen message attack (EU-CMA) and ensures the data integrity. According to Definition 2, there exists no probabilistic polynomial time adversary A can generate any pair (m∗ , σ ∗ ) for some m∗ ∈ Z∗p1 that ensures σ ∗ is just a valid signature on m∗ with private key sk without making any query for the online signature token on m∗ from the online signing oracle.

Theorem 2. Suppose our online/offline signature scheme is (t, q1 , q2 , ) secure against EU-CMA provided that we can construct an algorithm B, which solves the q-SDH problem in polynomial time with a non-negligible probability 0 ≥ 3 − qp2 . Proof. We prove this theorem by the contradiction method, assumed that A makes q1 offline signature queries and makes q2 online signature queries on message mi . The types of successful attacks from A can be divided into the following cases: ∗ ∗ ∗ Case 1: g m g2s g3u 6= g mi g2si g3ui for all i ∈ {1, · · · , q2 }. ∗ ∗ ∗ Case 2: g m g2s g3u = g mi g2si g3ui for some i ∈ {1, · · · , q2 }, and s∗ 6= si . ∗ ∗ ∗ Case 3: g m g2s g3u = g mi g2si g3ui for some i ∈ {1, · · · , q2 }, and s∗ = si , but u∗ 6= ui . Let G be a cyclic group of prime order p, g be a generator of G, and algorithm B is given a q-SDH instance 2 q (g, g τ , g (τ ) , · · · , g (τ ) ), its goal is to compute a new valid ∗ ∗ online/offline signature (σof f , σon ) and successfully solve the q-SDH problem. B simulates a challenger C and interaction with adversary A as follows. [CASE 1.] •







Initiation: B chooses two values y, z ∈ Z∗p and sets signature private key as SK = (a, y, z), then sends the verification public key V K = (g, g1 , g2 , g3 ), where g1 = g a , g2 = g y , g3 = g z to A. Sig of f Queries: A makes a i-th offline query, where 1 ≤ i ≤ q1 . B randomly chooses three integers (ri , si , ui ) ∈ Z∗p to compute the value of Chameleon hash function Hchi = g ri g2si g3ui = g (ri +si y+ui z) , let ci = ri +si y+u  iz and then responds with σiof f = H0 (Hchi )a , Hchi as the i-th offline signature token. σiof f is sent to A while (ri , si , ui ) are stored by B. Obviously, σiof f is a valid offline signature for V K since   e g, H0 (Hchi )a = e g1 , H0 (Hchi ) . Sig on Queries: A makes a i-th online query, where 1 ≤ 0 ∗ 0 i ≤ q2 . B randomly chooses  −1 si ∈ Zp , setsonui = 0(ri − 0 mi ) + (si − si )y + ui z z and returns σi = (si , ui 0 ) as the i-th online signature token. Obviously, σion is a valid online signature on message mi since Hchi (ri , si , ui ) = Hchi (mi , si 0 , ui 0 ). Forgery: A finally returns a valid forgery signature (m∗ , s∗ , u∗ , s∗ 0 , u∗ 0 ) satisfying the condition in Case 1. ∗ ∗ ∗ Since g m g2s g3u 6= g mi g2si g3ui , then we have c∗ = m∗ + s∗ y + u∗ z 6= ci . That means B can generate a pair ∗ (m∗ , Hch , σ ∗ ) to solve the q-SDH problem in polynomial time with probability of at least /3, since Case 1 occurs with the same probability.

Note that, the simulated online/offline signing oracles of Case 2 and Case 3 after Initiation, Sig of f Queries, and Sig on Queries phases are indistinguishable to Case 1. The only difference is that algorithm B can compute a valid online/offline signature to solve the q-SDH problem by forging ∗ in Case 1 whereas a new Chameleon hash function value Hch the trapdoor y and z are forged in Case 2 and Case 3. Thus,

we skip the repeat steps to Case 1 and focus on the Forgery phase in the subsequent security analysis. [CASE 2.] • Forgery: Note that in Case 2, the algorithm B will forge one of the double trapdoor y by setting the signature private key as SK = (x, a, z). From the analysis above, we know that Case 2 occurs with a probability of at least /3, and s∗ = si occurs with a probability of 1/p since the randomly selected si is uniformly distributed in Z∗p . Thus, for the whole game the probability of s∗ = si occurring is at most q2 /p. If A returns a valid forgery sig∗ ∗ ∗ ∗ ∗ 0 0 nature m∗ , σof f (a, r , s , u ), σon (s∗ , u∗ ) satisfying ∗ ∗ ∗ the condition in Case 2, which for some i, g m g2s g3u = B can g mi g2si g3ui and s∗ 6= si hold. Then algorithm  compute a = y = (m∗ − mi ) + (u∗ − ui )z (si − s∗ )−1 . Therefore, B can generate a new pair (m∗ , σ ∗ ) to solve the q-SDH problem in polynomial time with probability at least /3 − q2 /p. [CASE 3.] • Forgery: In Case 3, the algorithm B will forge another trapdoor z by setting SK = (x, y, a), and the probability of u∗ = ui occurring is at most q2 /p for the whole game. The proof is similar to that of Case 2, whereby B can  compute a = z = (m∗ − mi ) + (s∗ − si )z (ui − u∗ )−1 for some i with probability at least /3 − q2 /p to solve the q-SDH problem in polynomial time. Here  0 0 ∗ ∗ ∗ ∗ ∗ m∗ , σof f (a, r , s , u ), σon (s∗ , u∗ ) is a valid forgery signature by A satisfying the condition of Case 3. To sum up, we can construct an algorithm B which can solve the q-SDH problem in polynomial time with probability of at least /3 − q2 /p. This contradicts the original q-SDH assumption and thus Theorem 2 is proved. VI. N UMERICAL R ESULTS In this section, we evaluate the efficiency of our proposed scheme in terms of the computational complexity and communication overhead. We compare our LPDA-EC scheme with three existing schemes, namely, EPPA [10], PEDA [12], and SEDA [13], which are all designed from homomorphic encryption scheme. In particular, we perform several simulations to demonstrate the efficiency of our scheme. The implementation is conducted on a Linux machine with Intel Core i7-4710U CPU at 2.5GHz and 4.00 GB memory. The time cost operations are all estimated using the Pairing-Based cryptography (PBC) library. For better comparability, we choose the RSA modulus n is 1024 bits and the parameter p1 is 160 bits. Table IV lists the notations and its time cost in our evaluations. A. Computational Complexity When an edge terminal ETi joins the edge computing system, it requires two exponentiation operations in Zn2 to generate ci and three multiplication operations in G for online signature generation. After receiving the ciphertexts, the ES needs three exponentiation operations in G to verify the online signature and ω multiplication operations in Zn2 to aggregate the reports. Since the multiplication operations in Zn2 are

TABLE IV N OTATIONS IN E VALUATIONS Notations TE1 TE2 TM TP

Descriptions Exponentiation Operation in Zn2 Exponentiation Operation in G Multiplication Operation in G Pairing Operation

Time Cost (ms) 1.58 1.62 0.06 17.62

considered negligible compared to exponentiation and pairing operations, the computational cost of aggregation is negligible. In addition, the ES also needs one exponentiation operation in G to generate the aggregation signature. At last, the OC performs two pairing operations and two exponentiation operations in Zn2 to verify the validity of the aggregation signature and decrypt the aggregated ciphertext. From the analysis above, we can see that there are less time-consuming cryptographic operations in our LPDA-EC scheme, especially on the ETs’ side. Fig. 3(a) shows the comparison result of signature and verification time cost with other three schemes, and the detailed description of each operation is shown in Table V. From the figure, we can see that the time cost of signature and verification in our scheme is reduced at least 50% compared with EPPA [10], PEDA [12] and SEDA [13], since the time cost in their schemes rises significantly as the number of users increases. Fig. 3(b) shows the comparison results of overall computational cost among four schemes. It demonstrates that the proposed LPDA-EC is the most efficient, since the most complex operations are computed as a background computation. TABLE V S IGNATURE AND VERIFICATION COMPUTATION COST COMPARISONS Scheme LPDA-EC EPPA [10] PEDA [12] SEDA [13]

Cost 2TP + (3ω + 1)TE2 + ωTM (ω + 3)TP + (ω + 1)TM (ω + 1)TP + (2ω + 1)TE2 + (ω + 1)TM 2TP + (6ω + 3)TE2 + ωTM

B. Communication Overhead The communication overhead of the proposed LPDA-EC scheme includes ET-to-ES communication and ES-to-CC communication. In the ET-to-ES communication part, each ET generates the individual data report and sends it to the ES, which is in the form of Pi = IDi ||ci ||T Si ||σion , and its size should be SETi = |IDi |+2048+|T Si |+160, if n is 1024 bits and p1 is 160 bits. Thus, the ES collects the total reports from ω users that are ST S = ωSETi in overall size in each certain time slot. Next, we consider the ES-to-CC communication part. In the report aggregation phase, the CC aggregates the ω individual reports and generates P = IDj ||c||T St ||σAgg . The aggregated report form indicates that the aggregation scheme can significantly reduce the communication overhead between ES and CC. Specifically, the overhead of ES-to-CC communication decreases from (|IDj |+2048+|T St |+160)∗ω bits to SSC = |IDj | + 2048 + |T St | + 160 bits, which means there is no correlation between ES-to-CC communication

4

2.5

4

x 10

4

x 10

LPDA−EC

LPDA−EC

EPPA

2

3.2 Time Cost (ms)

Time Cost (ms)

SEDA

1.5

EPPA PEDA

PEDA

1

0.5

2.4

SEDA

1.6

0.8

0 0

200 400 600 800 Number of Users (a) Signature and Verification Cost Comparison

0 0

1000

200 400 600 800 Number of Users (b) Overall Computational Cost Comparison

1000

Fig. 3. Computational complexity comparison 6

x 10

4000 LPDA−EC

4

Communication Overhead (Bits)

Communication Overhead (Bits)

5

EPPA SEDA

3

2

1

3200

2400

1600 LPDA−EC EPPA

800

SEDA 0 0

200

400 600 Number of Users (a) ET−to−ES Overhead

800

1000

0 0

200

400 600 Number of Users (b) ES−to−CC Overhead

800

1000

Fig. 4. Communication overhead comparison

overhead and user number. Furthermore, in Fig. 4 we plot the communication overhead in terms of the user’s number ω with comparison of three schemes, where we set the size of |ID| and |T S| be 160 bits. Since the PEDA scheme [12] does not consider the communication overhead, we only focus on the EPPA [10], SEDA [13], and LPDA-EC. It is shown that our proposed LPDA-EC scheme is the most efficient in both ETto-ES and ES-to-CC communication overheads by comparison with other two schemes. VII. C ONCLUSION In this paper, we have proposed a lightweight privacypreserving data aggregation scheme called LPDA-EC for edge computing system based on the online/offline signature technique, Paillier homomorphic cryptosystem and double trapdoor Chameleon hash function that can simultaneously achieve the privacy-preserving and lightweight aggregation. With the ES deployed at the network edge, LPDA-EC can transmit the time-consuming operations to the ES and minimum online computational cost. Detailed security analysis demonstrates that the proposed LPDA-EC scheme is secure under our defined security model. In addition, the extensive performance evaluations indicate the lightweight in computational costs and communication overheads. For our future work, we will extend our scheme to some specific application scenarios and consider the stronger adversarial model. ACKNOWLEDGMENT This work was supported in part by the National Key Research and Development Program of China under Grant 2017YFB0802303, in part by the National Natural Science Foundation of China under Grant 61672283 and Grant 61602238, in part by the Natural Science Foundation of Jiangsu Province under Grant BK20160805, and in part by the National Science Foundation grants CNS 1757533, CNS 1629746, CNS 1564128, CNS 1449860, CNS 1461932, CNS 1460971, and IIP 1439672.

R EFERENCES [1] D. He, N. Kumar, S. Zeadally, A. Vinel, and L. T. Yang, “Efficient and privacy-preserving data aggregation scheme for smart grid against internal adversaries,” IEEE Transactions on Smart Grid., vol. 8, no. 5, pp. 2411–2419, Sep. 2017. [2] A. M. Rahmani, T. N. Gia, B. Negash, A. Anzanpour, I. Azimi, M. Jiang, and P. Liljeberg, “Exploiting smart e-health gateways at the edge of healthcare internet-of-things: a fog computing approach,” Future Generation Computer Systems, vol. 78, part 2, pp. 641–658, Jan. 2018. [3] W. Ejaz, M. Naeem, A. Shahid, A. Anpalagan, and M. Jo, “Efficient energy management for the internet of things in smart cities,” IEEE Communications Magazine, vol. 55, no. 1, pp. 84–91, Jan. 2017. [4] K. Zhang, Y. Mao, S. Leng, Y. He, and Y. Zhang, “Mobile-edge computing for vehicular networks: A promising network paradigm with predictive off-loading,” IEEE Vehicular Technology Magazine, vol. 12, no. 2, pp. 36–44, Jun. 2017. [5] Y. Mao, J. Zhang, and K. B. Letaief, “Dynamic computation offloading for mobile-edge computing with energy harvesting devices,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 12, pp. 3590– 3605, Dec. 2016. [6] W. Shi, J. Cao, Q. Zhang, Y. Li, and L. Xu, “Edge computing: Vision and challenges,” IEEE Internet of Things Journal, vol. 3, no. 5, pp. 637–646, Oct. 2016. [7] X. Sun and N. Ansari, “Edgeiot: Mobile edge computing for the internet of thingss,” IEEE Communications Magazine, vol. 54, no. 12, pp. 22-29, Dec. 2016. [8] J. Zhang, B. Chen, Y. Zhao, X. Chen, and F. Hu, “Data security and privacy-preserving in edge computing paradigm: Survey and open issues,” IEEE Access, vol. 6, pp. 18209-18237, Mar. 2018. [9] F. Li, B. Luo, and P. Liu, “Secure information aggregation for smart grids using homomorphic encryption,” in in Proc of IEEE SmartGridComm’10, Gaithersburg, MD, Oct. pp. 13–16, 2012. [10] R. Lu, X. Liang, X. Li, X. Lin, and X. Shen, “Eppa: An efficient and privacy-preserving aggregation scheme for secure smart grid communications,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 9, pp. 1621–1631, Sep. 2012. [11] H. Li, X. Lin, H. Yang, X. Liang, R. Lu, and X. Shen, “Eppdr: an efficient privacy-preserving demand response scheme with adaptive key evolution in smart grid,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 8, pp. 2053–2064, Aug. 2014. [12] C.-I. Fan, S.-Y. Huang, and Y.-L. Lai, “Privacy-enhanced data aggregation scheme against internal attackers in smart grid,” IEEE Transactions on Industrial informatics, vol. 10, no. 1, pp. 666–675, Feb. 2014. [13] J. Ni, K. Alharbi, X. Lin, and X. Shen, “Security-enhanced data aggregation against malicious gateways in smart grid,” in Proc of IEEE GLOBECOM’15, San Diego, CA, USA, Dec. pp. 1–6, 2015. [14] J. Ni, K. Zhang, X. Lin, and X. Shen, “Edat: Efficient data aggregation without ttp for privacy-assured smart metering,” in Proc of IEEE ICC’16, Kuala Lumpur, Malaysia, May. pp. 1–6, 2016. [15] R. Lu, K. Heung, A.-H. Lashkari, and A.-A. Ghorbani, “A lightweight privacy-preserving data aggregation scheme for fog computing-enhanced iot,” IEEE Access, vol. 5, pp. 3302-3312, Mar. 2017. [16] D. Boneh and M. Franklin, “Identity-based encryption from the weil pairing,” in Proc of CRYPTO’01, Santa Barbara, California, USA, Aug. pp. 213–229, 2001. [17] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc of EUROCRYPT’99, Czech Republic, May. pp. 223–238, 1999. [18] C. Gao, B. Wei, D. Xie, and C. Tang, “Divisible on-line/off-line signatures,” in Proc of CT-RSA’09, San Francisco, CA, USA, Apr. pp. 148–163, 2009. [19] A. Shamir and Y. Tauman, “Improved online/offline signature schemes,” in Proc of CRYPTO’01, Santa Barbara, California, USA, Aug. pp. 355– 367, 2001. [20] D. Boneh and X. Boyen, “Short signatures without random oracles,” in Proc of EUROCRYPT’04, Interlaken, Switzerland, May. pp. 56–73, 2004. [21] D. Catalano, M. Di Raimondo, D. Fiore, and R. Gennaro, “Off-line/online signatures: theoretical aspects and experimental results,” in Proc of PKC’08, Barcelona, Spain, Mar. pp. 101–120, 2008. [22] D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” in Proc of ASIACRYPT’01, Gold Coast, Australia, Dec. pp. 514–532, 2001.