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.  Google Scholar

[2]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[14]

F. Macwilliams and N. Sloane, The theory of Error Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1977.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

V. Pless, R. Brualdi and W. Huffman, Handbook of Coding Theory, Elsevier Science Inc. New York, USA, 1998. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Y. Zheng and X. Zhang, Plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.  doi: 10.1109/18.915690.  Google Scholar

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.  Google Scholar

[2]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[14]

F. Macwilliams and N. Sloane, The theory of Error Correcting Codes, Amsterdam, The Netherlands: North-Holland, 1977.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

V. Pless, R. Brualdi and W. Huffman, Handbook of Coding Theory, Elsevier Science Inc. New York, USA, 1998. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

Y. Zheng and X. Zhang, Plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215-1223.  doi: 10.1109/18.915690.  Google Scholar

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012

[20]

Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete & Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (73)
  • HTML views (213)
  • Cited by (0)

Other articles
by authors

[Back to Top]