An Efficient Privacy Preserving Data Aggregation Scheme with
Constant Communication Overheads for Wireless Sensor Networks Piyi Yang, Zhenfu Cao, Xiaolei Dong, and Tanveer A. Zia
Abstract—Providing efficient data aggregation while preserv- the cluster (see the full version of this paper for the proof). ing data privacy in wireless sensor networks (WSNs) is a Third, our key agreement protocol saves much more storage challenging problem. Existing security schemes either incur high spaces compared with the key-pool based schemes e.g. [3], communication and computational overheads or simply fail to counter attacks when nodes are compromised. In this paper, we [4] presented before. present a multidimensional privacy preserving data aggregation scheme for WSNs which is efficient and provides strong security. II. P ROPOSED S CHEME The scheme not only provides efficient countermeasure against passive and active privacy compromising attacks, coalition at- A. System Initialization tacks from malicious base station and captured sensor nodes, In the system and sensor initialization, the base station (𝐵𝑆) but also is robust to data loss. In addition, the proposed scheme provides data aggregation with constant communication runs the similar operations in [2] to generate an elliptic curve overheads, so that the transmission cost can be significantly 𝐸 over a finite field 𝔽𝑞 , and 𝐸(𝔽𝑞 ) is a cyclic addition group reduced which makes it suitable to be used in large scale WSNs. of the order 𝑞. We denote the bit length of 𝑞 by ∣𝑞∣ = 𝑛𝑞 . To the best of our knowledge, our scheme is the first one that Let 𝑃 be a generator of 𝐸(𝔽𝑞 ). Then, 𝐵𝑆 chooses a random addresses the privacy and efficiency issues in WSNs all at once. number 𝑥 ˆ ∈ ℤ∗𝑞 as the master key, and computes 𝑃𝑝𝑢𝑏 = 𝑥 ˆ𝑃 Index Terms—Privacy preserving data aggregation, constant as the system public key. communication overhead, wireless sensor network, robust, com- 𝐵𝑆 also setups 𝑛 as the aggregation dimension, which promised node attack, coalition attack, multidimensional. means that each sensor node can collect and report 𝑛 di- mension data. It then setups a super-increasing ∑𝑖−1 sequences I. I NTRODUCTION → −𝑎 = (𝑎1 , 𝑎2 , . . . , 𝑎𝑛∑ ) such that 𝑗=1 𝑎𝑗 ⋅ 𝐾 ⋅ 𝑑 < 𝑎𝑖 for
D 𝑛 UE to the large scale of WSNs and resource con- 𝑖 = 1, . . . , 𝑛, and 𝑗=1 𝑎𝑗 ⋅ 𝐾 ⋅ 𝑑 < 𝑞. Here, 𝐾 is the straints of the sensor nodes, reporting the raw data maximum neighbors of the sensor node in a cluster, 𝑑 denotes sensed by each sensor node may significantly increase the the maximum value of all the sensed data. Next, it chooses energy consumption for communication. One specific power- four secure cryptographic hash functions [6] ℎ := {0, 1}∗ → saving mechanism used in wireless sensor networks is data {0, 1}𝑛𝑞 /2 , 𝐻 := {0, 1}∗ → {0, 1}𝐾 , 𝐻1 := {0, 1}∗ → 𝔽𝑞 , aggregation [1]. However, one issue raised by this range of and 𝐻2 := {0, 1}∗ → {0, 1}𝑛𝑞 . applications is the privacy of the data being collected. If 𝐵𝑆 publishes the system parameters params = there is no privacy protection in a data aggregation scheme, (𝐸(𝔽𝑞 ), 𝔽𝑞 , 𝑃, 𝑃𝑝𝑢𝑏 , 𝐾, − →𝑎 , ℎ, 𝐻, 𝐻1 , 𝐻2 ) and keeps the sys- the compromised nodes can overhear the transmissions and tem secret key 𝑥ˆ secret. obtain the sensitive data. Therefore, privacy preservation has become an important security requirement for secure data ag- B. Node Setup And Neighbor Key Agreement gregation in WSNs [4]. Even though many privacy preserving data aggregation schemes [3], [4], [5] have been proposed, At the beginning of this phase, the base station (𝐵𝑆) setups designing an efficient multidimensional privacy preserving each node including sensor node and cluster head. In algorithm data aggregation scheme against compromised sensor nodes, 1, we make use of a variant of Shao’s short signature [7] to malicious base station remains an open problem. generate the certificate 𝐶𝑇1 , 𝐶𝑇2 for the public key 𝑃 𝐾. In In this paper, we propose such a data aggregation scheme order to verify 𝑃 𝐾 is actually generated by 𝐵𝑆, we could for WSNs. The main contribution of this paper is as follows: perform the following verification, 𝑟′ ← 𝑃 𝐾 + 𝐶𝑇1 ⋅ 𝑃𝑝𝑢𝑏 + ? First, our scheme is the first data aggregation scheme that 𝐶𝑇2 ⋅ 𝑃, ℎ(𝑃 𝐾, 𝑟′ ) = 𝐶𝑇1 . Because 𝑟′ = 𝑃 𝐾 + 𝐶𝑇1 ⋅ 𝑃𝑝𝑢𝑏 + meets the above security goal. Second, the communication 𝐶𝑇2 ⋅𝑃 = 𝑠1 𝑃 +𝐶𝑇1 𝑥ˆ𝑃 +(𝑘−𝐶𝑇1 𝑥 ˆ)𝑃 = (𝑠1 +𝑘)𝑃 = 𝑟, we complexity of our scheme is 𝑂(1) with respect to the size of have ℎ(𝑃 𝐾, 𝑟′ ) = ℎ(𝑃 𝐾, 𝑟). Hence, the certificate 𝐶𝑇1 , 𝐶𝑇2 produced by BS is always valid. Manuscript received July 25, 2011. The associate editor coordinating the After the nodes initialization, each cluster head (CH) ex- review of this letter and approving it for publication was C.-K. Wu. P. Yang is with the Department of Computer Science and Engineering, ecutes the key agreement prepare algorithm (algorithm 2) to School of Optical-Electrical and Computer Engineering, University of Shang- initiate the key agreement process. Each node that receives the hai for Science and Technology, No.516, Jungong Road, Shanghai 200093, key agreement message executes the first round key agreement People’s Republic of China (e-mail: yang.piyi@gmail.com). Z. Cao and X. Dong are with Shanghai Jiaotong University, 800 (algorithm 3). The CH does not execute this algorithm. Each Dongchuan Road, Shanghai 200240, People’s Republic of China (e-mail: node, except the CH, executes the the second round of zfcao@cs.sjtu.edu.cn, dong-xl@cs.sjtu.edu.cn). key agreement algorithm when it receives a key agreement T, A. Zia is with the School of Computing & Mathematics, Charles Sturt University, NSW 2678, Australia (e-mail: tzia@csu.edu.au). message for the second time. The CH executes this algorithm Digital Object Identifier 10.1109/LCOMM.2011.092911.111598 when it receives the message for the first time. The second 1089-7798/11$25.00 ⃝ c 2011 IEEE 1206 IEEE COMMUNICATIONS LETTERS, VOL. 15, NO. 11, NOVEMBER 2011
round of key agreement algorithm is almost the same as Algorithm 4 Data Aggregation Prepare algorithm 3 except being executed in the reverse order (Its 1: 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ = ∅, 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− = ∅ 2: 𝑇 𝑒𝑚𝑝𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ = ∅; 𝐴𝑣𝑎𝑙𝑖𝑑 = 𝑡𝑟𝑢𝑒; 𝑁 𝑁 𝐼 = ∅ detail description is in the full version of this paper). After the key agreement, each node 𝑁𝑖 ∈ 𝒩 initializes its neighbor key list 𝑁 𝐾𝐿𝑖𝑠𝑡𝑖 = {𝑘𝑖,1 , . . . , 𝑘𝑖,𝑙 }, where 𝑘𝑖,𝑗 = Algorithm 5 Cluster Header Announce 𝑠𝑖,1 𝑃𝑗 for 1 ≤ 𝑗 ≤ 𝑙. Here, 𝑘𝑖,𝑗 means key 𝑘𝑗 of node 𝑁𝑖 , 𝑠𝑖,1 1: 𝐸 ← 𝑀; 𝑏 = 𝐻2 (𝑠2 ∣∣𝐸) means the secret key 𝑠1 of node 𝑁𝑖 . 2: select 𝐴 keys from 𝑁 𝐾𝐿𝑖𝑠𝑡 : ⟨𝑘1 , 𝐻(𝑘1 )⟩, . . . , ⟨𝑘𝐴 , 𝐻(𝑘𝐴 )⟩ 3: 𝑇 𝑒𝑚𝑝𝐴𝑁 𝐾𝐿𝑖𝑠𝑡 = {𝑘1 , . . . , 𝑘𝐴 }; 𝐿𝑖𝑠𝑡 = {𝐻(𝑘1 ), . . . , 𝐻(𝑘𝐴 )} Thus, each neighbor key 𝑘𝑖,𝑗 is symmetrically shared be- 4: send ⟨𝐸, 𝐿𝑖𝑠𝑡⟩ to the next node //encrypted with 𝑘𝑛𝑒𝑥𝑡 tween 𝑁𝑖 and 𝑁𝑗 , since 𝑘𝑖,𝑗 = 𝑠𝑖,1 𝑃𝑗 = 𝑠𝑖,1 𝑠𝑗,1 𝑃 = 𝑠𝑗,1 𝑃𝑖 = 𝑘𝑗,𝑖 for 1 ≤ 𝑗 ≤ 𝑙. At the same time, due to the hardness of Computational Diffie-Hellman (CDH) problem [6], each neighbor key 𝑘𝑖,𝑗 is secure against the external attacks. D. Recovery of Aggregated Data
Algorithm 1 Initialization of nodes After receiving the aggregated 𝑀 = ⟨𝑖𝑑, 𝑦, 𝑐⟩, the base 1: randomly choose 𝑠1 ∈ ℤ∗ 𝑞 station performs the following steps to recover the data. 2: 𝑃 𝐾 = 𝑠1 𝑃, 𝑠2 = 𝑥 ˆ ⋅ 𝐻1 (𝑖𝑑) 3: randomly selects 𝑘 from ℤ∗ 𝑞 ∙ retrieve 𝐸 by 𝑖𝑑, and compute 𝑏 = 𝐻2 (ˆ 𝑥𝐻1 (𝑖𝑑))∣∣𝐸). 4: 𝑟 = 𝑘𝑃 + 𝑃 𝐾, 𝐶𝑇1 = ℎ(𝑃 𝐾, 𝑟), 𝐶𝑇2 =𝑘−𝑥 ˆ ⋅ 𝐶𝑇1 ∙ recover 𝑚 by computing 𝑚 = 𝑐 ⊕ 𝑏. 5: preload the node with (𝑠1 , 𝑠2 , 𝑃 𝐾, 𝐶𝑇1 , 𝐶𝑇2 , params) and energy 6: 𝑎 = 0; 𝑁 𝐾𝐿𝑖𝑠𝑡 =empty; 𝑉 𝑎𝑙𝑖𝑑 =true ∙ get the current timestamp 𝑇 ′ , check ∣𝑇 ′ − 𝑇 ∣ < Δ𝑇 . If it doesn’t hold, the base station will reject the message in order to prevent the replay attack. Algorithm 2 Key Agreement Prepare ∙ compute ℎ′𝑗 = 𝐻2 (𝑦∣∣𝑏∣∣𝑇 ∣∣𝑁 𝐼∖𝑁 𝑁 𝐼) and compares it 1: 𝑀 ← ⟨𝑖𝑑, ⟨⟨0, 0, 0⟩1 , . . . , ⟨0, 0, 0⟩𝐾−1 ⟩⟩ with ℎ𝑗 . If they don’t equals, the message 𝑀 is also 2: randomly select 𝑖 from {1, 2, . . . , 𝐾 − 1} rejected. 3: replace ⟨0, 0, 0⟩𝑖 with ⟨𝑃 𝐾, 𝐶𝑇1 , 𝐶𝑇2 ⟩ in 𝑀 ∙ the base station computes 𝑏𝑖 = 𝐻2 (ˆ 𝑥𝐻1 (𝑖)∣∣𝐸) for 4: send 𝑀 to the next node 𝑖 ∈ 𝐼, where∑𝑛 𝐼 =∑ 𝑁 𝐼∖𝑁 𝑁 𝐼. Next it computes 𝑆 = 𝑦 − 𝑗=1 𝑎𝑗 ⋅ 𝑖∈𝐼 𝑏𝑖 mod 𝑞. Then it invokes algorithm ∑8 with 𝑆 to recover all aggregated sum values Algorithm 3 First Round of Key Agreement SUM𝑗 = 𝑖∈𝐼 𝑥𝑖𝑗 and the corresponding average values 1: ⟨𝑖, 𝐿𝑖𝑠𝑡⟩ ← 𝑀 2: ⟨𝑃 𝐾1 , 𝐶𝑇1,1 , 𝐶𝑇1,2 ⟩, . . . , ⟨𝑃𝐾−1 , 𝐶𝑇𝐾−1,1 , 𝐶𝑇𝐾−1,2 ⟩ ← 𝐿𝑖𝑠𝑡 AVG𝑗 = SUM𝑗 /∣𝐼∣, for 𝑗 = 1, . . . , 𝑛. Here, 𝑥𝑖𝑗 means 3: 𝑇 𝑒𝑚𝑝𝐿𝑖𝑠𝑡 = {1, 2, . . . , 𝐾 − 1} the 𝑗 dimensional sensed data of node 𝑁𝑖 . 4: for 𝑗 = 1 to 𝐾 − 1 do 5: if 𝑃𝑗 ∕= 0 then Encryption Privacy Privacy vs. Data-loss Node 6: if ℎ(𝑃 𝐾𝑗 , 𝑃 𝐾𝑗 + 𝐶𝑇𝑗,1 ⋅ 𝑃𝑝𝑢𝑏 + 𝐶𝑇𝑗,2 ⋅ 𝑃 ) == 𝐶𝑇𝑗,1 then type vs. BS BS and resilience comm. 7: 𝑘𝑗 = 𝑠1 ⋅ 𝑃 𝐾𝑗 ; 𝑁 𝐾𝐿𝑖𝑠𝑡 = 𝑁 𝐾𝐿𝑖𝑠𝑡 ∪ {⟨𝑘𝑗 , 𝐻(𝑘𝑗 )⟩} other nodes complexity 8: 𝑎 = 𝑎 + 1; 𝑇 𝑒𝑚𝑝𝐿𝑖𝑠𝑡 = 𝑇 𝑒𝑚𝑝𝐿𝑖𝑠𝑡∖{𝑗} coalition 9: else 10: wait Δ𝑇 ⋅ (𝐾 − 1) time; send 𝑀 to CH; return 11: end if HLNNA [4] node-to-CH Yes∗ No Yes∗ 𝑂(𝐾) 12: end if (CPDA protocol) 13: end for 14: if 𝑃𝑖 ∕= 0 then HLNNA [4] node-to-node Yes No No 𝑂(𝐾) 15: 𝑘𝑝𝑟𝑒𝑣 = 𝑘𝑖 (SMART 16: else protocol) 17: wait Δ𝑇 ⋅ (𝐾 − 1) time; send 𝑀 to CH 18: return CZRPJM [3] node-to-node Yes No Yes 𝑂(𝐾) 19: end if 20: randomly select 𝑗 from 𝑇 𝑒𝑚𝑝𝐿𝑖𝑠𝑡 LLS [5] node-to-CH No No Yes O(1) 21: replace ⟨𝑃 𝐾𝑗 , 𝐶𝑇𝑗,1 , 𝐶𝑇𝑗,2 ⟩ with ⟨𝑃 𝐾, 𝐶𝑇1 , 𝐶𝑇2 ⟩ in 𝐿𝑖𝑠𝑡 node-to-BS 22: 𝑀 ← ⟨𝑖𝑑, 𝐿𝑖𝑠𝑡⟩; send 𝑀 to the next node Proposed node-to-node Yes Yes Yes O(1) node-to-CH node-to-BS ∗ the original protocol can be extended to achieve this property. C. Data Aggregation Table 1. Comparison of the security feature and complexities Our two rounds multidimensional privacy preserving data aggregation protocol is inspired by Conti et al. [3]. At the beginning of the data aggregation protocol, each node runs Algorithm 6 First Round of Data Aggregation prepare algorithm (algorithm 4). The CH executes announce 1: ⟨𝐸, 𝐿𝑖𝑠𝑡⟩ ← 𝑀//decrypted with 𝑘𝑝𝑟𝑒𝑣 ; algorithm (algorithm 5) to initiate the data aggregation pro- 2: 𝑏 = 𝐻2 (𝑠2 ∣∣𝐸); ℎ1 , . . . , ℎ𝑅 ← 𝐿𝑖𝑠𝑡 3: for 𝑖 = 1 to 𝑅 do cess. Each node, except the CH, executes algorithm 6 when 4: if ∃𝑘 ∈ 𝑁 𝐾𝐿𝑖𝑠𝑡 and 𝐻(𝑘) == ℎ𝑖 then receiving the key selection announcement message 𝑀 for the 5: 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− = 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− ∪ {𝑘}; Remove ℎ𝑖 from 𝐿𝑖𝑠𝑡 6: end if first time. The CH never executes this algorithm. Each node, 7: end for except the CH, executes the second round data aggregation 8: 𝐴′ = 𝐴 − ∣𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− ∣ 9: Select 𝐴′ keys from 𝑁 𝐾𝐿𝑖𝑠𝑡∖𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− : ⟨𝑘1 , 𝐻(𝑘1 )⟩, . . . , ⟨𝑘𝐴′ , algorithm (algorithm 7) when receiving 𝑀 for the second 𝐻(𝑘𝐴′ )⟩; 𝑇 𝑒𝑚𝑝𝐴𝑁 𝐾𝐿𝑖𝑠𝑡 = {𝑘1 , . . . , 𝑘𝐴′ }; 𝐿𝑖𝑠𝑡 = 𝐿𝑖𝑠𝑡 ∪ time. The CH executes this procedure when it receives the {𝐻(𝑘1 ), . . . , 𝐻(𝑘𝐴′ )} 10: send ⟨𝐸, 𝐿𝑖𝑠𝑡⟩ to the next node //encrypted with 𝑘𝑛𝑒𝑥𝑡 message for the first time. YANG et al.: AN EFFICIENT PRIVACY PRESERVING DATA AGGREGATION SCHEME WITH CONSTANT COMMUNICATION OVERHEADS FOR WIRELESS . . .1207
Algorithm 7 Second Round of Data Aggregation a sensor node 𝑁𝑖 by trying to let 𝑁𝑖 agree on keys only with 1: if executing is CH then its neighbors (nodes controlled by the attacker) during key 2: if receiving 𝑀 first time then 3: 𝑦 = 0, ⟨𝐸, 𝐿𝑖𝑠𝑡⟩ ← 𝑀//decrypted with 𝑘𝑝𝑟𝑒𝑣 agreement phase. But the attacker must have 𝑉 keys. Since 4: else if receiving 𝑀 second time then its neighbors only share two keys with 𝑁𝑖 , as long as 𝑉 > 2, 5: ⟨𝑁 𝑁 𝐼, 𝐿𝑖𝑠𝑡, 𝑦⟩ ← 𝑀//decrypted with 𝑘𝑝𝑟𝑒𝑣 6: //𝑁 𝐼 is the set of node’s identifier in the cluster it will not have enough keys to let 𝑁𝑖 agree on, so 𝑁𝑖 will 7: ℎ𝐶𝐻 = 𝐻2 (𝑦∣∣𝑏∣∣𝑇 ∣∣𝑁 𝐼∖𝑁 𝑁 𝐼) simply not participate in the aggregation. The privacy of this 8: 𝑚 = ⟨𝐸∣∣𝑇 ∣∣ℎ𝐶𝐻 ∣∣𝑁 𝐼∖𝑁 𝑁 𝐼∣∣𝑖𝑑⟩, 𝑐 = 𝑚 ⊕ 𝑏 9: 𝑀 ← ⟨𝑖𝑑, 𝑦, 𝑐⟩; Send 𝑀 to the base station; return node will not be compromised. 10: end if 11: else 12: ⟨𝑁 𝑁 𝐼, 𝐿𝑖𝑠𝑡, 𝑦⟩ ← 𝑀//decrypted with 𝑘𝑝𝑟𝑒𝑣 ; ℎ1 , . . . , ℎ𝑅 ← 𝐿𝑖𝑠𝑡 IV. C OMPARISON 13: end if 14: for 𝑘 ∈ 𝑇 𝑒𝑚𝑝𝐴𝑁 𝐾𝐿𝑖𝑠𝑡 do Table 1 gives the comparison between our scheme and the 15: if ∃ℎ𝑖 , 𝐻(𝑘) = ℎ𝑖 then existing relevant schemes. In Table 1, the column encryption 16: remove ℎ𝑖 from 𝐿𝑖𝑠𝑡 17: else type indicates communication data is encrypted to what extent, 18: 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ = 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ ∪ {𝑘} e.g. node-to-BS means that communication is only encrypted 19: end if 20: end for from node to base station. Data-loss resilience means whether 21: for ℎ𝑖 ∈ 𝐿𝑖𝑠𝑡 do an aggregated data could be computed correctly when some 22: if ∃𝑘 ∈ 𝑁 𝐾𝐿𝑖𝑠𝑡∖𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ and 𝐻(𝑘) = ℎ𝑖 then 23: 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− = 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− ∪ {𝑘}; remove ℎ𝑖 from 𝐿𝑖𝑠𝑡 nodes do not participate or a message is lost. 24: end if 25: end for 26: 𝑁 𝑢𝑚 = ∣𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ ∪ 𝐵𝑎𝑔𝑇 𝑜𝑆𝑒𝑡(𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− )∣ V. C ONCLUSION 27: if 𝑁 𝑢𝑚 < 𝑉 then 28: 𝐴𝑣𝑎𝑙𝑖𝑑 = 𝑓 𝑎𝑙𝑠𝑒, 𝑥 = 0, 𝑁 𝑁 𝐼 = 𝑁 𝑁 𝐼 ∪ {𝑖𝑑} In this paper, we have proposed a novel multidimensional 29: else ∑𝑛 privacy preserving data aggregation scheme for wireless sensor 30: 𝑥= 𝑗=1 𝑎𝑗 ⋅ (𝑥𝑗 + 𝑏) mod 𝑞 31: end if networks (WSNs). Our scheme is efficient, secure, scalable, 32: for 𝑘 ∈ 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡+ do and resilient to data loss. To the best of our knowledge, our 33: 𝑥 = 𝑥 + 𝐻2 (𝐸∣∣𝑘) 34: end for scheme is the first one that addresses the privacy and efficiency 35: for 𝑘 ∈ 𝐴𝑁 𝐾𝐿𝑖𝑠𝑡− do issues all at once. 36: 𝑥 = 𝑥 − 𝐻2 (𝐸∣∣𝑘) 37: end for 38: send ⟨𝑁 𝑁 𝐼, 𝐿𝑖𝑠𝑡, 𝑥 + 𝑦⟩ to the next node//encrypted with 𝑘𝑛𝑒𝑥𝑡 Algorithm 8 Recovery of Aggregated Data 1: 𝕌 = ∅, 𝑥 = 𝑆 2: for 𝑗 = 𝑛 to 1 do 3: SUM𝑗 = (𝑥 − 𝑥 mod 𝑎𝑗 )/𝑎𝑗 , AVG𝑗 = SUMj /∣I∣ III. S ECURITY 4: 𝕌 = 𝕌 ∪ {(SUMj , AVG𝑗 )}; 𝑥 = 𝑥 mod 𝑎𝑗 5: end for Theorem 1: Our scheme prevents the privacy of the individ- 6: return 𝕌 ual node’s sensed data from being compromised by eavesdrop attack, malicious base station attack, compromised node attack and coalition attack. R EFERENCES Proof: It is easy to proof the security against eavesdrop, malicious base station and node-compromising attack. [1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survery ∑𝑛 Since on sensor networks,” IEEE Commun. Mag., vol. 40, no. 8, pp. 102–116, it encrypts the sensed data (𝑥1 , . . . , 𝑥𝑛 ) into 𝑥𝑖 = 𝑗=1 𝑎𝑗 ⋅ Aug. 2002. (𝑥𝑖𝑗 +𝑏𝑖 )±𝐻2 (𝐸∣∣𝑘) mod 𝑞 with a shared key 𝑏𝑖 and a selected [2] I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography. key 𝑘. Without knowing 𝑏𝑖 and 𝑘, it is impossible to recover Cambridge University Press, 1999. London Mathematical Society Lecture Note Series 265. the sensed data or the aggregated data. [3] M. Conti, L. Zhang, S. Roy, R. Di Pietro, S. Jajodia, and L. V. Mancini, The attacker can control the base station and some sensor “Privacy-preserving robust data aggregation in wireless sensor networks,” nodes to perform passive attack or active attack. For passive Security and Commun. Networks, vol. 2, no. 2, pp. 195–213, 2009. [4] W. He, X. Liu, H. Nguyen, K. Nahrstedt, and T. Abdelzaher, “PDA: attack, [3] figured out that given 𝑤 ≥ 2 nodes are compro- privacy-preserving data aggregation in wireless sensor networks,” in Proc. mised, it can have at most 2𝑤 − 2 node’s information. Thus, 26th IEEE International Conference on Computer Communications, pp. the probability of knowing a single selected key of a node is 2045–2053, May 2007. [5] X. Lin, R. Lu, and X. Shen, “MDPA: multidimensional privacy-preserving (2𝑤 − 2)/(𝐾 − 1). Then, the probability of knowing all 𝑉 aggregation scheme for wireless sensor networks,” Wireless Commun. and selected keys is ( 2𝑤−2 𝑉 𝐾−1 ) . When 𝑤 = 5, 𝐾 = 20, 𝑉 = 8 (the Mobile Computing, vol. 10, no. 6, pp. 843–856, 2010. total number of keys in each node is 𝐾 − 1 = 19, so 𝑉 = 8 [6] W. Mao, Modern Cryptography: Theory and Practice. Prentice Hall PTR, 2003. keys could be selected), it is less than 0.001. So the success [7] Z. Shao, “Short signature scheme based on discrete logarithms,” in probability of a passive attacker is negligible. For active attack, Proc. Advances in Web-Age Information Management, Lecture Notes in it can leverage the 𝑤 controlled nodes to break the privacy of Computer Science 3739, pp. 645-650, Springer-Verlag, 2005.
