[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Provable Related-Key Security of Contracting Feistel Networks

  • Conference paper
  • First Online:
Information Security and Cryptology (Inscrypt 2020)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12612))

Included in the following conference series:

Abstract

We continue the line of works constructing related-key secure PRFs (Bellare and Cash, CRYPTO 2010) and PRPs (Barbosa and Farshim, FSE 2014). In detail, we consider generalized Feistel networks using contracting round functions from \(\{0,1\}^m\) to \(\{0,1\}^n\), and explore conditions that are sufficient for such Contracting Feistel Networks (CFNs) to achieve security up to \(2^{n/2}\) adversarial queries. As results, we show that provable related-key security is achieved with \(\lceil \frac{m}{n}\rceil +3\) rounds, as long as the CFN uses two independent main keys \(K_1,K_2\) in all the rounds in a close-to-alternating manner. Our results provide new approaches to construct related-key secure variable-input-length block ciphers from related-key secure variable-input-length PRFs.

W. Yu and Y. Zhao are co-first authors of the article.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abdalla, M., Benhamouda, F., Passelègue, A., Paterson, K.G.: Related-key security for pseudorandom functions beyond the linear barrier. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 77–94. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_5

    Chapter  Google Scholar 

  2. Anderson, R., Biham, E.: Two practical and provably secure block ciphers: BEAR and LION. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 113–120. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60865-6_48

    Chapter  Google Scholar 

  3. Anderson, R., Kuhn, M.: Low cost attacks on tamper resistant devices. In: Christianson, B., Crispo, B., Lomas, M., Roe, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 125–136. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0028165

    Chapter  Google Scholar 

  4. Barbosa, M., Farshim, P.: The related-key analysis of Feistel constructions. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 265–284. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_14

    Chapter  Google Scholar 

  5. Bellare, M., Cash, D.: Pseudorandom functions and permutations provably secure against related-key attacks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 666–684. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_36

    Chapter  Google Scholar 

  6. Bellare, M., Kohno, T.: A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 491–506. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_31

    Chapter  Google Scholar 

  7. Bellare, M., Ristenpart, T., Rogaway, P., Stegers, T.: Format-preserving encryption. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 295–312. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-05445-7_19

    Chapter  Google Scholar 

  8. Biham, E.: New types of cryptanalytic attacks using related keys. J. Cryptol. 7(4), 229–246 (1994). https://doi.org/10.1007/BF00203965

    Article  MathSciNet  MATH  Google Scholar 

  9. Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1–18. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_1

    Chapter  Google Scholar 

  10. Biryukov, A., Khovratovich, D., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_14

    Chapter  Google Scholar 

  11. 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). https://doi.org/10.1007/3-540-45760-7_9

    Chapter  Google Scholar 

  12. Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_19

    Chapter  Google Scholar 

  13. Diffie, W., (translators), Ledin, G.: SMS4 encryption algorithm for wireless networks. Cryptology ePrint Archive, Report 2008/329 (2008). http://eprint.iacr.org/2008/329

  14. Dunkelman, O., Keller, N., Shamir, A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. J. Cryptol. 27(4), 824–849 (2014)

    Article  MathSciNet  Google Scholar 

  15. Fehr, S., Karpman, P., Mennink, B.: Short non-malleable codes from related-key secure block ciphers. IACR Trans. Symm. Cryptol. 2018(1), 336–352 (2018)

    Google Scholar 

  16. Feistel, H., Notz, W.A., Smith, J.L.: Some cryptographic techniques for machine-to-machine data communications. Proc. IEEE 63(11), 1545–1554 (1975)

    Article  Google Scholar 

  17. Gueron, S., Mouha, N.: Simpira v2: a family of efficient permutations using the AES round function. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 95–125. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_4

    Chapter  Google Scholar 

  18. Guo, C.: Understanding the related-key security of feistel ciphers from a provable perspective. IEEE Trans. Inf. Theory 65(8), 5260–5280 (2019). https://doi.org/10.1109/TIT.2019.2903796

  19. Hoang, V.T., Rogaway, P.: On generalized Feistel networks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 613–630. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_33

    Chapter  Google Scholar 

  20. Iwata, T., Kohno, T.: New security proofs for the 3GPP confidentiality and integrity algorithms. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 427–445. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-25937-4_27

    Chapter  Google Scholar 

  21. Knudsen, L.R.: Cryptanalysis of LOKI 91. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 196–208. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_62

    Chapter  Google Scholar 

  22. Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. J. Cryptol. 24(3), 588–613 (2011)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  24. Lucks, S.: Faster Luby-Rackoff ciphers. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 189–203. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60865-6_53

    Chapter  Google Scholar 

  25. Morris, B., Rogaway, P., Stegers, T.: How to encipher messages on a small domain. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 286–302. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_17

    Chapter  Google Scholar 

  26. Nandi, M.: On the optimality of non-linear computations of length-preserving encryption schemes. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 113–133. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48800-3_5

    Chapter  Google Scholar 

  27. Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptol. 12(1), 29–66 (1999)

    Article  MathSciNet  Google Scholar 

  28. Patarin, J.: Security of random Feistel schemes with 5 or more rounds. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 106–122. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_7

    Chapter  Google Scholar 

  29. 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_21

    Chapter  Google Scholar 

  30. Patarin, J.: Security of balanced and unbalanced Feistel schemes with linear non equalities. Cryptology ePrint Archive, Report 2010/293 (2010). http://eprint.iacr.org/2010/293

  31. Patarin, J., Nachef, V., Berbain, C.: Generic attacks on unbalanced Feistel schemes with contracting functions. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 396–411. Springer, Heidelberg (2006). https://doi.org/10.1007/11935230_26

    Chapter  Google Scholar 

  32. Sadeghiyan, B., Pieprzyk, J.: A construction for super pseudorandom permutations from a single pseudorandom function. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 267–284. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_23

    Chapter  Google Scholar 

  33. Schneier, B., Kelsey, J.: Unbalanced Feistel networks and block cipher design. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 121–144. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60865-6_49

    Chapter  Google Scholar 

  34. Shen, Y., Guo, C., Wang, L.: Improved security bounds for generalized Feistel networks. IACR Trans. Symmetric Cryptol. 2020(1), 425–457 (2020). https://doi.org/10.13154/tosc.v2020.i1.425-457

  35. Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita, T., Shirai, T.: Piccolo: an ultra-lightweight blockcipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 342–357. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_23

    Chapter  Google Scholar 

  36. Zhang, L., Wu, W.: Pseudorandomness and super pseudorandomness on the unbalanced Feistel networks with contracting functions. Chin. J. Comput. 32(7), 1320–1330 (2009). Clarified via personal communication

    Google Scholar 

  37. Zheng, Y., Matsumoto, T., Imai, H.: On the construction of block ciphers provably secure and not relying on any unproved hypotheses. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 461–480. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_42

    Chapter  Google Scholar 

Download references

Acknowledgements

We sincerely thank the reviewers of Inscrypt 2020 for their invaluable comments that help improving the quality of this paper. This work was partly supported by the Program of Qilu Young Scholars (Grant No. 61580089963177) of Shandong University.

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, Shandong University, Qingdao, Shandong, China

    Wenqi Yu, Yuqing Zhao & Chun Guo

  2. Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Qingdao, 266237, Shandong, China

    Wenqi Yu, Yuqing Zhao & Chun Guo

  3. Shandong Institute of Blockchain, Jinan, China

    Chun Guo

  4. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100093, China

    Chun Guo

Authors
  1. Wenqi Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuqing Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chun Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chun Guo .

Editor information

Editors and Affiliations

  1. Jinan University, Guangzhou, China

    Yongdong Wu

  2. Computer Science Department, Columbia University, New York, NY, USA

    Moti Yung

A Security Proof for \(\mathsf {CFN} ^{F^{3n,n}}\)

A Security Proof for \(\mathsf {CFN} ^{F^{3n,n}}\)

The main flow quite resembles Sect. 3. In detail, we first replace the keyed function \(F^{3n,n}\) with an random function \(\mathsf {RF} ^{3n,n}:\mathcal {K} \times \{0,1\} ^{3n}\rightarrow \{0,1\} ^n\) and obtain the random CFN \(\mathsf {CFN} ^{\mathsf {RF} ^{3n,n}}\) with a security gap at most \(\mathbf {Adv}^{\mathrm {\Phi } \text {-rka}[2]}_{F^{3n,n}}(D)\). This allows us to focus on analyzing \(\mathbf {Adv}^{\mathrm {\Phi } \text {-rka}[1]}_{\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}}(D)\) below.

