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

Unlinkable Updatable Hiding Databases and Privacy-Preserving Loyalty Programs

Published Online: 27 Apr 2021
Page range: 95 - 121
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 allow vendors to profile buyers based on their purchase histories, which can reveal privacy sensitive information. Existing privacy-friendly loyalty programs force buyers to choose whether their purchases are linkable. Moreover, vendors receive more purchase data than required for the sake of profiling. We propose a privacy-preserving loyalty program where purchases are always unlinkable, yet a vendor can profile a buyer based on her purchase history, which remains hidden from the vendor. Our protocol is based on a new building block, an unlinkable updatable hiding database (HD), which we define and construct. HD allows the vendor to initialize and update databases stored by buyers that contain their purchase histories and their accumulated loyalty points. Updates are unlinkable and, at each update, the database is hidden from the vendor. Buyers can neither modify the database nor use old versions of it. Our construction for HD is practical for large databases.

Keywords

[1] Masayuki Abe, Jens Groth, Kristiyan Haralambiev, and Miyako Ohkubo. Optimal structure-preserving signatures in asymmetric bilinear groups. In CRYPTO 2011, pages 649–666.Search in Google Scholar

[2] Joseph A. Akinyele, Christina Garman, Ian Miers, Matthew W. Pagano, Michael Rushanan, Matthew Green, and Aviel D. Rubin. Charm: a framework for rapidly prototyping cryptosystems. J. Cryptographic Engineering, 3(2):111–128, 2013.Search in Google Scholar

[3] Roy L Anderson, Joan M Ziegler, and Jacob Y Wong. Anonymous merchandise delivery system, 2010. US Patent 7,693,798.Search in Google Scholar

[4] Alberto Blanco-Justicia and Josep Domingo-Ferrer. Privacy-preserving loyalty programs. In DPM 2014, SETOP 2014, QASA 2014, pages 133–146.Search in Google Scholar

[5] Johannes Blömer, Jan Bobolz, Denis Diemert, and Fabian Eidens. Updatable anonymous credentials and applications to incentive systems. In ACM CCS 2019, pages 1671–1685.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. IACR Cryptol. ePrint Arch., 2020:382.Search in Google Scholar

[7] Jan Camenisch, Rafik Chaabouni, and Abhi Shelat. Effi-cient protocols for set membership and range proofs. In ASIACRYPT 2008, pages 234–252.Search in Google Scholar

[8] Jan Camenisch, Maria Dubovitskaya, and Alfredo Rial. UC commitments for modular protocol design and applications to revocation and attribute tokens. In CRYPTO 2016, pages 208–239.Search in Google Scholar

[9] Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Compact e-cash. In EUROCRYPT 2005, pages 302–321.Search in Google Scholar

[10] Jan Camenisch, Stephan Krenn, and Victor Shoup. A framework for practical universally composable zero-knowledge protocols. In ASIACRYPT 2011, pages 449–467.Search in Google Scholar

[11] Jan Camenisch, Anja Lehmann, Gregory Neven, and Alfredo Rial. Privacy-preserving auditing for attribute-based credentials. In ESORICS 2014, pages 109–127.Search in Google Scholar

[12] Jan Camenisch and Anna Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT 2001, pages 93–118.Search in Google Scholar

[13] Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In FOCS 2001, pages 136–145.Search in Google Scholar

[14] Dario Catalano and Dario Fiore. Vector commitments and their applications. In PKC 2013, pages 55–72.Search in Google Scholar

[15] George Danezis, Markulf Kohlweiss, Benjamin Livshits, and Alfredo Rial. Private client-side profiling with random forests and hidden markov models. In PETS 2012, pages 18–37.Search in Google Scholar

[16] Matthias Enzmann and Markus Schneider. A privacy-friendly loyalty system for electronic marketplaces. In 2004 IEEE International Conference on e-Technology, e-Commerce, and e-Services (EEE 04), pages 385–393.Search in Google Scholar

[17] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct nizks without pcps. In EUROCRYPT 2013, pages 626–645.Search in Google Scholar

[18] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281–308, 1988.Search in Google Scholar

[19] Oliver Hinz, Eva Gerstmeier, Omid Tafreschi, Matthias Enzmann, and Markus Schneider. Customer loyalty programs and privacy concerns. BLED 2007 Proceedings, page 32, 2007.Search in Google Scholar

[20] Malika Izabachène, Benoît Libert, and Damien Vergnaud. Block-wise p-signatures and non-interactive anonymous credentials with efficient attributes. In Cryptography and Coding - 13th IMA International Conference, IMACC 2011, pages 431–450.Search in Google Scholar

[21] Tun-Min Catherine Jai and Nancy J King. Privacy versus reward: Do loyalty programs increase consumers’ willingness to share personal information with third-party advertisers and data brokers? Journal of Retailing and Consumer Services, 28:296–303, 2016.Search in Google Scholar

[22] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT 2010, pages 177–194.Search in Google Scholar

[23] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In ACM STOC 1992, pages 723–732.Search in Google Scholar

[24] Markulf Kohlweiss and Alfredo Rial. Optimally private access control. In WPES 2013, pages 37–48, 2013.Search in Google Scholar

[25] Benoît Libert, Thomas Peters, and Moti Yung. Group signatures with almost-for-free revocation. In CRYPTO 2012, pages 571–589.Search in Google Scholar

[26] Benoît Libert, Somindu C. Ramanna, and Moti Yung. Functional commitment schemes: From polynomial commitments to pairing-based accumulators from simple assumptions. In ICALP 2016, pages 30:1–30:14.Search in Google Scholar

[27] Benoît Libert and Moti Yung. Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In TCC 2010, pages 499–517.Search in Google Scholar

[28] Philip Marquardt, David Dagon, and Patrick Traynor. Impeding individual user profiling in shopper loyalty programs. In FC 2011, pages 93–101.Search in Google Scholar

[29] Milica Milutinovic, Italo Dacosta, Andreas Put, and Bart De Decker. An advanced, privacy-friendly loyalty system. In Privacy and Identity Management for Emerging Services and Technologies - 8th IFIP WG 9.2, 9.5, 9.6/11.7, 11.4, 11.6 International Summer School, pages 128–138.Search in Google Scholar

[30] Payman Mohassel, Mike Rosulek, and Alessandra Scafuro. Sublinear zero-knowledge arguments for RAM programs. In EUROCRYPT 2017, pages 501–531.Search in Google Scholar

[31] Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO ’91, pages 129–140.Search in Google Scholar

[32] Arrianto Mukti Wibowo, Kwok-Yan Lam, and Gary S. H. Tan. Loyalty program scheme for anonymous payment system. In Electronic Commerce and Web Technologies, EC-Web 2000, pages 253–265.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo