Cryptology ePrint Archive: Report 2017/695

Updatable Tokenization: Formal Definitions and Provably Secure Constructions

Christian Cachin and Jan Camenisch and Eduarda Freire-Stoegbuchner and Anja Lehmann

Abstract: Tokenization is the process of consistently replacing sensitive elements, such as credit cards numbers, with non-sensitive surrogate values. As tokenization is mandated for any organization storing credit card data, many practical solutions have been introduced and are in commercial operation today. However, all existing solutions are static yet, i.e., they do not allow for efficient updates of the cryptographic keys while maintaining the consistency of the tokens. This lack of updatability is a burden for most practical deployments, as cryptographic keys must also be re-keyed periodically for ensuring continued security. This paper introduces a model for updatable tokenization with key evolution, in which a key exposure does not disclose relations among tokenized data in the past, and where the updates to the tokenized data set can be made by an untrusted entity and preserve the consistency of the data. We formally define the desired security properties guaranteeing unlinkability of tokens among different time epochs and one-wayness of the tokenization process. Moreover, we construct two highly efficient updatable tokenization schemes and prove them to achieve our security notions.

Category / Keywords: cryptographic protocols /

Original Publication (with major differences): Financial Cryptography and Data Security 2017

Date: received 12 Jul 2017

Contact author: anj at zurich ibm com

Available format(s): PDF | BibTeX Citation

Version: 20170721:151050 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]