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

Twin Column Parity Mixers and Gaston

A New Mixing Layer and Permutation

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2023 (CRYPTO 2023)

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

Included in the following conference series:

  • 1452 Accesses

Abstract

We introduce a new type of mixing layer for the round function of cryptographic permutations, called circulant twin column parity mixer (CPM), that is a generalization of the mixing layers in Keccak-\(f\) and Xoodoo. While these mixing layers have a bitwise differential branch number of 4 and a computational cost of 2 (bitwise) additions per bit, the circulant twin CPMs we build have a bitwise differential branch number of 12 at the expense of an increase in computational cost: depending on the dimension this ranges between 3 and 3.34 XORs per bit. Our circulant twin CPMs operate on a state in the form of a rectangular array and can serve as mixing layer in a round function that has as non-linear step a layer of S-boxes operating in parallel on the columns. When sandwiched between two ShiftRow-like mappings, we can obtain a columnwise branch number of 12 and hence it guarantees 12 active S-boxes per two rounds in differential trails. Remarkably, the linear branch numbers (bitwise and columnwise alike) of these mappings is only 4. However, we define the transpose of a circulant twin CPM that has linear branch number of 12 and a differential branch number of 4. We give a concrete instantiation of a permutation using such a mixing layer, named Gaston. It operates on a state of \(5 \times 64\) bits and uses \(\chi \) operating on columns for its non-linear layer. Most notably, the Gaston round function is lightweight in that it takes as few bitwise operations as the one of NIST lightweight standard Ascon. We show that the best 3-round differential and linear trails of Gaston have much higher weights than those of Ascon. Permutations like Gaston can be very competitive in applications that rely for their security exclusively on good differential properties, such as keyed hashing as in the compression phase of Farfalle.

R. H. Makarim—Independent Researcher.

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 79.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 99.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

