American Institute of Mathematical Sciences

Advanced
February  2018, 12(1): 115-122. doi: 10.3934/amc.2018007

Generalized nonlinearity of $ S$-boxes

Sugata Gangopadhyay 1, , Goutam Paul 2,, , Nishant Sinha 1, and  Pantelimon Stǎnicǎ 3,

1. 

Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee 247667, India
2. 

Cryptology and Security Research Unit, R. C. Bose Centre for Cryptology and Security, Indian Statistical Institute, Kolkata 700108, India
3. 

Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943-5216, USA

* Corresponding author: Goutam Paul

Nishant Sinha thanks IIT Roorkee for supporting his research

Received  September 2016 Published  March 2018

While analyzing $ S$-boxes, or vectorial Boolean functions, it is of interest to approximate its component functions by affine functions. In the usual attack models, it is assumed that all input vectors to an $ S$-box are equiprobable. The nonlinearity of an $ S$-box is defined, subject to this assumption. In this paper, we explore the possibility of linear cryptanalysis of an $ S$-box by introducing biased inputs and thus propose a generalized notion of nonlinearity along with a generalization of the Walsh-Hadamard spectrum of an $ S$-box.

Keywords: Nonlinearity, S-box, vectorial Boolean function, Walsh-Hadamard transform.
Mathematics Subject Classification: Primary: 06E30, 11T71; Secondary: 94A60.
Citation: Sugata Gangopadhyay, Goutam Paul, Nishant Sinha, Pantelimon Stǎnicǎ. Generalized nonlinearity of $ S$-boxes. Advances in Mathematics of Communications, 2018, 12 (1) : 115-122. doi: 10.3934/amc.2018007
References:
[1]

P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61. 

[2]

E. Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. AMS, 124 (1996), 2293-3002. 

[3]

S. Gangopadhyay, A. Kar Gangopadhyay, S. Pollatos and P. Stǎnicǎ, Cryptographic Boolean functions with biased inputs, Crypt. Commun. Discrete Struct. Seq., 9 (2017), 301-314. 

[4]

Y. Lu and Y. Desmedt, Bias analysis of a certain problem with applications to E0 and Shannon ciper, in ICISC 2010, 2011, 16-28.

[5]

M. Matsui, Linear cryptanalysis method for DES cipher, in EUROCRYPT'93, Springer, 1994,386-397.

[6]

R. O'Donnell, Analysis of Boolean Functions, Cambridge Univ. Press, 2014.

[7]

M. G. Parker, Generalised S-box nonlinearity, NESSIE Public Document, 11. 02. 03: NES/DOC/UIB/WP5/020/A.

[8]

D. R. Stinson, Cryptography: Theory and Practice, 3rd Edition, Chapman and Hall/CRC, 2005.

show all references

Nishant Sinha thanks IIT Roorkee for supporting his research

References:
[1]

P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61. 

[2]

E. Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. AMS, 124 (1996), 2293-3002. 

[3]

S. Gangopadhyay, A. Kar Gangopadhyay, S. Pollatos and P. Stǎnicǎ, Cryptographic Boolean functions with biased inputs, Crypt. Commun. Discrete Struct. Seq., 9 (2017), 301-314. 

[4]

Y. Lu and Y. Desmedt, Bias analysis of a certain problem with applications to E0 and Shannon ciper, in ICISC 2010, 2011, 16-28.

[5]

M. Matsui, Linear cryptanalysis method for DES cipher, in EUROCRYPT'93, Springer, 1994,386-397.

[6]

R. O'Donnell, Analysis of Boolean Functions, Cambridge Univ. Press, 2014.

[7]

M. G. Parker, Generalised S-box nonlinearity, NESSIE Public Document, 11. 02. 03: NES/DOC/UIB/WP5/020/A.

[8]

D. R. Stinson, Cryptography: Theory and Practice, 3rd Edition, Chapman and Hall/CRC, 2005.