1.1 A.1 Bad Transcripts

Definition 7

An attainable transcript \(\tau =(\mathcal {Q},\mathbf{K} )\) is bad, if the condition \(\text {EV}^{\mathsf {cf}}\vee \text {EV}^{\mathsf {sf}}\), which means either a claw or a switch exists in \(\mathbf{K} \), is fulfilled. Otherwise we say \(\tau \) is good.

It is clear that

$$\begin{aligned} {\Pr }\big [T_{id}\in \mathcal {T}_{bad}] = {\Pr }\big [\text {EV}^{\mathsf {cf}}\vee \text {EV}^{\mathsf {sf}}\big ] \le \mathbf {Adv}_\mathrm{\Phi }^{\textsf {cf}}(D) +\mathbf {Adv}_\mathrm{\Phi }^{\textsf {sf}}(D). \end{aligned}$$
(14)

1.2 A.2 Analyzing Good Transcripts

Bad Predicate. We define a “bad predicate” \(\mathsf {Bad} (\mathsf {RF} ^{3n,n})\) on the ideal keyed function \(\mathsf {RF} ^{3n,n}\), such that once \(\mathsf {Bad} (\mathsf {RF} ^{3n,n})\) is not fulfilled, the event \(T_{id}=\tau \) is equivalent to \(\mathsf {RF} ^{3n,n}\) satisfying 4q new and distinct equations. Since the keys of the 2nd and 4th rounds are same, while the keys of the 3rd and 5th rounds are also same, we need to ensure that for these four rounds, there exists 4q different equations. And then \(K_{1}^{bad}\) leads to \(\mathsf {RF} ^{3n,n}_{K_{2}}\) input collisions and \(K_{2}^{bad}\) causes \(\mathsf {RF} ^{3n,n}_{K_{1}}\) input collisions. Formally, the specific definition and probability analysis are as follows.

Definition 8

Given a function \(\mathsf {RF} ^{3n,n}\), the predicate \(\mathsf {Bad} (\mathsf {RF} ^{3n,n})\) is fulfilled, if either of the conditions “\(K_1\) is bad” and “\(K_2\) is bad” is fulfilled.

  • The condition “\(K_1\) is bad” consists of five subconditions as follows.

    (B-1) there exists i and j such that \(X_{2,i}[n+1,4n]\) = \(X_{2,j}[n+1,4n],(i\ne j)\).

    (B-2) there exists i and j such that \(X_{2,i}[n+1,4n]\) = \(X_{4,j}[n+1,4n]\).

    (B-3) there exists i and j such that \(X_{2,i}[n+1,4n]\) = \(X_{6,j}[n+1,4n]\).

    (B-4) there exists i and j such that \(X_{4,i}[n+1,4n]\) = \(X_{4,j}[n+1,4n],(i\ne j)\).

    (B-5) there exists i and j such that \(X_{4,i}[n+1,4n]\) = \(X_{6,j}[n+1,4n]\).

  • The condition “\(K_2\) is bad” consists of five subconditions as follows.

    (B-6) there exists i and j such that \(X_{5,i}[n+1,4n]\) = \(X_{5,j}[n+1,4n],(i\ne j)\).

    (B-7) there exists i and j such that \(X_{5,i}[n+1,4n]\) = \(X_{3,j}[n+1,4n]\).

    (B-8) there exists i and j such that \(X_{5,i}[n+1,4n]\) = \(X_{1,j}[n+1,4n]\).

    (B-9) there exists i and j such that \(X_{3,i}[n+1,4n]\) = \(X_{3,j}[n+1,4n],(i\ne j)\).

    (B-10) there exists i and j such that \(X_{3,i}[n+1,4n]\) = \(X_{1,j}[n+1,4n]\).

