Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Crooked Indifferentiability of the Feistel Construction

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 15489))

  • 368Accesses

  • 1Citation

Abstract

The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks—that is, adversarial subversion—of the component round functions. Specifically, we establish that a Feistel-based construction with more than\(337n/\log (1/\epsilon )\) rounds can transform a subverted random function—which disagrees with the original one at a small fraction (denoted by\(\epsilon \)) of inputs—into an object that iscrooked-indifferentiable from a random permutation (or ideal cipher), even if the adversary is aware of all the randomness used in the transformation. Here,n denotes the length of both the input and output of the round functions that underlie the Feistel cipher. We also provide a lower bound showing that the construction cannot use fewer than\(2n/\log (1/\epsilon )\) rounds to achieve crooked-indifferentiable security.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8465
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • 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

Similar content being viewed by others

Notes

  1. 1.

    For technical reasons, we need to encode the input of the round function with the pairwise independent function, please see the proof of Lemma3 for detailed discussions.

  2. 2.

    The concept of crooked indifferentiability for random oracles was initially an extension of classical indifferentiability. We put the definition and properties of classical indifferentiability in Section A.1 of the full version [21].

References

  1. Bellare, M., Paterson, K.G., Rogaway, P.: Security of symmetric encryption against mass surveillance. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. Part I, volume 8616 of LNCS, pp. 1–19. Springer, Heidelberg (2014)

    Google Scholar 

  2. Bhattacharyya, R., Nandi, M., Raychaudhuri, A.: Crooked indifferentiability of enveloped xor revisited. In INDOCRYPT2021, 73–92 (2021)

    MathSciNet  Google Scholar 

  3. M. Blum. Designing programs that check their work, November 1988. Technical Report TR-88-009, International Computer Science Institure. Available athttp://www.icsi.berkeley.edu/pubs/techreports/tr-88-009.pdf

  4. M. Blum and S. Kannan. Designing programs that check their work. In21st ACM STOC, pages 86–97. ACM Press, May 1989

    Google Scholar 

  5. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In22nd ACM STOC, pages 73–83. ACM Press, May 1990

    Google Scholar 

  6. Chow, S.S.M., Russell, A., Tang, Q., Yung, M., Zhao, Y., Zhou, H.-S.: Let a non-barking watchdog bite: Cliptographic signatures with an offline watchdog. In: Lin, D., Sako, K. (eds.) PKC 2019. Part I, volume 11442 of LNCS, pp. 221–251. Springer, Heidelberg (2019)

    Google Scholar 

  7. Coretti, S., Dodis, Y., Guo, S., Steinberger, J.P.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I, volume 10820 of LNCS, pp. 227–258. Springer, Heidelberg, Apr. / (2018)

    Google Scholar 

  8. Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  9. Coron, J.-S., Holenstein, T., Künzler, R., Patarin, J., Seurin, Y., Tessaro, S.: How to build an ideal cipher: The indifferentiability of the Feistel construction. Journal of Cryptology29(1), 61–114 (2016)

    Article MathSciNet  Google Scholar 

  10. Dachman-Soled, D., Katz, J., Thiruvengadam, A.: 10-round Feistel is indifferentiable from an ideal cipher. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. Part II, volume 9666 of LNCS, pp. 649–678. Springer, Heidelberg (2016)

    Chapter  Google Scholar 

  11. Dai, Y., Steinberger, J.P.: Indifferentiability of 8-round Feistel networks. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. Part I, volume 9814 of LNCS, pp. 95–120. Springer, Heidelberg (2016)

    Chapter  Google Scholar 

  12. Dodis, Y., Ganesh, C., Golovnev, A., Juels, A., Ristenpart, T.: A formal treatment of backdoored pseudorandom generators. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. Part I, volume 9056 of LNCS, pp. 101–126. Springer, Heidelberg (2015)

    Chapter  Google Scholar 

  13. Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: Random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part II, volume 10211 of LNCS, pp. 473–495. Springer, Heidelberg, Apr. / (2017)

    Google Scholar 

  14. Dodis, Y., Puniya, P.: On the relation between the ideal cipher and the random oracle models. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 184–206. Springer, Heidelberg (2006)

    Google Scholar 

  15. Dodis, Y., Puniya, P.: Feistel networks made public, and applications. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 534–554. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  16. Maurer, U.M., 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)

    Google Scholar 

  17. Russell, A., Tang, Q., Yung, M., Zhou, H.-S.: Cliptography: Clipping the power of kleptographic attacks. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. Part II, volume 10032 of LNCS, pp. 34–64. Springer, Heidelberg (2016)

    Chapter  Google Scholar 

  18. Russell, A., Tang, Q., Yung, M., Zhou, H.-S.: Generic semantic security against a kleptographic adversary. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 907–922. ACM Press, Oct. / (2017)

    Google Scholar 

  19. Russell, A., Tang, Q., Yung, M., Zhou, H.-S.: Correcting subverted random oracles. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. Part II, volume 10992 of LNCS, pp. 241–271. Springer, Heidelberg (2018)

    Chapter  Google Scholar 

  20. A. Russell, Q. Tang, M. Yung, H.-S. Zhou, and J. Zhu. Correcting subverted random oracles, 2021.https://eprint.iacr.org/2021/042

  21. A. Russell, Q. Tang, and J. Zhu. Crooked indifferentiability of the feistel construction. Cryptology ePrint Archive, Paper 2024/1456, 2024

    Google Scholar 

  22. Tang, Q., Yung, M.: Cliptography: Post-snowden cryptography. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 2615–2616. ACM Press, Oct. / (2017)

    Google Scholar 

  23. Young, A., Yung, M.: The dark side of “black-box’’ cryptography, or: Should we trust capstone? In: Koblitz, N. (ed.) CRYPTO’96. LNCS, vol. 1109, pp. 89–103. Springer, Heidelberg (1996)

    Google Scholar 

  24. Young, A., Yung, M.: Kleptography: Using cryptography against cryptography. In: Fumy, W. (ed.) EUROCRYPT’97. LNCS, vol. 1233, pp. 62–74. Springer, Heidelberg (1997)

    Google Scholar 

Download references

Acknowledgements

We thank anonymous reviewers for valuable comments. Jiadong Zhu was supported in part by the National Natural Science Foundation of China Grants No. 62325210, 62272441.

Author information

Authors and Affiliations

  1. University of Connecticut, Storrs, USA

    Alexander Russell

  2. The University of Sydney, Sydney, Australia

    Qiang Tang

  3. State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China

    Jiadong Zhu

Authors
  1. Alexander Russell
  2. Qiang Tang
  3. Jiadong Zhu

Corresponding author

Correspondence toJiadong Zhu.

Editor information

Editors and Affiliations

  1. Academia Sinica, Taipei, Taiwan

    Kai-Min Chung

  2. NTT Social Informatics Laboratories, Tokyo, Japan

    Yu Sasaki

Rights and permissions

Copyright information

© 2025 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Russell, A., Tang, Q., Zhu, J. (2025). Crooked Indifferentiability of the Feistel Construction. In: Chung, KM., Sasaki, Y. (eds) Advances in Cryptology – ASIACRYPT 2024. ASIACRYPT 2024. Lecture Notes in Computer Science, vol 15489. Springer, Singapore. https://doi.org/10.1007/978-981-96-0938-3_14

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 8465
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • 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

[8]ページ先頭
©2009-2025 Movatter.jp