November  2019, 13(4): 579-600. doi: 10.3934/amc.2019036

Differential uniformity and the associated codes of cryptographic functions

1. 

INRIA, 2 rue Simone Iff, Paris, France

2. 

Mathematics and Science College of Shanghai Normal University, Shanghai, China

* Corresponding author: Pascale Charpin

Received  October 2018 Revised  January 2019 Published  June 2019

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.

Citation: Pascale Charpin, Jie Peng. Differential uniformity and the associated codes of cryptographic functions. Advances in Mathematics of Communications, 2019, 13 (4) : 579-600. doi: 10.3934/amc.2019036
References:
[1]

T. BergerA. CanteautP. 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. BlondeauA. 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. BrackenE. ByrneG. 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. CarletP. 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. CharpinA. 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. MesnagerF. OzbudakA. 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. PottE. PasalicA. 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. XiongH. 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.

show all references

References:
[1]

T. BergerA. CanteautP. 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. BlondeauA. 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. BrackenE. ByrneG. 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. CarletP. 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. CharpinA. 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. MesnagerF. OzbudakA. 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. PottE. PasalicA. 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. XiongH. 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.

[1]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[2]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete and Continuous Dynamical Systems, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[3]

Ábel Garab. Unique periodic orbits of a delay differential equation with piecewise linear feedback function. Discrete and Continuous Dynamical Systems, 2013, 33 (6) : 2369-2387. doi: 10.3934/dcds.2013.33.2369

[4]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33

[5]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete and Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939

[6]

Bai-Ni Guo, Feng Qi. Properties and applications of a function involving exponential functions. Communications on Pure and Applied Analysis, 2009, 8 (4) : 1231-1249. doi: 10.3934/cpaa.2009.8.1231

[7]

Piermarco Cannarsa, Peter R. Wolenski. Semiconcavity of the value function for a class of differential inclusions. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 453-466. doi: 10.3934/dcds.2011.29.453

[8]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[9]

H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181

[10]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

[11]

Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42.

[12]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete and Continuous Dynamical Systems, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

[13]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control and Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012

[14]

Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289

[15]

Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control and Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

[16]

Welington Cordeiro, Manfred Denker, Michiko Yuri. A note on specification for iterated function systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3475-3485. doi: 10.3934/dcdsb.2015.20.3475

[17]

Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control and Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167

[18]

Todd Kapitula, Björn Sandstede. Eigenvalues and resonances using the Evans function. Discrete and Continuous Dynamical Systems, 2004, 10 (4) : 857-869. doi: 10.3934/dcds.2004.10.857

[19]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure and Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569

[20]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (279)
  • HTML views (293)
  • Cited by (2)

Other articles
by authors

[Back to Top]