## 5 Efficiency
### Implementation  
Next, we analyze the computation cost to aggregate metering data and verify their authenticity in a neighborhood. In the proposed scheme, the stream cipher is used to encrypt metering data from each smart meter and decrypt the aggregated metering data at the concentrator. In general, a block cipher like AES is typically 100 times faster than RSA encryption and 2000 times faster than RSA decryption, with about 60 MB per second on a modest platform [38]. Stream ciphers are even faster, and our symmetric encryption is able to encrypt and decrypt 100 MB per second or more. Therefore, the computation overhead for encryption and decryption operations in the proposed scheme is negligible compared to the previous schemes [3, 5, 6] using [PERSON]'s asymmetric homomorphic encryption [9, 11]. The most time-consuming operations in the proposed scheme are signature generation (by smart meters)  
Figure 4: Total message size for an aggregation (log scale). Figure 3: Total message size for an aggregation (linear scale). and verification (by the concentrator), which are based on pairing computations. Thus, we measure only the asymmetric computations required for signature generation and verification in the proposed scheme. We used a Type A curve (in the pairing-based cryptography (PBC) library [39]) providing groups in which bilinear map \(e:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_{T}\) is defined. Although such curves provide good computational efficiency (especially for pairing computation), the same does not hold from the point of view of the space required to represent group elements. Indeed, each element of \(\mathbb{G}\) requires 512 bits at an 80-bit security level and 1536 bits when 128-bit security is chosen. Table 3 shows the computational times for signature generation by a smart meter and signature verification by a concentrator. For each operation, we include benchmark timing. Each cryptographic operation was implemented using the PBC library version 0.4.18 [39] on a PC with 3.0 GHZ processor. The public key parameters were selected to provide 80-bit security. The implementation uses a 160-bit elliptic curve group based on the supersingular curve \(y^{2}=x^{3}+x\) over a 512-bit finite field. The computational cost is analyzed in terms of the pairing and exponentiation operations in \(\mathbb{G}\) and \(\mathbb{G}_{T}\). The comparatively negligible hash operations are ignored. As shown in Table 3, each smart meter needs a constant time period to generate an aggregate signature for its data which is independent of the number of smart meters in the neighborhood. The concentrator, on the other hand, needs a time period which has a linear relationship with the number of meters in order to verify the aggregate signature. However, this cost could be alleviated by reducing the aggregate group size in practice (though the size should be set at more than two to provide user privacy). In practice, the size of the aggregate group would be determined on the basis of the size of the smart grid system. For example, the aggregate group size can be determined by considering the hop counts (between the smart meter and the collection unit) and the grid network delay [5,6]. When an aggregate group consists of \(N\) smart meters and the aggregation tree is constructed with a complete binary tree (the root node is the concentrator in the tree), the maximum hop counts from the meter to the concentrator is \(\text{log}(N+2)-1\). Since the average hop count is 15, and the network delay for each hop is currently 20 ms for the Internet [14], \(N\) could be set to at least \(2^{16}-2\approx 65500\) in grid networks using the Internet. When it comes to the number of collectors in the grid network, it can be set to \(S/N\approx S/65500\) where \(S\) is the whole size or total number of nodes in the grid network. As seen in Table 3, it takes \((0.2N+11.6)\)ms for the concentrator to verify the integrity of the received data while the decryption time is comparably negligible.