A Non-Sequential Unsplittable Privacy-Protecting Multi-Coupon Scheme

Abstract

A multi-coupon (MC ) represents a collection of k coupons that a user can redeem to a vendor in exchange for a benefit (some good or service). Recently, Chen et al. [CEL+07] proposed an unforgeable privacy-protecting multi-coupon scheme (MCS), which discourages sharing of coupons through a property called unsplitta- bility, where the coupons of a single MC cannot be separately used by two users. Pre- vious MCSs relied on the all-or-nothing principle, a weaker form of unsplittability, where sharing a single coupon implies sharing the whole multi-coupon. The construc- tion proposed in [CEL+07] supports coupons with practical attributes: independent benefits, and validity periods (e.g., expiration dates). However, it has the disadvantage that the coupons contained in an MC must be redeemed in sequential order. Hence, it is suitable for fewer applications. In this paper, we address this problem and propose a scheme that satisfies the same set of security requirements, supports the same practical attributes, and offers similar efficiency, but in which users are able to choose which coupon they redeem.