Beyond-birthday secure domain-preserving PRFs from a single permutation. (English) Zbl 1445.94020

Summary: This paper revisits the fundamental cryptographic problem of building pseudorandom functions (PRFs) from pseudorandom permutations (PRPs). We prove that, \(\mathsf{SUMPIP}\), i.e. \(P \oplus P^{-1}\), the sum of a PRP and its inverse, and \(\mathsf{EDMDSP}\), the single-permutation variant of the “dual” of the Encrypted Davies-Meyer scheme introduced by B. Mennink and S. Neves [Crypto 2017, Lect. Notes Comput. Sci. 10403, 556–583 (2017; Zbl 1418.94056)], are secure PRFs up to \(2^{2n/3}/n\) adversarial queries. To our best knowledge, \(\mathsf{SUMPIP}\) is the first parallelizable, single-permutation-based, domain-preserving, beyond-birthday secure PRP-to-PRF conversion method.


94A60 Cryptography
68P25 Data encryption (aspects in computer science)


Zbl 1418.94056


Full Text: DOI


[1] Babai L.: The Fourier transform and equations over finite Abelian groups: an introduction to the method of trigonometric sums (lecture notes), Version 1.3, Section 4. http://people.cs.uchicago.edu/laci/reu02/fourier.pdf.
[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).
[3] Bellare M., Desai A., Jokipii E., Rogaway P.: A concrete security treatment of symmetric encryption. In: Proceedings, 38th Annual Symposium on Foundations of Computer Science, pp. 394-403. IEEE (1997).
[4] Bellare, M.; Krovetz, T.; Rogaway, P.; Nyberg, K. (ed.), Luby-Rackoff backwards: increasing security by making block ciphers non-invertible, No. 1403, 266-280, (1998), Berlin · Zbl 0994.94521
[5] Bellare, M.; Kilian, J.; Rogaway, P., The security of the cipher block chaining message authentication code, J. Comput. Syst. Sci., 61, 362-399, (2000) · Zbl 0970.68054
[6] Bellare, M.; Rogaway, P.; Vaudenay, S. (ed.), The security of triple encryption and a framework for code-based game-playing proofs, No. 4004, 409-426, (2006), Berlin · Zbl 1140.94321
[7] Bhattacharya S., Nandi M.: Full Indifferentiable Security of the XOR of two or more random permutations using the \(\chi ^2\) method. In: EUROCRYPT 2018, Part I, pp. 387-412 (2018). · Zbl 1423.94053
[8] Bogdanov, A.; Knudsen, LR; Leander, G.; Paar, C.; Poschmann, A.; Robshaw, MJB; Seurin, Y.; Vikkelsoe, C.; Paillier, P. (ed.); Verbauwhede, I. (ed.), PRESENT: an ultra-lightweight block cipher, No. 4727, 450-466, (2007), Berlin · Zbl 1142.94334
[9] Borghoff, J.; Canteaut, A.; Güneysu, T.; Kavun, E.; Knezevic, M.; Knudsen, LR; Leander, G.; Nikov, V.; Paar, C.; Rechberger, C.; Rombouts, P.; Thomsen, S.; Yalçn, T.; Wang, X. (ed.); Sako, K. (ed.), PRINCE-a low-latency block cipher for pervasive computing applications, No. 7658, 208-225, (2012), Berlin · Zbl 1292.94035
[10] Chen, S.; Steinberger, J.; Nguyen, PQ (ed.); Oswald, E. (ed.), Tight security bounds for key-alternating ciphers, No. 8441, 327-350, (2014), Berlin · Zbl 1317.94096
[11] Chen, S.; Lampe, R.; Lee, J.; Seurin, Y.; Steinberger, J.; Garay, JA (ed.); Gennaro, R. (ed.), Minimizing the two-round Even-Mansour cipher, No. 8616, 39-56, (2014), Berlin · Zbl 1317.94095
[12] Cogliati, B.; Seurin, Y.; Iwata, T. (ed.); Cheon, JH (ed.), Beyond-birthday-bound security for tweakable Even-Mansour ciphers with linear tweak and key mixing, No. 9453, 134-158, (2015), Berlin · Zbl 1375.94113
[13] Cogliati, B.; Seurin, Y.; Robshaw, M. (ed.); Katz, J. (ed.), EWCDM: an efficient, beyond-birthday secure, nonce-misuse resistant MAC, No. 9814, 121-149, (2016), Berlin · Zbl 1351.94034
[14] Cogliati B., Seurin Y.: Analysis of the single-permutation encrypted Davies-Meyer construction. Des. Codes Cryptogr. (2018). https://doi.org/10.1007/s10623-018-0470-9. · Zbl 1442.94035
[15] Cogliati, B.; Lampe, R.; Patarin, J.; Cid, C. (ed.); Rechberger, C. (ed.), The indistinguishability of the XOR of \(k\) permutations, No. 8540, 285-302, (2014), Berlin
[16] Dai, W.; Hoang, VT; Tessaro, S.; Katz, J. (ed.); Shacham, H. (ed.), Information-theoretic indistinguishability via the chi-squared method, No. 10403, 497-523, (2017), Berlin · Zbl 1418.94042
[17] Dodis, Y.; Pietrzak, K.; Puniya, P.; Smart, N. (ed.), A new mode of operation for block ciphers and length-preserving MACs, No. 4965, 198-219, (2008), Berlin · Zbl 1149.94311
[18] Dodis, Y.; Reyzin, L.; Rivest, RL; Shen, E.; Dunkelman, O. (ed.), Indifferentiability of permutation-based compression functions and tree-based modes of operation, with applications to MD6, No. 5665, 104-121, (2009), Berlin · Zbl 1248.94065
[19] Dziembowski S., Pietrzak K.: Leakage-resilient cryptography. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, 25-28 October, 2008, Philadelphia, PA, pp. 293-302 (2008). https://doi.org/10.1109/FOCS.2008.56.
[20] Gilboa S., Gueron S.: The Advantage of Truncated Permutations (2012). arXiv:1610.02518.
[21] Hall, C.; Wagner, D.; Kelsey, J.; Schneier, B.; Krawczyk, H. (ed.), Building PRFs from PRPs, No. 1462, 370-389, (1998), Berlin · Zbl 0931.94045
[22] Hoang, VT; Tessaro, S.; Robshaw, M. (ed.); Katz, J. (ed.), Key-alternating ciphers and key-length extension: exact bounds and multi-user security, No. 9814, 3-32, (2016), Berlin · Zbl 1351.94051
[23] Kiltz, E.; Pietrzak, K.; Szegedy, M.; Canetti, R. (ed.); Garay, JA (ed.), Digital signatures with minimal overhead from indifferentiable random invertible functions, No. 8042, 571-588, (2013), Berlin · Zbl 1310.94156
[24] Luby M., Rackoff C.: Pseudo-random permutation generators and cryptographic composition. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC’86, ACM, New York, NY, pp. 356-363 (1986)
[25] Lucks, S.; Preneel, B. (ed.), The sum of PRPs is a secure PRF, No. 1807, 470-484, (2000), Berlin · Zbl 1082.94526
[26] Mandal, A.; Patarin, J.; Nachef, V.; Gong, G. (ed.); Gupta, KC (ed.), Indifferentiability beyond the birthday bound for the XOR of two public random permutations, No. 6498, 69-81, (2010), Berlin Heidelberg · Zbl 1253.94061
[27] Maurer, U.; Pietrzak, K.; Biham, E. (ed.), The security of many-round Luby-Rackoff pseudo-random permutations, No. 2656, 544-561, (2003), Berlin · Zbl 1038.94542
[28] Maurer, U.; Renner, R.; Holenstein, C.; Naor, M. (ed.), Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, No. 2951, 21-39, (2004), Berlin · Zbl 1197.94196
[29] Mennink, B.; Neves, S.; Katz, J. (ed.); Shacham, H. (ed.), Encrypted Davies-Meyer and its dual: towards optimal security using mirror theory, No. 10403, 556-583, (2017), Berlin · Zbl 1418.94056
[30] Mennink, B.; Neves, S., Optimal PRFs from blockcipher designs, IACR Trans. Symmetric Cryptol., 2017, 228-252, (2017)
[31] Mennink, B.; Preneel, B.; Safavi-Naini, R. (ed.); Canetti, R. (ed.), Hash functions based on three permutations: a generic security analysis, No. 7417, 330-347, (2012), Berlin · Zbl 1296.94132
[32] Mennink, B.; Preneel, B.; Malkin, T. (ed.); Kolesnikov, V. (ed.); Lewko, AB (ed.); Polychronakis, M. (ed.), On the XOR of multiple random permutations, No. 9092, 619-634, (2015), Berlin · Zbl 1423.94089
[33] Patarin, J.; Franklin, M. (ed.), Security of random Feistel schemes with 5 or more rounds, No. 3152, 106-122, (2004), Berlin · Zbl 1104.94035
[34] Patarin, J.; Safavi-Naini, R. (ed.), A proof of security in \(O(2^n)\) for the XOR of two random permutations, No. 5155, 232-248, (2008), Berlin · Zbl 1162.94397
[35] Patarin, J.; Avanzi, RM (ed.); Keliher, L. (ed.); Sica, F. (ed.), The “Coefficients H” technique, No. 5381, 328-345, (2009), Berlin
[36] 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).
[37] 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).
[38] Steinberger J.: The sum-capture problem for Abelian groups. (2014). arXiv:1309.5582.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.