References

  1. Barreto, P., Rijmen, V.: The WHIRLPOOL hashing function. Submitted to NESSIE, Sept 2000, revised May 2003. https://citeseerx.ist.psu.edu/document?repid=rep1 &type=pdf &doi=664b5286124b28abf2d30a07ba6f9e020f4138fe

  2. Beierle, C., Kranz, T., Leander, G.: Lightweight multiplication in \(GF(2^n)\) with applications to MDS matrices. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 625–653. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_23

    Chapter  MATH  Google Scholar 

  3. Bertoni, G., Daemen, J., Hoffert, S., Peeters, M., Van Assche, G., Van Keer, R.: Farfalle: parallel permutation-based cryptography. IACR Trans. Symmetric Cryptol. 2017(4), 1–38 (2017). https://tosc.iacr.org/index.php/ToSC/article/view/801

  4. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge functions. Ecrypt Hash Workshop 2007 (2007)

    Google Scholar 

  5. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak reference (2011). https://keccak.team/papers.html

  6. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Permutation-based encryption, authentication and authenticated encryption. In: Directions in Authenticated Ciphers (2012)

    Google Scholar 

  7. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-38424-3_1

    Chapter  Google Scholar 

  8. Bordes, N., Daemen, J., Kuijsters, D., Van Assche, G.: Thinking outside the Superbox. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 337–367. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_12

    Chapter  Google Scholar 

  9. Canteaut, A., et al.: Saturnin: a suite of lightweight symmetric algorithms for post-quantum security. IACR Trans. Symmetric Cryptol. 2020(S1), 160–207 (2020). https://doi.org/10.13154/tosc.v2020.iS1.160-207

  10. Cui, T., Grassi, L.: Algebraic key-recovery attacks on reduced-round Xoofff. In: Dunkelman, O., Jacobson, Jr., M.J., O’Flynn, C. (eds.) SAC 2020. LNCS, vol. 12804, pp. 171–197. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-81652-0_7

    Chapter  Google Scholar 

  11. Daemen, J., Hoffert, S., Van Assche, G., Van Keer, R.: The design of Xoodoo and Xoofff. IACR Trans. Symmetric Cryptol. 2018(4), 1–38 (2018). https://tosc.iacr.org/index.php/ToSC/article/view/7359

  12. 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

  13. Daemen, J.: Cipher and hash function design, strategies based on linear and differential cryptanalysis, Ph D. Thesis, K.U.Leuven (1995). http://jda.noekeon.org/

  14. Daemen, J., Mella, S., Van Assche, G.: Tighter trail bounds for Xoodoo. IACR Cryptol. ePrint Arch, p. 1088 (2022). https://eprint.iacr.org/2022/1088

  15. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2. submission to NIST Lightweight Cryptography Standardization Process (round 2) (2019). https://ascon.iaik.tugraz.at/

  16. Dobraunig, C., Eichlseder, M., Mendel, F., Schläffer, M.: Ascon v1.2: lightweight authenticated encryption and hashing. J. Cryptol. 34(3), 1–42 (2021). https://doi.org/10.1007/s00145-021-09398-9

    Article  MathSciNet  MATH  Google Scholar 

  17. Duval, S., Leurent, G.: MDS matrices with lightweight circuits. IACR Trans. Symmetric Cryptol. 2018(2), 48–78 (2018). https://doi.org/10.13154/tosc.v2018.i2.48-78

  18. El Hirch, S., Mella, S., Mehrdad, A., Daemen, J.: Improved differential and linear trail bounds for ASCON. IACR Trans. Symmetric Cryptol. 2022(4), 145–178 (2022). https://doi.org/10.46586/tosc.v2022.i4.145-178

  19. Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. In: Imai, H., Rivest, R.L., Matsumoto, T. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 210–224. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57332-1_17

    Chapter  Google Scholar 

  20. Fuchs, J., Rotella, Y., Daemen, J.: On the security of keyed hashing based on an unkeyed block function. IACR Cryptol. ePrint Arch, p. 1172 (2022). https://eprint.iacr.org/2022/1172

  21. Guo, J., Peyrin, T., Poschmann, A.: The PHOTON family of lightweight hash functions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 222–239. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_13

    Chapter  Google Scholar 

  22. Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED block cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_22

    Chapter  Google Scholar 

  23. Kranz, T., Leander, G., Stoffelen, K., Wiemer, F.: Shorter linear straight-line programs for MDS matrices. IACR Trans. Symmetric Cryptol. 2017(4), 188–211 (2017). https://doi.org/10.13154/tosc.v2017.i4.188-211

  24. Li, C., Wang, Q.: Design of lightweight linear diffusion layers from near-MDS matrices. IACR Trans. Symmetric Cryptol. 2017(1), 129–155 (2017). https://doi.org/10.13154/tosc.v2017.i1.129-155

  25. Li, S., Sun, S., Shi, D., Li, C., Hu, L.: Lightweight iterative MDS matrices: How small can we go? IACR Trans. Symmetric Cryptol. 2019(4), 147–170 (2019). https://doi.org/10.13154/tosc.v2019.i4.147-170

  26. Li, Y., Wang, M.: On the construction of lightweight circulant involutory MDS matrices. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 121–139. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_7

    Chapter  Google Scholar 

  27. Liu, M., Sim, S.M.: Lightweight MDS generalized circulant matrices. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 101–120. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_6

    Chapter  Google Scholar 

  28. Makarim, R.H., Rohit, R.: Towards tight differential bounds of Ascon: a hybrid usage of SMT and MILP. IACR Trans. Symmetric Cryptol. 2022(3), 303–340 (2022). https://doi.org/10.46586/tosc.v2022.i3.303-340

  29. Matsui, M., Yamagishi, A.: A new method for known plaintext attack of FEAL cipher. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 81–91. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_7

    Chapter  Google Scholar 

  30. Mella, S., Daemen, J., Van Assche, G.: New techniques for trail bounds and application to differential trails in Keccak. IACR Trans. Symmetric Cryptol. 2017(1), 329–357 (2017)

    Article  Google Scholar 

  31. National Institute of Standards and Technology: Lightweight Cryptography (LWC) Standardization project (2019). https://csrc.nist.gov/projects/lightweight-cryptography

  32. Rijmen, V., Daemen, J., Preneel, B., Bosselaers, A., De Win, E.: The cipher SHARK. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 99–111. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-60865-6_47

    Chapter  Google Scholar 

  33. Sim, S.M., Khoo, K., Oggier, F., Peyrin, T.: Lightweight MDS involution matrices. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 471–493. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_23

    Chapter  Google Scholar 

  34. Stoffelen, K., Daemen, J.: Column parity mixers. IACR Trans. Symmetric Cryptol. 2018(1), 126–159 (2018). https://doi.org/10.13154/tosc.v2018.i1.126-159

  35. Venkateswarlu, A., Kesarwani, A., Sarkar, S.: On the lower bound of cost of MDS matrices. IACR Trans. Symmetric Cryptol. 2022(4), 266–290 (2022). https://doi.org/10.46586/tosc.v2022.i4.266-290

Download references

Acknowledgements

Solane El Hirch is supported by the Cryptography Research Center of the Technology Innovation Institute (TII), Abu Dhabi (UAE), under the TII-Radboud project with title Evaluation and Implementation of Lightweight Cryptographic Primitives and Protocols. Joan Daemen is supported by the European Research Council under the ERC advanced grant agreement under grant ERC-2017-ADG Nr. 788980 ESCADA. Rusydi H. Makarim did this work while he was at the Cryptography Research Center of the Technology Innovation Institute (TII), Abu Dhabi (UAE). We would also like to thank the reviewers of CRYPTO 2023 and our shepherd Bart Preneel for their insightful suggestions which helped us in significantly improving the quality of paper.

Author information

Authors and Affiliations

  1. Radboud University, Nijmegen, The Netherlands

    Solane El Hirch & Joan Daemen

  2. Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE

    Raghvendra Rohit

  3. Jakarta, Indonesia

    Rusydi H. Makarim

Authors
  1. Solane El Hirch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joan Daemen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raghvendra Rohit
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rusydi H. Makarim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Solane El Hirch .

Editor information

Editors and Affiliations

  1. Rambus Inc., San Jose, CA, USA

    Helena Handschuh

  2. Brown University, Providence, RI, USA

    Anna Lysyanskaya

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

El Hirch, S., Daemen, J., Rohit, R., Makarim, R.H. (2023). Twin Column Parity Mixers and Gaston. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14083. Springer, Cham. https://doi.org/10.1007/978-3-031-38548-3_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-38548-3_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-38547-6

  • Online ISBN: 978-3-031-38548-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation