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

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 ex-
tending 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 pre-
sented 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
... mehr
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+ sys-
tem 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 prac-
tice, allowing to run transactions within a second—while we have
not exhausted the potential for optimizations.