5.4. PRIVACY AND INTEGRITY PRESERVING DATA AGGREGATION (PIP) 75
e final step in the decryption process of the EC Elgamal algorithm is reverse mapping
the elliptic curve point back to the plaintext data. Unfortunately, there is no known method that
can efficiently perform the reverse mapping of a point to an integer for our mapping function.
e reverse mapping function we use is a brute force attack on the elliptic curve point mT given
point T. In our secure data aggregation scheme, decryption is only performed at the base sta-
tion. Our assumption is that the base station is a powerful machine. erefore, reverse mapping
the point using a brute force method aided by the knowledge of the range of sensed data and
heuristics such as Pollard’s method and the baby-step giant-step method is feasible.
Algorithm 5.3 Elliptic Curve Elgamal
Require: Elliptic curve parameters D D .q; FR; a; b; T; p ; h/, sensor reading m
i
, base station’s
private key z
e
and base station public key Q
e
D z
e
T
Encryption
1: Map the message m to an elliptic curve point M using a mapping function.
2: Generate a random integer a
i
.
3: Calculate C
1
D a
i
T and C
2
D M C a
i
Q
e
.
4: .C
1
; C
2
/ D .a
i
T; M C a
i
Q
e
/ is the ciphertext.
Decryption
5: Calculate
.
z
e
C
1
/ and add it to C
2
.
6: e decrypted message M is the addition .z
e
C
1
/ C C
2
.
5.4 PRIVACY AND INTEGRITY PRESERVING DATA
AGGREGATION (PIP)
is algorithm is based on the Recursive Secret Sharing (RSS) algorithm described by Parakh
and Kak in [93]. e scheme was originally proposed for achieving efficient storage relative to
the original secret sharing algorithm by Shamir which is described in Chapter 2. Secret sharing
algorithms divide data ı into n shares, which are created such that the shares do not reveal any
information about the original data and the original data can be recreated only if k shares are
combined together where k < n. RSS [93] provides a construction where the shares of the data
ı can be used to store k 2 additional pieces of information. A node with at least k shares
can easily reconstruct all of the k 1 pieces of hidden information. In our algorithm, we use
secret sharing for achieving confidentiality, since the shares themselves are completely random
and do not reveal any information about the data. We provide a construction in which we can
prevent a node which has all the shares from reconstructing and retrieving the hidden data. Our
construction preserves the homomorphic property of SSS and RSS which is used to aggregate
data in a privacy preserving manner.
e basic idea is to create shares for a given sensor reading using RSS. Each node then
sends all of the shares to its parent. Because RSS is based on SSS, it is additively homomorphic
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.