Differential uniformity and the associated codes of cryptographic functions

Pascale Charpin; Jie Peng

doi:10.3934/amc.2019036

Article Contents

2019, Volume 13, Issue 4: 579-600. Doi: 10.3934/amc.2019036

This issue Previous Article Some cryptanalytic and coding-theoretic applications of a soft stern algorithm Next Article A network reliability approach to the analysis of combinatorial repairable threshold schemes

Differential uniformity and the associated codes of cryptographic functions

Pascale Charpin^1, , and
Jie Peng^2,

1.
INRIA, 2 rue Simone Iff, Paris, France
2.
Mathematics and Science College of Shanghai Normal University, Shanghai, China

^* Corresponding author: Pascale Charpin
^* Corresponding author: Pascale Charpin

Received: October 2018

Revised: January 2019

Published: June 2019

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

The associated codes of almost perfect nonlinear (APN) functions have been widely studied. In this paper, we consider more generally the codes associated with functions that have differential uniformity at least $ 4 $. We emphasize, for such a function $ F $, the role of codewords of weight $ 3 $ and $ 4 $ and of some cosets of its associated code $ C_F $. We give some properties on codes associated with differential uniformity exactly $ 4 $. We obtain lower bounds and upper bounds for the numbers of codewords of weight less than $ 5 $ of the codes $ C_F $. We show that the nonlinearity of $ F $ decreases when these numbers increase. We obtain a precise expression to compute these numbers, when $ F $ is a plateaued or a differentially two-valued function. As an application, we propose a method to construct differentially $ 4 $-uniform functions, with a large number of $ 2 $-to-$ 1 $ derivatives, from APN functions.

Keywords:

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 14G50.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	T. Berger, A. Canteaut, P. Charpin and Y. Laigle-Chapuy, On almost perfect nonlinear functions over $F_2^n$, IEEE Trans. Inform. Theory, 52 (2006), 4160-4170. doi: 10.1109/TIT.2006.880036.
[2]	E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72. doi: 10.1007/BF00630563.
[3]	C. Blondeau, A. Canteaut and P. Charpin, Differential properties of power functions, Int. J. of Information and Coding Theory, 1 (2010), 149–170. Special Issue dedicated to Vera Pless. doi: 10.1504/IJICOT.2010.032132.
[4]	C. Blondeau, A. Canteaut and P. Charpin, Differential properties of $x\mapsto x^{2^t-1}$, IEEE Trans. Inform. Theory, 57 (2011), 8127-8137. doi: 10.1109/TIT.2011.2169129.
[5]	C. Bracken, E. Byrne, G. Mcguire and G. Nebe, On the equivalence of quadratic APN functions, Des. Codes Cryptogr., 61 (2011), 261-272. doi: 10.1007/s10623-010-9475-8.
[6]	A. Canteaut and L. Perrin, On CCZ-equivalence, extended-affine equivalence, and function twisting, Finite Fields Appl., 56 (2019), 209-246. doi: 10.1016/j.ffa.2018.11.008.
[7]	C. Carlet, Boolean and vectorial plateaued functions and apn functions, IEEE Trans. Inform. Theory, 61 (2015), 6272-6289. doi: 10.1109/TIT.2015.2481384.
[8]	C. Carlet, P. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156. doi: 10.1023/A:1008344232130.
[9]	C. Carlet and E. Prouff, On plateaued functions and their constructions, Fast Software Encryption-FSE'03 (Lecture Notes in Computer Science), T. Johansson (Ed.), Springer-Verlag, 2887 (2003), 54–73. doi: 10.1007/978-3-540-39887-5_6.
[10]	P. Charpin and G. Kyureghyan, On sets determining the differential spectrum of mappings, Int. J. of Information and Coding Theory, Special Issue on the honor of Gerard Cohen, 4 (2017), 170–184. doi: 10.1504/IJICOT.2017.083844.
[11]	P. Charpin and J. Peng, New links between nonlinearity and differential uniformity, Finite Fields Appl., 56 (2019), 188-208. doi: 10.1016/j.ffa.2018.12.001.
[12]	P. Charpin, A. Tiet$\ddot{a}$v$\ddot{a}$inen and V. Zinoviev, On binary cyclic codes with minimum distance $d = 3$, Problems of Information Transmission, 33 (1997), 287-296.
[13]	T. Cusick and H. Dobbertin, Some new three-valued crosscorrelation functions for binary m-sequences, IEEE Trans. Inform. Theory, 42 (1996), 1238-1240. doi: 10.1109/18.508848.
[14]	F. Macwilliams and N. Sloane, The theory of Error Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1977.
[15]	S. Mesnager, F. Ozbudak, A. Sinak and G. Cohen, On $q$-ary plateaued functions over $F_q$ and their explicit characterizations functions, European Journal of Combinatorics, 63 (2017), 6139-6148. doi: 10.1109/TIT.2017.2715804.
[16]	K. Nyberg, S-boxes and round functions with controllable linearity and differential uniformity, In Proc. of Fast Software Encryption-FSE'94 (Lecture Notes in Computer Science), Berlin, Germany: Springer-Verlag, 1008 (1994), 111–130. doi: 10.1007/3-540-60590-8_9.
[17]	V. Pless, R. Brualdi and W. Huffman, Handbook of Coding Theory, Elsevier Science Inc. New York, USA, 1998.
[18]	A. Pott, E. Pasalic, A. Muratovic-Ribic and S. Bajric, On the maximum number of bent components of vectorial functions, IEEE Trans. Inform. Theory, 64 (2018), 403-411. doi: 10.1109/TIT.2017.2749421.
[19]	M. Xiong, H. Yan and P. Yuan, On a conjecture of differentially $8$-uniform power functions, Des. Codes Cryptogr., 86 (2018), 1601-1621. doi: 10.1007/s10623-017-0416-7.
[20]	Y. Zheng and X. Zhang, Plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223. doi: 10.1109/18.915690.