BBA+: Improving the Security and Applicability of Privacy-Preserving Point Collection

Gunnar Hartung, Max Hoffmann, Matthias Nagel, Andy Rupp

ACM CCS 2017 on Oct. 30–Nov. 3, 2017, Dallas, TX, USA


Black-box accumulation (BBA) has recently been introduced as a building-block for a variety of user-centric protocols such as loyalty, refund, and incentive systems. Loosely speaking, this building block may be viewed as a cryptographic “piggy bank” that allows a user to collect points (aka incentives, coins, etc.) in an anonymous and unlinkable way. A piggy bank may be “robbed” at some point by a user, letting her spend the collected points, thereby only revealing the total amount inside the piggy bank and its unique serial number. In this paper we present BBA+, a definitional framework extending the BBA model in multiple ways: (1) We support offline systems in the sense that there does not need to be a permanent connection to a serial number database to check whether a presented piggy bank has already been robbed. (2) We enforce the collection of “negative points” which users may not voluntarily collect, as this is, for example, needed in pre-payment or reputation systems. (3) The security property formalized for BBA+ schemes is stronger and more natural than for BBA: Essentially, we demand that the amount claimed to be inside a piggy bank must be exactly the amount legitimately collected with this piggy bank. As piggy bank transactions need to be unlinkable at the same time, defining this property is highly non-trivial. (4) We also define a stronger form of privacy, namely forward and backward privacy. Besides the framework, we show how to construct a BBA+ system from cryptographic building blocks and present the promising results of a smartphone-based prototypical implementation. They show that our current instantiation may already be useable in practice, allowing to run transactions within a second—while we have not exhausted the potential for optimizations.