Abstract
One of the most prominent PRP-to-PRF designs is truncation, a method that found renewed interest with the GCM-SIV authenticated encryption scheme. A long line of research (from 1998 to 2018) shows that truncating an n-bit random permutation to m bits achieves tight \(n-m/2\) security. However, it appeared that the result was a direct consequence of a statistical result of Stam from 1978. In this work, we aim to gain better understanding in the possibilities and impossibilities of truncation. We take a closer look at the ancient result, observe that it is much more general, and link it with a generalized truncation function that uses an arbitrary post-processing function after the evaluation of the permutation. The main conclusion is that generalized truncation with any balanced post-processing achieves the same security bound as plain truncation. For unbalanced post-processing, security degrades gradually with the amount of unbalancedness. The results in particular exhibit a use of the Kullback-Leibler divergence for cryptographic indistinguishability proofs, without resorting to the recently popularized chi-squared method.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that our definition of distance has a factor \(\frac{1}{2}\) compared to that of Stam.
References
Adams, C.: The CAST-128 encryption algorithm. Request for Comments (RFC) 2144, May 1997. http://tools.ietf.org/html/rfc2144
Aoki, K., et al.: Specification of Camellia – a 128-bit Block Cipher, Version 2.0 (2001). https://info.isl.ntt.co.jp/crypt/eng/camellia/dl/01espec.pdf
Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y.: GIFT: a small present - towards reaching the limit of lightweight encryption. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 321–345. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_16
Beierle, C., et al.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 123–153. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_5
Bellare, M., Guérin, R., Rogaway, P.: XOR MACs: new methods for message authentication using finite pseudorandom functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 15–28. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_2
Bellare, M., Impagliazzo, R.: A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. Cryptology ePrint Archive, Report 1999/024 (1999). http://eprint.iacr.org/1999/024
Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48658-5_32
Bellare, M., Krovetz, T., Rogaway, P.: Luby-Rackoff backwards: increasing security by making block ciphers non-invertible. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 266–280. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054132
Bellare, M., Rogaway, P.: The security of triple encryption and a framework for code-based game-playing proofs. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 409–426. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_25
Bernstein, D.J.: SURF: simple unpredictable random function (1997). https://cr.yp.to/papers.html#surf
Bernstein, D.J.: How to stretch random functions: the security of protected counter sums. J. Cryptol. 12(3), 185–192 (1999). https://doi.org/10.1007/s001459900051
Bhattacharya, S., Nandi, M.: A note on the chi-square method: a tool for proving cryptographic security. Cryptogr. Commun. 10(5), 935–957 (2018). https://doi.org/10.1007/s12095-017-0276-z
Biham, E., Anderson, R., Knudsen, L.: Serpent: a new block cipher proposal. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 222–238. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69710-1_15
Bogdanov, A., et al.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74735-2_31
Bose, P., Hoang, V.T., Tessaro, S.: Revisiting AES-GCM-SIV: multi-user security, faster key derivation, and better bounds. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 468–499. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_18
Brassard, G.: On computationally secure authentication tags requiring short secret shared keys. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology, pp. 79–86. Springer, Boston, MA (1983). https://doi.org/10.1007/978-1-4757-0602-4_7
Chang, D., Nandi, M.: A short proof of the PRP/PRF switching lemma. Cryptology ePrint Archive, Report 2008/078 (2008). http://eprint.iacr.org/2008/078
Cogliati, B., Lampe, R., Patarin, J.: The indistinguishability of the XOR of \(k\) permutations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 285–302. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_15
Cogliati, B., Seurin, Y.: EWCDM: an efficient, beyond-birthday secure, nonce-misuse resistant MAC. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 121–149. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_5
Csiszár, I.: Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizitat von Markoffschen Ketten. Magyar. Tud. Akad. Mat. Kutató Int. Közl 8, 85–108 (1963)
Csiszár, I.: Information-type measure of difference of probability distributions and indirect observations. Stud. Sci. Math. Hung. 2, 299–318 (1967)
Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04722-4
Dai, W., Hoang, V.T., Tessaro, S.: Information-theoretic indistinguishability via the chi-squared method. In: Katz, J., Shacham, H., (eds.) [33], pp. 497–523. https://doi.org/10.1007/978-3-319-63697-9_17
Dworkin, M.: NIST SP 800–38A: Recommendation for block cipher modes of operation: methods and techniques (2001)
Gilboa, S., Gueron, S.: Distinguishing a truncated random permutation from a random function. Cryptology ePrint Archive, Report 2015/773 (2015). http://eprint.iacr.org/2015/773
Gilboa, S., Gueron, S.: The advantage of truncated permutations. CoRR abs/1610.02518 (2016). http://arxiv.org/abs/1610.02518
Gilboa, S., Gueron, S., Morris, B.: How many queries are needed to distinguish a truncated random permutation from a random function? J. Cryptol. 31(1), 162–171 (2018). https://doi.org/10.1007/s00145-017-9253-0
Gueron, S., Langley, A., Lindell, Y.: AES-GCM-SIV: specification and analysis. Cryptology ePrint Archive, Report 2017/168 (2017). http://eprint.iacr.org/2017/168
Gueron, S., Lindell, Y.: GCM-SIV: full nonce misuse-resistant authenticated encryption at under one cycle per byte. In: Ray, I., Li, N., Kruegel, C. (eds.) Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, 12–16 October 2015, pp. 109–119. ACM, New York (2015). https://doi.org/10.1145/2810103.2813613
Hall, C., Wagner, D., Kelsey, J., Schneier, B.: Building PRFs from PRPs. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 370–389. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055742
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 8–26. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_2
Iwata, T., Seurin, Y.: Reconsidering the security bound of AES-GCM-SIV. IACR Trans. Symmetric Cryptol. 2017(4), 240–267 (2017). https://doi.org/10.13154/tosc.v2017.i4.240-267
Katz, J., Shacham, H. (eds.): Advances in Cryptology - CRYPTO 2017–37th Annual International Cryptology Conference, Santa Barbara, CA, USA, 20–24 August 2017, Proceedings, Part III. LNCS, vol. 10403. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-63697-9
Kemperman, J.H.: On the optimum rate of transmitting information. Ann. Math. Stat. 40(6), 2156–2177 (1969). https://doi.org/10.1214/aoms/1177697293
Kullback, S.: A lower bound for discrimination information in terms of variation (corresp.). IEEE Trans. Inf. Theory 13(1), 126–127 (1967). https://doi.org/10.1109/TIT.1967.1053968
Kullback, S., Leibler, R.A.: On information and sufficiency. Ann. Math. Stat. 22(1), 79–86 (1951). https://doi.org/10.1214/aoms/1177729694
Lindell, Y., Langley, A., Gueron, S.: AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption. Internet-Draft draft-irtf-cfrg-gcmsiv-05, Internet Engineering Task Force, May 2017, Work in Progress. https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-gcmsiv-05
Lucks, S.: The sum of PRPs is a secure PRF. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 470–484. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_34
McGrew, D.A., Viega, J.: The security and performance of the Galois/Counter Mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343–355. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30556-9_27
Mennink, B., Neves, S.: Encrypted Davies-Meyer and its dual: towards optimal security using mirror theory. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 556–583. https://doi.org/10.1007/978-3-319-63697-9_19
Mennink, B., Neves, S.: Optimal PRFs from blockcipher designs. IACR Trans. Symmetric Cryptol. 2017(3), 228–252 (2017). https://doi.org/10.13154/tosc.v2017.i3.228-252
Mennink, B., Preneel, B.: On the XOR of multiple random permutations. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 619–634. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_30
Morimoto, T.: Markov processes and the \(H\)-theorem. J. Phys. Soc. Jpn. 18(3), 328–331 (1963). https://doi.org/10.1143/JPSJ.18.328
Patarin, J.: A proof of security in \(O(2^n)\) for the Xor of two random permutations. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 232–248. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85093-9_22
Patarin, J.: Introduction to mirror theory: analysis of systems of linear equalities and linear non equalities for cryptography. Cryptology ePrint Archive, Report 2010/287 (2010). http://eprint.iacr.org/2010/287
Patarin, J.: Security in \(O(2^n)\) for the Xor of two random permutations - proof with the standard \(h\) technique-. Cryptology ePrint Archive, Report 2013/368 (2013). http://eprint.iacr.org/2013/368
Stam, A.J.: Distance between sampling with and without replacement. Stat. Neerl. 32(2), 81–91 (1978). https://doi.org/10.1111/j.1467-9574.1978.tb01387.x
Stam, A.J.: A note on sampling with and without replacement. Stat. Neerl. 40(1), 35–38 (1986). https://doi.org/10.1111/j.1467-9574.1986.tb01162.x
Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. J. Comput. Syst. Sci. 22(3), 265–279 (1981). https://doi.org/10.1016/0022-0000(81)90033-7
Acknowledgments
Bart Mennink is supported by a postdoctoral fellowship from the Netherlands Organisation for Scientific Research (NWO) under Veni grant 016.Veni.173.017. The author would like to thank the reviewers for their detailed comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Mennink, B. (2019). Linking Stam’s Bounds with Generalized Truncation. In: Matsui, M. (eds) Topics in Cryptology – CT-RSA 2019. CT-RSA 2019. Lecture Notes in Computer Science(), vol 11405. Springer, Cham. https://doi.org/10.1007/978-3-030-12612-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-12612-4_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12611-7
Online ISBN: 978-3-030-12612-4
eBook Packages: Computer ScienceComputer Science (R0)