1. bookVolume 2021 (2021): Issue 3 (July 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Fast Privacy-Preserving Punch Cards

Published Online: 27 Apr 2021
Page range: 289 - 307
Received: 30 Nov 2020
Accepted: 16 Mar 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

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× reduction in the computation and a 11× reduction in the communication required to perform a “hole punch,” a 55× reduction in the communication required to redeem a punch card, and a 128× 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.

Keywords

[1] Paulo S. L. M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order. In Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers, pages 319–331, 2005.Search in Google Scholar

[2] Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya. Compact e-cash and simulatable vrfs revisited. In Pairing-Based Cryptography - Pairing 2009, Third International Conference, Palo Alto, CA, USA, August 12-14, 2009, Proceedings, pages 114–131, 2009.Search in Google Scholar

[3] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In CCS, 1993.Search in Google Scholar

[4] Daniel J. Bernstein. Curve25519: New diffie-hellman speed records. In Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, pages 207–228, 2006.Search in Google Scholar

[5] Johannes Blömer, Jan Bobolz, Denis Diemert, and Fabian Eidens. Updatable anonymous credentials and applications to incentive systems. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 1671–1685, 2019.Search in Google Scholar

[6] Jan Bobolz, Fabian Eidens, Stephan Krenn, Daniel Slamanig, and Christoph Striecks. Privacy-preserving incentive systems with highly efficient point-collection. In Asia CCS, 2020.Search in Google Scholar

[7] Dan Boneh and Victor Shoup. A Graduate Course in Applied Cryptography (version 0.5). 2020. https://cryptobook.us.Search in Google Scholar

[8] Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography. IACR Cryptology ePrint Archive, 2002:80, 2002.Search in Google Scholar

[9] Sean Bowe. BLS12-381: new zk-snark elliptic curve construction. https://electriccoin.co/blog/new-snark-curve/, 2017.Search in Google Scholar

[10] Daniel R. L. Brown and Robert P. Gallant. The static diffie-hellman problem. IACR Cryptology ePrint Archive, 2004:306, 2004.Search in Google Scholar

[11] Meta S. Brown. Loyalty programs and data mining.Search in Google Scholar

[12] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, pages 315–334, 2018.Search in Google Scholar

[13] Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Compact e-cash. In Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, pages 302–321, 2005.Search in Google Scholar

[14] Jan Camenisch and Anna Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In Advances in Cryptology - EURO-CRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding, pages 93–118, 2001.Search in Google Scholar

[15] Jan Camenisch and Anna Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, pages 56–72, 2004.Search in Google Scholar

[16] Jan Camenisch and Markus Stadler. Efficient group signature schemes for large groups (extended abstract). In Advances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 410–424, 1997.Search in Google Scholar

[17] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136–145. IEEE Computer Society, 2001.Search in Google Scholar

[18] Ran Canetti. Universally composable security. J. ACM, 67(5):28:1–28:94, 2020.Search in Google Scholar

[19] Melissa Chase, Sarah Meiklejohn, and Greg Zaverucha. Algebraic macs and keyed-verification anonymous credentials. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014, pages 1205–1216, 2014.Search in Google Scholar

[20] David Chaum. Blind signatures for untraceable payments. In Advances in Cryptology: Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982, pages 199–203, 1982.Search in Google Scholar

[21] David Chaum. Security without identification: Transaction systems to make big brother obsolete. Commun. ACM, 28(10):1030–1044, 1985.Search in Google Scholar

[22] David Chaum and Torben P. Pedersen. Wallet databases with observers. In Advances in Cryptology - CRYPTO ’92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, pages 89–105, 1992.Search in Google Scholar

[23] Jung Hee Cheon. Security analysis of the strong diffie-hellman problem. In Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, pages 1–11, 2006.Search in Google Scholar

[24] Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, pages 476–493, 2013.Search in Google Scholar

[25] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, 22(6):644–654, 1976.Search in Google Scholar

[26] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, 1986.Search in Google Scholar

[27] Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword search and oblivious pseudorandom functions. In Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, pages 303–324, 2005.Search in Google Scholar

[28] Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part II, pages 33–62, 2018.Search in Google Scholar

[29] Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, pages 1–17, 2013.Search in Google Scholar

[30] Jack Grigg, Riad Wahby, Sean Bowe, and Zhenfei Zhang. pairing-plus. https://github.com/algorand/pairing-plus, 2020.Search in Google Scholar

[31] Jens Groth and Amit Sahai. Efficient non-interactive proof systems for bilinear groups. In Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings, pages 415–432, 2008.Search in Google Scholar

[32] Nan Guo, Jianju Cheng, Bin Zhang, and Kangbin Yim. Aggregate signature-based efficient attributes proof with pairing-based anonymous credential. In 16th International Conference on Network-Based Information Systems, NBiS 2013, Seo-gu, Gwangju, CA, Korea (South), September 4-6, 2013, pages 276–281, 2013.Search in Google Scholar

[33] Sarita Harbour. What are the pros and cons of punch cards for your small business? 2017.Search in Google Scholar

[34] Gunnar Hartung, Max Hoffmann, Matthias Nagel, and Andy Rupp. BBA+: improving the security and applicability of privacy-preserving point collection. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 -November 03, 2017, pages 1925–1942, 2017.Search in Google Scholar

[35] Max Hoffmann, Valerie Fetzer, Matthias Nagel, Andy Rupp, and Rebecca Schwerdt. P4TC - provably-secure yet practical privacy-preserving toll collection. PoPETs, 2020(3):62–152, 2020.Search in Google Scholar

[36] Max Hoffmann, Michael Klooß, Markus Raiber, and Andy Rupp. Black-box wallets: Fast anonymous two-way payments for constrained devices. PoPETs, 2020(1):165–194, 2020.Search in Google Scholar

[37] Tibor Jager and Andy Rupp. Black-box accumulation: Collecting incentives in a privacy-preserving way. PoPETs, 2016(3):62–82, 2016.Search in Google Scholar

[38] K. Kasamatsu, S. Kanno, T. Kobayashi, and Y. Kawahara. Barreto-naehrig curves. Technical report, 2 2014.Search in Google Scholar

[39] Taechan Kim and Razvan Barbulescu. Extended tower number field sieve: A new complexity for the medium prime case. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, pages 543–571, 2016.Search in Google Scholar

[40] Ravie Lakshmanan. Loyalty programs cost you your personal data – are the rewards worth it? 2019.Search in Google Scholar

[41] Isis Agora Lovecruft and Henry de Valence. curve25519-dalek. https://github.com/dalek-cryptography/curve25519-dalek, 2019.Search in Google Scholar

[42] Milica Milutinovic, Italo Dacosta, Andreas Put, and Bart De Decker. ucentive: An efficient, anonymous and unlinkable incentives scheme. In 2015 IEEE TrustCom/BigDataSE/ISPA, Helsinki, Finland, August 20-22, 2015, Volume 1, pages 588–595, 2015.Search in Google Scholar

[43] Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231–262, 2004.Search in Google Scholar

[44] David Pointcheval and Olivier Sanders. Short randomizable signatures. In Topics in Cryptology - CT-RSA 2016 - The Cryptographers’ Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 - March 4, 2016, Proceedings, pages 111–126, 2016.Search in Google Scholar

[45] Andy Rupp, Foteini Baldimtsi, Gesine Hinterwälder, and Christof Paar. Cryptographic theory meets practice: Efficient and privacy-preserving payments for public transport. ACM Trans. Inf. Syst. Secur., 17(3):10:1–10:31, 2015.Search in Google Scholar

[46] Y. Sakemi, Lepidum, T. Kobayashi, and T. Saito. Pairing-friendly curves. Technical report, 3 2020.Search in Google Scholar

[47] Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, pages 239–252, 1989.Search in Google Scholar

[48] Claus-Peter Schnorr. Efficient signature generation by smart cards. J. Cryptol., 4(3):161–174, 1991.Search in Google Scholar

[49] Victor Shoup. Lower bounds for discrete logarithms and related problems. In Advances in Cryptology - EUROCRYPT ’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, 1997, Proceeding, pages 256–266, 1997.Search in Google Scholar

[50] Victor Shoup. A computational introduction to number theory and algebra. Cambridge University Press, 2006.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo