  Loyalty programs in the form of punch cards that can be redeemed for benefits
have long been a ubiquitous element of the consumer landscape. However, their
increasingly popular digital equivalents, while providing more convenience and
better bookkeeping, pose a considerable privacy risk. This paper introduces a
privacy-preserving punch card protocol that allows firms to digitize their
loyalty programs without forcing customers to submit to corporate surveillance.
We also present a number of extensions that allow our scheme to provide other
privacy-preserving customer loyalty features.
  Compared to the best prior work, we achieve a $14\times$ reduction in the
computation and a $11\times$ reduction in the communication required to perform
a "hole punch," a $55\times$ reduction in the communication required to redeem
a punch card, and a $128\times$ reduction in the computation time required to
redeem a card. Much of our performance improvement can be attributed to
removing the reliance on pairings or range proofs present in prior work, which
has only addressed this problem in the context of more general loyalty systems.
By tailoring our scheme to punch cards and related loyalty systems, we
demonstrate that we can reduce communication and computation costs by orders of
magnitude.