Otherwise we say \(\tau \) is good.

Similarly to Sect. 3.2, we expand the probability of each \(\mathcal (B-i)\) to \(1/2^{n}\) and obtain

$$\begin{aligned} {\Pr }\big [K_1\text { is bad}\mid \lnot (\text {EV}^{\mathsf {cf}}\vee \text {EV}^{\mathsf {sf}})\big ] \le \frac{5q^{2}}{2^{n}},\\ {\Pr }\big [K_2\text { is bad}\mid \lnot (\text {EV}^{\mathsf {cf}}\vee \text {EV}^{\mathsf {sf}})\big ] \le \frac{5q^{2}}{2^{n}}. \end{aligned}$$

And we reach,

$$\begin{aligned} {\Pr }\big [\mathsf {Bad} (\mathsf {RF} ^{3n,n})] \le \frac{10q^{2}}{2^{n}}. \end{aligned}$$
(15)

Completing the Proof. For the remaining, we fix a good transcript \(\tau =(\mathcal {Q},K)\), where \(\mathcal {Q}=(\phi _{i},X_{1,i}[1,4n],X_{7,i}[1,4n])_{i=1,...,q}\).

First, we classify RKD functions \(\phi _{i}\), suppose that the quantity of \(\phi _{i}\) is \(\alpha \), which are denoted \(\phi ^{(1)},\phi ^{(2)},\cdot \cdot \cdot ,\phi ^{(\alpha )}\) respectively. \(\mathcal {Q}_{i}\)( \(i=1,\dots ,\alpha )\) are denoted a set of transcripts with RKD functions \(\phi _{i}\). For \(i=1,\dots ,\alpha \), define

$$ \begin{aligned}&\mathcal {Q}_{i}=\big \{(\phi ^{(i)},X_{1i}[1,4n],X_{7i}[1,4n]),\dots ,(\phi ^{(i)},X_{1q_{i}}[1,4n],X_{7q_{i}}[1,4n])\big \}, \end{aligned} $$

where \(\mathcal {Q}_{i}\) has \(q_{i}\) different inputs. Suppose that \(\phi ^{(1)},\phi ^{(2)},\cdot \cdot \cdot ,\phi ^{(\alpha )}\) can derive \(\beta \) different \(K_{1}\): \(K_{1}^{(1)}\), \(K_{1}^{(2)}\), \(\dots \), \(K_{1}^{(\beta )}\) \((\beta \le \alpha )\). Suppose that q queries to Related-Key Oracle constitute of \(q_{1}^{*},\dots ,q_{\beta }^{*}\) inputs separately in \(K_{1}^{(1)}\), \(K_{1}^{(2)}\), \(\dots \), \(K_{1}^{(\beta )}\). The probability to obtain \(\tau \) in ideal word is

$$\begin{aligned} \Pr [T_{id}=\tau ]=\bigg (\frac{1}{|\mathcal {K} |}\bigg )\prod _{i=0}^{\alpha }\frac{1}{(2^{4n})_{q_{i}}}\le \bigg (\frac{1}{|\mathcal {K} |}\bigg )\Big (2^{4n}-q\Big )^{-q}. \end{aligned}$$

In a similar vein to Sect. 3.2, the probability in real world is

$$\begin{aligned}&\Pr [T_{re}=\tau ]={\Pr }\big [\textsf {RK}[\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}_K]\vdash \mathcal {Q}\big ]\cdot \Pr _{K^*}[K^*=K] \\&~=\bigg (\frac{1}{|\mathcal {K} |}\bigg )\cdot \bigg (1-{\Pr }\big [\mathsf {Bad} (\mathsf {RF} ^{3n,n})\big ] \bigg )\cdot {\Pr }\big [\textsf {RK}[\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}_K]\vdash \mathcal {Q}\mid \lnot \mathsf {Bad} (\mathsf {RF} ^{3n,n})\big ]. \end{aligned}$$

