Abstract
At Eurocrypt’18, Cid, Huang, Peyrin, Sasaki, and Song introduced a new tool called Boomerang Connectivity Table (BCT) for measuring the resistance of a block cipher against the boomerang attack which is an important cryptanalysis technique introduced by Wagner in 1999 against block ciphers. Next, Boura and Canteaut introduced an important parameter related to the BCT for cryptographic S-boxes called boomerang uniformity. The purpose of this paper is to present a brief state-of-the-art on the notion of boomerang uniformity of vectorial Boolean functions (or S-boxes) and provide new results. More specifically, we present a slightly different but more convenient formulation of the boomerang uniformity and prove some new identities. Moreover, we focus on quadratic permutations in even dimension and obtain general criteria by which they have optimal BCT. As a consequence of the new criteria, two previously known results can be derived, and many new quadratic permutations with optimal BCT (optimal means that the maximal value in the Boomerang Connectivity Table equals the lowest known differential uniformity) can be found. In particular, we show that the boomerang uniformity of the binomial differentially 4-uniform permutations presented by Bracken, Tan, and Tan equals 4. Furthermore, we show a link between the boomerang uniformity and the nonlinearity for some special quadratic permutations. Finally, we present a characterization of quadratic permutations with boomerang uniformity 4. With this characterization, we show that the boomerang uniformity of a quadratic permutation with boomerang uniformity 4 is preserved by the extended affine (EA) equivalence.
Similar content being viewed by others
References
Biham E., Shamir A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes A.J., Vanstone S.A. (eds.) CRYPTO’90, vol. 537, pp. 2–21. LNCSSpringer, Heidelberg (1991). August.
Biham E., Dunkelman O., Keller N.: The rectangle attack - rectangling the Serpent. In: Pfitzmann B. (ed.) EUROCRYPT 2001, vol. 2045, pp. 340–357. LNCSSpringer, Heidelberg (2001). May.
Biham E., Dunkelman O., Keller N.: New results on boomerang and rectangle attacks. In: Daemen J., Rijmen V. (eds.) FSE 2002, vol. 2365, pp. 1–16. LNCSSpringer, Heidelberg (2002). February.
Biryukov A., Khovratovich D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Matsui M. (ed.) ASIACRYPT 2009, vol. 5912, pp. 1–18. LNCSSpringer, Heidelberg (2009). December.
Biryukov A., De Cannière C., Dellkrantz G.: Cryptanalysis of SAFER++. In: Boneh D. (ed.) CRYPTO 2003, vol. 2729, pp. 195–211. LNCSSpringer, Heidelberg (2003). August.
Blondeau C., Canteaut A., Charpin P.: Differential properties of power functions. Int. J. Inf. Coding Theory 1(2), 149–170 (2010).
Boura C., Canteaut A.: On the boomerang uniformity of cryptographic sboxes. IACR Trans. Symmetric Cryptol. 2018(3), 290–310 (2018). Sep.
Boura, C., Perrin, L., Tian, S.: Boomerang uniformity of popular S-box constructions. In: Proceedings of The eleventh international workshop on coding and cryptograph (WCC) (2019)
Bracken C., Tan C.H., Tan Y.: Binomial differentially 4 uniform permutations with high nonlinearity. Finite Fields Appl. 18(3), 537–546 (2012).
Carlet C.: Boolean functions for cryptography and error correcting codes. In: Crama Y., Hammer P. (eds.) Chapter of the Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press, Cambridge (2010).
Carlet C.: Vectorial Boolean Functions for Cryptography. In: Crama Y., Hammer P. (eds.) Chapter of the Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 398–469. Cambridge University Press, Cambridge (2010).
Carlet C., Charpin P., Zinoviev V.: Codes, bent functions and permutations suitable For DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (1998).
Charpin P., Peng J.: New links between nonlinearity and differential uniformity. Finite Fields Their Appl. 56, 188–208 (2019).
Cid C., Huang T., Peyrin T., Sasaki Y., Song L.: Boomerang connectivity table: a new cryptanalysis tool. In: Nielsen J.B., Rijmen V. (eds.) Advances in Cryptology - EUROCRYPT 2018, pp. 683–714. Springer International Publishing, Cham (2018).
Dunkelman O., Keller N., Shamir A.: A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. In: Tal R. (ed.) CRYPTO 2010, volume 6223 of LNCS, pp. 393–410. Springer, Heidelberg (2010).
Gold R.: Maximal recursive sequences with 3-valued recursive cross-correlation functions. IEEE Trans. Inform. Theory 14(1), 154–156 (1968).
Kelsey, J., Kohno, T., Schneier, B.: Amplified boomerang attacks against reduced-round MARS and Serpent. In: Schneier, B. (ed) (2000)
Kim J., Hong S., Preneel B., Biham E., Dunkelman O., Keller N.: Related-key boomerang and rectangle attacks: theory and experimental analysis. IEEE Trans. Inf. Theory 58(7), 4948–4966 (2012).
Leander G., Poschmann A.: On the Classification of $4$ Bit S-Boxes. In: Carlet C., Sunar B. (eds.) WAIFI 2007, vol. 4547, pp. 159–176. LNCSSpringer, Heidelberg (2007). June.
Li K., Longjiang Q., Sun B., Li C.: New results about the boomerang uniformity of permutation polynomials. IEEE Trans. Inf. Theory 65(11), 7542–7553 (2019).
Nyberg K.: S-boxes and round functions with controllable linearity and differential uniformity. In: Preneel B. (ed.) FSE’94, vol. 1008, pp. 111–130. LNCSSpringer, Heidelberg (1995). December.
Shizhu T., Christina B., Léo Perrin: Boomerang uniformity of popular S-box constructions. IACR Cryptol. 2019, 1002 (2019).
Song, L., Qi, X., Hu, L.: Boomerang connectivity table revisited-application to SKINNY and AES. https://eprint.iacr.org/2019/146.pdf
Wagner D.: The boomerang attack. In: Knudsen L.R. (ed.) FSE’99, vol. 1636, pp. 156–170. LNCSSpringer, Heidelberg (1999). March.
Zieve, M.E.: Permutation polynomials induced from permutations of subfields, and some complete sets of mutually orthogonal latin squares. arXiv:1312.1325v3 (2013)
Acknowledgements
The authors thank the anonymous reviewers and the Associate Editor for their detailed comments that highly improved the presentation and the quality of this paper. They also thank Nian Li and Haode Yan for their interesting discussions in Hong Kong. C. Tang was supported by National Natural Science Foundation of China (Grant No. 11871058) and China West Normal University (Grant Nos. 14E013, CXTD2014-4 and the Meritocracy Research Funds). M. Xiong was supported by The Hong Kong Research Grants Council, Project No. N_HKUST619/17.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by O. Ahmadi.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Mesnager, S., Tang, C. & Xiong, M. On the boomerang uniformity of quadratic permutations. Des. Codes Cryptogr. 88, 2233–2246 (2020). https://doi.org/10.1007/s10623-020-00775-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-020-00775-2
Keywords
- Vectorial function
- S-box
- Block cipher
- Boomerang uniformity
- Boomerang Connectivity Table
- Boomerang attack
- Symmetric cryptography