Previous work on electronic coupon (e-coupon) systems mainly focused on security properties such as unforgeability, doubleredemption detection, and anonymity/unlinkability. However, achieving both traceability against dishonest users and anonymity for honest users without involving any third party is an open problem that has not been solved by the previous work. Another desirable feature of an e-coupon system that has not been studied in the literature is user privacy, which means the shop cannot identify the good (among all the choices specified in the coupon) that has been chosen by the customer during the redemption process. In this paper, we present a novel e-coupon system that can achieve all these desirable properties. We define the formal security models for these new security requirements, and show that our new e-coupon system is proven secure in the proposed models.