72 5. SECURE AGGREGATION OF DATA IN A SENSOR CLOUD
tion scheme for efficient data encryption and an ECC-based aggregate digital signature scheme
that is able to aggregate and verify digital signatures. is scheme protects both the confiden-
tiality and integrity of data and is resilient against the false data injection attacks. Our second
solution is based on symmetric key approaches and also provides both data confidentiality and
data integrity. is solution is also resilient to data injection attacks and, by virtue of being a
symmetric key solution, is more energy-efficient than the first solution.
5.3 SECURE HIERARCHICAL DATA AGGREGATION
ALGORITHM
e secure hierarchical data aggregation algorithm employs homomorphic encryption and ag-
gregate digital signatures for providing end-to-end confidentiality and data integrity. e en-
cryption algorithm used is Elliptic Curve Elgamal (ECEG), which is the Elgamal encryption
algorithm adapted to work on elliptic curves. e digital signature algorithm is a version of the
Elliptic Curve Digital Signature Algorithm (ECDSA) modified to allow for signature aggre-
gation. We also designed a secure tree construction algorithm shown in Algorithm 5.1 which
favors strong bidirectional links and organizes the nodes in a tree hierarchy. e tree construc-
tion algorithm adapts to node disconnection and consists of a reconfiguration procedure shown
in Algorithm 5.2 that can be used by disconnected nodes to connect back to the network. is
procedure helps in increasing the connectivity of the network under a node capture or denial of
service attack.
After the nodes are deployed, they start the tree construction protocol and organize them-
selves in a tree hierarchy rooted at the base station. Once the tree construction is over, the nodes
start sensing data. Each node then generates a reading x. e reading is signed using the ag-
gregate signature algorithm and SIG(x) is generated. e reading is then encrypted using the
homomorphic encryption algorithm and the ciphertext ENC(x) is produced. e leaf nodes
of the tree send the encrypted data, signature and the public key corresponding to the private
key used for signature generation to their parent. After an intermediate node has received data
from all its children, it performs a summation of the encrypted readings (SUM-ENC), which is
possible because of homomorphic encryption. It also performs the summation of the signature
(SUM-SIG) using the aggregate signature algorithm and all the public keys (SUM-PK). SUM-
ENC, SUM-SIG, and SUM-PK are then sent to the node’s parent. is process is repeated at
every node until the data reaches the base station. In the remainder of this section, we discuss
the signature and encryption algorithms in more detail
5.3.1 MODIFIED ECDSA SIGNATURE ALGORITHM
e signature algorithm assumes the sensors are preloaded with the appropriate elliptic curve
parameters, the base station’s public key and a network wide random integer. e random integer
is used to compute a new integer k for each round at the sensors. Every sensor therefore generates
5.3. SECURE HIERARCHICAL DATA AGGREGATION ALGORITHM 73
Algorithm 5.1 Tree Construction Algorithm
Require: Parameters MAX_CHILDREN, NUM_NODES, Secret key k deployed on each
node
1: e base station starts by broadcasting a HELLO message, which consists of a random
number r.
2: If a sensor which has not yet elected its parent receives a HELLO message, it calculates
HMAC
k
.r/ and sends it in a PARENT REQUEST to the originator of the HELLO
message.
3: if a PARENT REQUEST is received then
4: Calculate HMAC
k
.r/ and check whether it matches the HMAC in the packet.
5: Check whether RSSI value of the request packet is greater than a minimum threshold.
6: Check that the number of children is less than the MAX_CHILDREN limit.
7: e number of requests from a particular node is less than the allowed limit.
8: If the above four checks are satisfied, send an ACCEPTED message otherwise send
REJECTED.
9: end if
10: Upon receiving an ACCEPTED message a node elects the sender of the ACCEPTED
message as its parent and broadcasts a HELLO message.
11: If a sensor has not been able to elect a parent after a certain period of time it invokes the
HELP procedure.
12: In case of a disconnection the HELP procedure is invoked by the affected nodes.
Algorithm 5.2 HELP Procedure
1: e sensor invoking the help procedure broadcasts a HELP request with a random number
r
1
.
2: Nearby sensors who are higher in the hierarchy than the HELP invoking sensor and can
accept more children reply to the HELP request with HMAC
k
.r
1
/ and a random number
r
2
.
3: e sensor calculates HMAC
k
.r
1
/, compares it with the HMAC
k
.r
1
/ in the incoming
packets and chooses one of the replying nodes as its parent. It then sends HMAC
k
.r
2
/ to
the parent.
4: e parent verifies HMAC
k
.r
2
/ and upon verification accepts the sensor as a child.
and uses the same integer k in a given round. At the start of each new data aggregation round,
sensors choose their private key z and generate a corresponding public key Q D zT where T is the
base point on the elliptic curve. In the original ECDSA algorithm a signature is a tuple .r; s/ such
that r D .r.x/ mod p/, where .r.x/; r.y// D kT, and s D k
1
.h.m/ C z r.x// mod p. Where
h is a secure hash function and p is a sufficiently large prime number. When two signatures d
1
D
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.