In this paper, we address the problem of demand response of electrical vehicles (EVs) during microgrid outages in the smart grid through the application of Vehicle-to-Grid (V2G) technology. Particularly, we present a novel privacy-preserving double auction scheme. In our auction market, the MicroGrid Center Controller (MGCC) acts as the auctioneer, solving the social welfare maximization problem of matching buyers to sellers, and the cloud is used as a broker between bidders and the auctioneer, protecting privacy through homomorphic encryption. Theoretical analysis is conducted to validate our auction scheme in satisfying the intended economic and privacy properties (e.g., strategy-proofness and k-anonymity). We also evaluate the performance of the proposed scheme to confirm its practical effectiveness. © 2017 IEEE.