Practical Multi-Coupon Schemes with Strong Unsplittability

So far, one main obstacle in constructing multi-coupon schemes is how to devise an efficient issue protocol in which the size of the multi-coupons can be chosen freely and the complexity of the resultant protocol is not dependent on the size of the multi-coupons. Another obstacle is how to provide efficient and flexible mechanisms for redemption protocol. This paper overcame these problems by proposing two revised schemes with improved efficiency and functionality. In order to specify the size of multi-coupons flexibly, the new schemes employed the discrete logarithm based range proof by Chaabouni et al. and the knowledge proof of committed values by Canard et al. respectively. In addition, the computation complexities of redemption protocols were optimized by making use of the batch zero-knowledge proof and verification by Peng et al. It can be proved that the new schemes are secure in Nguyen's security model for multi-coupon schemes. Moreover, the new schemes for the first time achieve all the desirable features required in applications, i.e., concurrent issuing, compact storage, batch redeeming, as well as supporting coupon's object and its expiration date. Furthermore, performance comparison shows that their communication and computation overheads are significantly lower than the previous two schemes with strong unsplittability.