Table 1.  Maximum bias without and with biased inputs for all DES S-boxes.
$F$ $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ $S_7$ $S_8$
$\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n}\epsilon({\bf{u}}, {\bf{v}} \cdot F)$ 0.219 0.219 0.219 0.156 0.219 0.188 0.281 0.188
$\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n} \epsilon^{(p)}_{{\mathcal{S}}}({\bf{u}}, {\bf{v}}\cdot F)$ 0.494 0.494 0.497 0.489 0.494 0.491 0.494 0.494
Table Options

Download as excel

$F$ $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ $S_7$ $S_8$
$\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n}\epsilon({\bf{u}}, {\bf{v}} \cdot F)$ 0.219 0.219 0.219 0.156 0.219 0.188 0.281 0.188
$\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n} \epsilon^{(p)}_{{\mathcal{S}}}({\bf{u}}, {\bf{v}}\cdot F)$ 0.494 0.494 0.497 0.489 0.494 0.491 0.494 0.494
[1]

Tingting Pang, Nian Li, Li Zhang, Xiangyong Zeng. Several new classes of (balanced) Boolean functions with few Walsh transform values. Advances in Mathematics of Communications, 2021, 15 (4) : 757-775. doi: 10.3934/amc.2020095
[2]

Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
[3]

Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013
[4]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010
[5]

Michel C. Delfour. Hadamard Semidifferential, Oriented Distance Function, and some Applications. Communications on Pure and Applied Analysis, 2022, 21 (6) : 1917-1951. doi: 10.3934/cpaa.2021076
[6]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[7]

Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems and Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721
[8]

Na Zhao, Zheng-Hai Huang. A nonmonotone smoothing Newton algorithm for solving box constrained variational inequalities with a $P_0$ function. Journal of Industrial and Management Optimization, 2011, 7 (2) : 467-482. doi: 10.3934/jimo.2011.7.467
[9]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056
[10]

Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[11]

Agnieszka Badeńska. No entire function with real multipliers in class $\mathcal{S}$. Discrete and Continuous Dynamical Systems, 2013, 33 (8) : 3321-3327. doi: 10.3934/dcds.2013.33.3321
[12]

Peter Bella, Arianna Giunti. Green's function for elliptic systems: Moment bounds. Networks and Heterogeneous Media, 2018, 13 (1) : 155-176. doi: 10.3934/nhm.2018007
[13]

Virginia Agostiniani, Rolando Magnanini. Symmetries in an overdetermined problem for the Green's function. Discrete and Continuous Dynamical Systems - S, 2011, 4 (4) : 791-800. doi: 10.3934/dcdss.2011.4.791
[14]

Alfonso Sorrentino. Computing Mather's $\beta$-function for Birkhoff billiards. Discrete and Continuous Dynamical Systems, 2015, 35 (10) : 5055-5082. doi: 10.3934/dcds.2015.35.5055
[15]

Sungwon Cho. Alternative proof for the existence of Green's function. Communications on Pure and Applied Analysis, 2011, 10 (4) : 1307-1314. doi: 10.3934/cpaa.2011.10.1307
[16]

Jagmohan Tyagi, Ram Baran Verma. Positive solution to extremal Pucci's equations with singular and gradient nonlinearity. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2637-2659. doi: 10.3934/dcds.2019110
[17]

Dmitry Jakobson and Iosif Polterovich. Lower bounds for the spectral function and for the remainder in local Weyl's law on manifolds. Electronic Research Announcements, 2005, 11: 71-77.

[18]

Shengxin Zhu. Summation of Gaussian shifts as Jacobi's third Theta function. Mathematical Foundations of Computing, 2020, 3 (3) : 157-163. doi: 10.3934/mfc.2020015
[19]

Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209
[20]

Yi Ming Zou. Dynamics of boolean networks. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (324)
  • HTML views (168)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy