Top

Published in:

2018 | OriginalPaper | Chapter

Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the \(\chi ^2\) Method

Authors : Srimanta Bhattacharya, Mridul Nandi

Published in: Advances in Cryptology – EUROCRYPT 2018

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The construction \(\mathsf {XORP}\) (bitwise-xor of outputs of two independent n-bit random permutations) has gained broad attention over the last two decades due to its high security. Very recently, Dai et al. (CRYPTO’17), by using a method which they term the Chi-squared method (\(\chi ^2\) method), have shown n-bit security of \(\mathsf {XORP}\) when the underlying random permutations are kept secret to the adversary. In this work, we consider the case where the underlying random permutations are publicly available to the adversary. The best known security of \(\mathsf {XORP}\) in this security game (also known as indifferentiable security) is \(\frac{2n}{3}\)-bit, due to Mennink et al. (ACNS’15). Later, Lee (IEEE-IT’17) proved a better \(\frac{(k-1)n}{k}\)-bit security for the general construction \(\mathsf {XORP}[k]\) which returns the xor of k (\(\ge 2\)) independent random permutations. However, the security was shown only for the cases where k is an even integer. In this paper, we improve all these known bounds and prove full, i.e., n-bit (indifferentiable) security of \(\mathsf {XORP}\) as well as \(\mathsf {XORP}[k]\) for any k. Our main result is n-bit security of \(\mathsf {XORP}\), and we use the \(\chi ^2\) method to prove it.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Bootstrapping for Approximate Homomorphic Encryption

next chapter An Improved Affine Equivalence Algorithm for Random Permutations

In this work, we will essentially focus on information theoretic security in the ideal model. Therefore, the permutations and functions that we will consider, will be random (and not pseudorandom).

\(\chi ^2\)-distance has its origin in mathematical statistics dating back to the work of Pearson (see [LV87]). It may be observed that \(\chi ^2\)-distance is not symmetric and hence it is not a metric.

See [CT06] for a background on these topics.

We will consider another simulator in the proof of Theorem 3.

For example, such a duplicate of a tuple \((x_i, u_{0,i}, u_{1,i})\) can occur in the real world if \({\mathscr {A}}\) queries the \(\mathsf {XORP}\) with \(x_i\) and later makes a backward query to \(\mathsf {\Pi _0}\) with \(u_{0,i}\).

[AMP10]

Andreeva, E., Mennink, B., Preneel, B.: On the indifferentiability of the Grøstl hash function. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 88–105. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_7CrossRef

[BDP+13]

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G., NIST, G.: Keccak and the SHA-3 Standardization (2013)

[BDPVA08]

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_11CrossRef

[BDPVA11a]

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 320–337. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28496-0_19CrossRef

[BDPVA11b]

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the security of the keyed sponge construction. In: Symmetric Key Encryption Workshop (SKEW 2011) (2011)

[BI99]

Bellare, M., Impagliazzo, R.: A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. IACR Cryptol. ePrint Arch. 1999, 24 (1999)

[BKR98]

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/BFb0054132CrossRef

[BMN10]

Bhattacharyya, R., Mandal, A., Nandi, M.: Security analysis of the mode of JH hash function. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 168–191. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13858-4_10CrossRef

[BN18]

Bhattacharya, S., Nandi, M.: Revisiting variable output length pseudorandom functions. IACR Trans. Symmetric Cryptol. 2018(1) (2018, to appear)

[CAE]

CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness. http://competitions.cr.yp.to/caesar.html/

[CLP14]

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

[CS16a]

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_5CrossRef

[CT06]

Cover, T.M., Thomas, J.A.: Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience (2006)

[DHT17]

Dai, W., Hoang, V.T., Tessaro, S.: Information-theoretic indistinguishabilityvia the chi-squared method. In: Katz and Shacham [KS17], pp. 497–523 (2017)

[GG16]

