A Privacy-Protecting Multi-Coupon Scheme with Stronger Protection against Splitting

Abstract. A multi-coupon (MC) represents a collection of k coupons that a user can redeem to a vendor in exchange for some goods or services. Nguyen (FC 2006), deepening the ideas of Chen et al. (FC 2005), introduced an unforgeable privacy-protecting MC system with constant complexity for issuing and redemption of MCs, that discourages sharing of coupons through a property called weak unsplittability, where sharing of a single coupon implies sharing of the whole multi-coupon (all-ornothing sharing). Both schemes still lack some features required by many applications in practice, and also stronger forms of unsplittability are desirable. In this paper, we propose a new security model for MC systems with stronger definitions, followed by a concrete realization where single coupons within a MC may represent different goods or services, have independent validity periods, and must be redeemed sequentially ensuring a stronger version of unsplittability compared to all-or-nothing sharing. The complexity of the proposed scheme is linear in k for the generation of multi-coupons and constant for each redeemed single coupon