Abstract
We introduce the swap-or-not shuffle and show that the technique gives rise to a new method to convert a pseudorandom function (PRF) into a pseudorandom permutation (PRP) (or, alternatively, to directly build a confusion/diffusion blockcipher). We then prove that swap-or-not has excellent quantitative security bounds, giving a Luby-Rackoff type result that ensures security (assuming an ideal round function) to a number of adversarial queries that is nearly the size of the construction’s domain. Swap-or-not provides a direct solution for building a small-domain cipher and achieving format-preserving encryption, yielding the best bounds known for a practical scheme for enciphering credit-card numbers. The analysis of swap-or-not is based on the theory of mixing times of Markov chains.
Chapter PDF
Similar content being viewed by others
Keywords
References
Bellare, M., Ristenpart, T., Rogaway, P., Stegers, T.: Format-Preserving Encryption. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 295–312. Springer, Heidelberg (2009)
Bellare, M., Rogaway, P., Spies, T.: The FFX mode of operation for format-preserving encryption (February 2010) (submission to NIST, available from their website)
Black, J., Rogaway, P.: Ciphers with Arbitrary Finite Domains. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 114–130. Springer, Heidelberg (2002)
Brier, E., Peyrin, T., Stern, J.: BPS: a format-preserving encryption proposal (submission to NIST, available from their website)
Brightwell, M., Smith, H.: Using datatype-preserving encryption to enhance data warehouse security. In: 20th National Information Systems Security Conference Proceedings (NISSC), pp. 141–149 (1997)
Coron, J.-S., Patarin, J., Seurin, Y.: The Random Oracle Model and the Ideal Cipher Model Are Equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008)
Diaconis, P., Fill, J.: Strong stationary times via a new form of duality. Annals of Probability 18(4), 1483–1522 (1990)
FIPS 74. U.S. National Bureau of Standards (U.S.). Guidelines for implementing and using the NBS Data Encryption Standard. U.S. Dept. of Commerce (1981)
Granboulan, L., Pornin, T.: Perfect Block Ciphers with Small Blocks. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 452–465. Springer, Heidelberg (2007)
Halevi, S.: EME*: Extending EME to Handle Arbitrary-Length Messages with Associated Data. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 315–327. Springer, Heidelberg (2004)
Halevi, S., Rogaway, P.: A Tweakable Enciphering Mode. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 482–499. Springer, Heidelberg (2003)
Holenstein, T., Künzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: STOC 2011, pp. 89–98 (2011); Full version at arXiv:1011.1264
Hoang, V.T., Rogaway, P.: On Generalized Feistel Networks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 613–630. Springer, Heidelberg (2010)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. on Computing 17(2), 373–386 (1988)
Maurer, U., Pietrzak, K., Renner, R.: Indistinguishability Amplification. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 130–149. Springer, Heidelberg (2007)
Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)
Morris, B., Rogaway, P., Stegers, T.: How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 286–302. Springer, Heidelberg (2009)
Naor, M., Reingold, O.: On the construction of pseudo-random permutations: Luby-Rackoff revisited. J. of Cryptology 12(1), 29–66 (1999)
Naor, M., Reingold, O.: A pseudo-random encryption mode (1997) (manuscript)
Patarin, J.: Pseudorandom Permutations Based on the DES Scheme. In: Charpin, P., Cohen, G. (eds.) EUROCODE 1990. LNCS, vol. 514, pp. 193–204. Springer, Heidelberg (1991)
Patarin, J.: Luby-Rackoff: 7 Rounds Are Enough for \(2^{n(1-\varepsilon )}\) Security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 513–529. Springer, Heidelberg (2003)
Patarin, J.: Security of balanced and unbalanced Feistel schemes with linear non equalities. Cryptology ePrint report 2010/293 (2010)
Rudich, S.: Limits on the provable consequences of one-way functions. Ph.D. Thesis, UC Berkeley (1989)
Stefanov, E., Shi, E.: FastPRP: Fast pseudo-random permutations for small domains. Cryptology ePrint Report 2012/254 (2012)
Stütz, T., Uhl, A.: Efficient Format-Compliant Encryption of Regular Languages: Block-Based Cycle-Walking. In: De Decker, B., Schaumüller-Bichl, I. (eds.) CMS 2010. LNCS, vol. 6109, pp. 81–92. Springer, Heidelberg (2010)
Thorp, E.: Nonrandom shuffling with applications to the game of Faro. Journal of the American Statistical Association 68, 842–847 (1973)
Wen, J., Severa, M., Zeng, W., Luttrell, M., Jin, W.: Circuits and systems for video technology. IEEE Transactions on Circuits & Systems for Video Technology 12(6), 545–557 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research 2012
About this paper
Cite this paper
Hoang, V.T., Morris, B., Rogaway, P. (2012). An Enciphering Scheme Based on a Card Shuffle. In: Safavi-Naini, R., Canetti, R. (eds) Advances in Cryptology – CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-32009-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32008-8
Online ISBN: 978-3-642-32009-5
eBook Packages: Computer ScienceComputer Science (R0)