## 5 Efficiency
### Theoretical Analysis  
The theoretical efficiency comparison of the schemes are summarized in Table 2. The notations used in the table are:  
\[ \begin{array}{c|c}C_{\mathbb{G}}&\text{bit size of an element in }\mathbb{G}\\ C_{p}&\text{bit size of an element in }\mathbb{Z}_{p}^{*}\\ C_{n}&\text{bit size of an element in }\mathbb{Z}_{n}^{*}\\ &\text{($n=p\cdot q$ where $q$ is a large prime)}\\ C_{n^{2}}&\text{bit size of an element in }\mathbb{Z}_{n^{2}}^{*}\\ C_{ID}&\text{bit size of an identity string}\\ C_{t}&\text{bit size of a timestamp}\\ C_{m}&\text{bit size of a message (=symmetric key size)}\\ N&\text{the number of smart meters participating}\\ &\text{in the aggregation}\end{array} \]  
Each scheme is analyzed with regard to communication, message size, signature size, private key size, and public key size. Communication represents the number of message exchanges between smart meters and the concentrator, which are required for a metering data aggregation in a neighborhood. Message represents the total size of the ciphertext and the identity information that each smart meter is required to send for an aggregation. Signature represents the size of signatures that are delivered to the concentrator for an aggregation. Private and public key represent the number of private keys each smart meter stores and the number of public keys in the system for data aggregation in a neighborhood, respectively. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**System** & **Communication** & **Message** & **Signature** & **Private Key** & **Public Key** \\ \hline GJ [3] & \(N(N+1)\) & \((N-1)(C_{ID}+C_{n^{2}})+C_{m}\) & - & \(2C_{p}\) & \(N(C_{n}+C_{n^{2}})\) \\ LLL [5, 6] & \(N\) & \(C_{ID}+C_{n^{2}}\) & - & - & \(C_{n}+C_{n^{2}}\) \\ LLYLLS [21] & \(N+1\) & \((N+1)(C_{n^{2}}+2C_{ID}+C_{t})\) & \((N+1)(C_{\mathbb{G}}+C_{p})\) & \(C_{\mathbb{G}}+C_{p}+C_{m}\) & \(C_{n}+C_{n^{2}}\) \\ Proposed & \(2N+1\) & \([C_{ID}+C_{m},N(C_{ID}+C_{m})]\) & \(3C_{\mathbb{G}}\) & \(2C_{\mathbb{G}}+C_{m}\) & \(3C_{\mathbb{G}}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Efficiency comparison. In [PERSON] _et al._'s scheme [3], every smart meter in the neighborhood encrypts its own metering data with the other meters' public keys and performs a three-way handshake with the concentrator in order to aggregate metering data in the neighborhood. Thus, the scheme needs \(O(N)\) pairs of public keys of all smart meters participating in the aggregation, and \(O(N^{2})\) communications. In [PERSON] _et al._'s scheme [5, 6], each smart meter encrypts its measurement with the aggregate-so-far message under the concentrator's public key in the hop-by-hop approach following the aggregation tree. Since the smart meters do not need to decrypt messages during aggregation, they are not given private keys. In [PERSON] _et al._'s scheme [21], each meter in the same area network sends its data and signature to the local gateway directly, which is then aggregated with those from the other meters and delivered to the final concentrator. In the proposed scheme, \(N+1\) more communications are needed than [PERSON] _et al._'s scheme [5, 6] in order to establish a path key for an aggregation path. The signature size is constant regardless of the number of signers because each signature is aggregated. Since every smart meter concatenates its data to the list of identity-ciphertext pairs and forwards it to the next smart meter until it reaches the concentrator, the message size a smart meter is required to send increases in proportion to the proximity to the concentrator. As we discussed in Section 4.3, this communication overhead is caused by security requirements that ensure data integrity and sender authentication.