Abstract Vendors use loyalty programs as a mechanism to incentivize returning customers, whose repeated transactions provide sustained profit and information on the customers’ preferences. Such programs have become widespread, but they are facing criticism by business experts and consumer associations: since they facilitate profiling, a loss of consumer privacy ensues. We propose a protocol for privacy-aware loyalty programs that allows vendors and consumers to enjoy the benefits of loyalty (returning customers for the vendor and rewards for the consumers, respectively), while allowing consumers to stay anonymous and empowering them to decide how much of their profile they reveal to the vendor. The vendor must offer additional reward if he wants to learn more details on the consumer’s profile. Our protocol is based on partially blind signatures and generalization of product receipts, and provides anonymity to consumers and their purchases, while still allowing negotiated consumer profiling. We provide empirical results that confirm the viability of our approach.