Gilboa, S., Gueron, S.: The Advantage of Truncated Permutations, CoRR abs/1610.02518 (2016)

[GGM17]

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 (2017)MathSciNetCrossRef

[GKM+09]

Gauravaram, P., Knudsen, L.R., Matusiewicz, K., Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: Grøstl-a SHA-3 candidate. In: Dagstuhl Seminar Proceedings, Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2009)

[IMPS17]

Iwata, T., Minematsu, K., Peyrin, T., Seurin, Y.: ZMAC: a fast tweakable block cipher mode for highly secure message authentication. IACR Cryptol. ePrint Arch. 2017, 535 (2017)MATH

[IMV16]

Iwata, T., Mennink, B., Vizár, D.: CENC is optimally secure. IACR Cryptol. ePrint Arch. 2016, 1087 (2016)

[Iwa06]

Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (2006). https://doi.org/10.1007/11799313_20CrossRef

[KS17]

Katz, J., Shacham, H. (eds.): CRYPTO 2017. LNCS, vol. 10403. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9MATH

[Lee17]

Lee, J.: Indifferentiability of the sum of random permutations towards optimal security. IEEE Trans. Inf. Theory 63(6), 4050–4054 (2017)MathSciNetCrossRefMATH

[LR88]

Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)MathSciNetCrossRefMATH

[Luc00]

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_34CrossRef

[LV87]

Liese, F., Vajda, I.: Convex Statistical Distances. Teubner, Leipzig (1987)MATH

[MN17a]

Mennink, B., Neves, S.: Encrypted Davies-Meyer and its dual: Towards optimal security using Mirror theory, Cryptology ePrint Archive, Report 2017/xxx, to be published in CRYPTO 2017 (2017). http://eprint.iacr.org/2017/537

[MN17b]

Mennink, B., Neves, S.: Encrypted davies-meyer and its dual: towards optimal security using mirror theory. In: Katz and Shacham [KS17], pp. 556–583 (2017)

[MP15]

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_30CrossRef

[MPN10]

Mandal, A., Patarin, J., Nachef, V.: Indifferentiability beyond the birthday bound for the xor of two public random permutations. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 69–81. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17401-8_6CrossRef

[MRH04]

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). https://doi.org/10.1007/978-3-540-24638-1_2CrossRef

[Pat08a]

Patarin, J.: The “Coefficients H” technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328–345. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_21CrossRef

[Pat08b]

Patarin, J.: A proof of security in O(2ⁿ) 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_22CrossRef

[Pat10]

Patarin, J.: Introduction to Mirror Theory: Analysis of Systems of Linear Equalities and Linear Non Equalities for Cryptography. Cryptology ePrint Archive, Report 2017/287 (2010). http://eprint.iacr.org/2010/287

[RAB+08]

Rivest, R.L., Agre, B., Bailey, D.V., Crutchfield, C., Dodis, Y., Fleming, K.E., Khan, A., Krishnamurthy, J., Lin, Y., Reyzin, L., et al.: The MD6 hash function-a proposal to NIST for SHA-3. NIST 2(3) (2008, submitted)

[Sta78]

Stam, A.J.: Distance between sampling with and without replacement. Statistica Neerlandica 32(2), 81–91 (1978)MathSciNetCrossRefMATH

[Vau03]

Vaudenay, S.: Decorrelation: a theory for block cipher security. J. Cryptol. 16(4), 249–286 (2003)MathSciNetCrossRefMATH

[Wu11]

Wu, H.: The hash function JH, NIST (round 3), 6 (2011, submitted)

[Yas11]

Yasuda, K.: A new variant of PMAC: beyond the birthday bound. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 596–609. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_34CrossRef

Title: Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the Method
Authors: Srimanta Bhattacharya
Mridul Nandi
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2018
Print ISBN: 978-3-319-78380-2

Electronic ISBN: 978-3-319-78381-9

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-78381-9_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner