Paper 2017/137
Modifying an Enciphering Scheme after Deployment
Paul Grubbs, Thomas Ristenpart, and Yuval Yarom
Abstract
Assume that a symmetric encryption scheme has been deployed and used with a secret key. We later must change the encryption scheme in a way that preserves the ability to decrypt (a subset of) previously encrypted plaintexts. Frequent real-world examples are migrating from a token-based encryption system for credit-card numbers to a format-preserving encryption (FPE) scheme, or extending the message space of an already deployed FPE. The ciphertexts may be stored in systems for which it is not easy or not efficient to retrieve them (to re-encrypt the plaintext under the new scheme). We introduce methods for functionality-preserving modifications to encryption, focusing particularly on deterministic, length-preserving ciphers such as those used to perform format-preserving encryption. We provide a new technique, that we refer to as the Zig-Zag construction, that allows one to combine two ciphers using different domains in a way that results in a secure cipher on one domain. We explore its use in the two settings above, replacing token-based systems and extending message spaces. We develop appropriate security goals and prove security relative to them assuming the underlying ciphers are themselves secure as strong pseudorandom permutations.
Note: Full version
Metadata
- Available format(s)
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2017
- Keywords
- format-preserving encryptionsymmetric-key cryptography
- Contact author(s)
- pag225 @ cornell edu
- History
- 2017-07-05: revised
- 2017-02-20: received
- See all versions
- Short URL
- https://ia.cr/2017/137
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/137, author = {Paul Grubbs and Thomas Ristenpart and Yuval Yarom}, title = {Modifying an Enciphering Scheme after Deployment}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/137}, year = {2017}, url = {https://eprint.iacr.org/2017/137} }