It can be seen that the event \(\textsf {RK}[\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}_K]\vdash \mathcal {Q}\) is equivalent to the event that \(\mathsf {RF} ^{3n,n}\) satisfies 4q equations for the 2rd round to the 5th round, i.e., for \(i=1,...,q\),

$$\begin{aligned}&\mathsf {RF} _{K_2}^{3n,n}(X_{2i}[n+1,4n])=X_{2i}[1,n]\oplus X_{3i}[3n+1,4n],\\&\mathsf {RF} _{K_1}^{3n,n}(X_{3i}[n+1,4n])=X_{3i}[1,n]\oplus X_{4i}[3n+1,4n],\\&\mathsf {RF} _{K_2}^{3n,n}(X_{4i}[n+1,4n])=X_{4i}[1,n]\oplus X_{5i}[3n+1,4n],\\&\mathsf {RF} _{K_1}^{3n,n}(X_{5i}[n+1,4n])=X_{5i}[1,n]\oplus X_{6i}[3n+1,4n]. \end{aligned}$$

Therefore, we have the probability

$$\begin{aligned} {\Pr }&\big [\textsf {RK}[\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}_K]\vdash \mathcal {Q}\mid \lnot \mathsf {Bad} (\mathsf {RF} ^{3n,n})\big ] \\ =~&\prod _{i=1}^{q}\bigg ({\Pr }\big [\mathsf {RF} _{K_2}^{3n,n}(X_{2i}[n+1,4n])=X_{2i}[1,n]\oplus X_{3i}[3n+1,4n]\big ] \\&\times {\Pr }\big [\mathsf {RF} _{K_1}^{3n,n}(X_{3i}[n+1,4n])=X_{3i}[1,n]\oplus X_{4i}[3n+1,4n]\big ] \\&\times {\Pr }\big [\mathsf {RF} _{K_2}^{3n,n}(X_{4i}[n+1,4n])=X_{4i}[1,n]\oplus X_{5i}[3n+1,4n]\big ] \\&\times {\Pr }\big [\mathsf {RF} _{K_1}^{3n,n}(X_{5i}[n+1,4n])=X_{5i}[1,n]\oplus X_{6i}[3n+1,4n]\big ] \bigg ) \\ =~&\Big (\frac{1}{2^{n}}\Big )^{4q}. \end{aligned}$$

In all, using Eq. (15), we have

$$\begin{aligned}&\frac{\Pr [T_{re}=\tau ]}{\Pr [T_{id}=\tau ]} \nonumber \\ \ge ~&\bigg (1-{\Pr }\big [\mathsf {Bad} (\mathsf {RF} ^{3n,n})\big ] \bigg )\cdot {\Pr }\big [\textsf {RK}[\mathsf {CFN} ^{\mathsf {RF} ^{3n,n},6}_K]\vdash \mathcal {Q}\mid \lnot \mathsf {Bad} (\mathsf {RF} ^{3n,n})\big ] \Big / \prod _{i=0}^{\alpha }\frac{1}{(2^{4n})_{q_{i}}} \nonumber \\ \ge ~&\Big (1-\frac{10q^{2}}{2^{n}}\Big )\times \Big (\frac{1}{2^{4n}}\Big )^{q}\times (2^{4n}-q)^{q} \nonumber \\ \ge ~&1-\Big (\frac{10q^{2}}{2^{n}}+ \frac{q^{2}}{2^{4n}}\Big ). \end{aligned}$$
(16)

Gathering Eq. (14) and (16), and using Lemma 1, we complete the proof of Theorem 2.

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yu, W., Zhao, Y., Guo, C. (2021). Provable Related-Key Security of Contracting Feistel Networks. In: Wu, Y., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2020. Lecture Notes in Computer Science(), vol 12612. Springer, Cham. https://doi.org/10.1007/978-3-030-71852-7_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-71852-7_31

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-71851-0

  • Online ISBN: 978-3-030-71852-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation