An electric vehicle (EV) is a promising and futuristic automobile propelled by electric motors, using electrical energy stored in batteries or another energy storage device. Due to the need for the battery to be recharged, the cars will be required to visit a recharging infrastructure very frequently. This may disclose the users' private information, such as their location and, thus, compromise users' privacy. In this paper, we propose a new payment system that is suitable for EVs. Our system not only supports privacy protection (location privacy) but supports traceability in the case where the cars are stolen as well. Our system can further support the future vehicle-to-grid (V2G) paradigm. In addition, we prove the security and produce a proof-of-concept prototype to enumerate our system.