## 1 Introduction  
Smart grids are envisioned as a next generation approach to delivering electricity to millions of households by stakeholders. Smart grids have incorporated computation and communication technology into traditional power grids, allowing them to become smart and connected. Processing and storage units are embedded in traditional electricity meters and communicate with electrical appliances at home as well as the generation and management facilities of electric utilities, providing smart grids with great connectivity. With the intelligent, networked smart meters, smart grids enable the instant monitoring of power delivery and consumption information, the subscription of power usage, remote operation, advanced demand and outage management, and usage management. The rollout of smart meters has already begun, and this new technology has been rapidly adopted in countries throughout the world. For example, the United States and the European Union currently promote the deployment of smart grids. However, despite the numerous advantages offered by smart grids, security and privacy concerns started to arise [1; 2; 3]. Smart meters are expected to automatically provide accurate readings at requested time intervals to the utility company or electricity distribution network. Frequent and detailed meter readings can be used to optimize the grid but can also reveal behavioral patterns and leak personal information. Fine-grained electricity consumption profiles differ between devices. Thus, given a sufficient resolution on the time axis, electric utilities could know the daily energy usage patterns of a household and even go so far as to deduct whether the inhabitants are at home, when they get up and go to bed, and what kind of devices are being used at which time, among other things [2; 3; 4]. User privacy concerns have already jeopardized the mandatory deployment of smart meters in the Netherlands, leading to a deployment deadlock in April 2009. Recently, several studies have proposed solutions to this problem in smart grids [3; 4; 5; 6; 7; 8]. One promising technical solution to protect user privacy is anonymizing each packet of high-frequency metering data by aggregating them at multiple levels (e.g., neighborhood, subdivision, district, and city) via privacy-protecting cryptographic techniques such as homomorphic encryption [9; 10]. In this approach, the data collection unit can obtain sums of the measurements of all the connected smart meters without learning the individual measurements. Additionally, the smart meters involved in the aggregation cannot learn any plain measurements from the other meters. Thus, customer privacy can be protected. However, most of the well-known homomorphic encryption protocols are malleable [9; 10; 11]. Thus, given the ciphertext and public key, an adversary could generate another cipher which decrypts to another meaningful plaintext in the same domain as the original plaintext. As a result, a dishonest or fake smart meter could falsify data, leading to inaccurate aggregation results. Therefore, it is of great importance to provide efficient and secure data aggregation which guarantees user privacy, authentication, and aggregated data integrity in smart grids. One straightforward solution to this problem is enabling each smart meter to sign its metering data with a private key so that the collection unit can verify the integrity of data from individual meters and authenticate the source meters with their public keys. However, this approach allows the collection unitto learn the plain meter readings of each smart meter during the verification phase, which violates the privacy of users. On the other hand, when the measurements of smart meters are aggregated using the previous homomorphic encryptions [9; 10; 11] in order to protect user privacy, a signature scheme cannot enable the collection unit to verify the authenticity of plain (aggregated or individual) data.