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

[2]

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

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

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

[5]

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

[6]

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

[7]

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

[8]

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

show all references

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

[2]

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

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

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

[5]

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

[6]

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

[7]

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

[8]

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

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]

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
[2]

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
[3]

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
[4]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stăniă. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020056
[5]

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

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

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

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

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

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

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

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

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.

[14]

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
[15]

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

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[17]

Jeremiah Birrell. A posteriori error bounds for two point boundary value problems: A green's function approach. Journal of Computational Dynamics, 2015, 2 (2) : 143-164. doi: 10.3934/jcd.2015001
[18]

Wen-ming He, Jun-zhi Cui. The estimate of the multi-scale homogenization method for Green's function on Sobolev space $W^{1,q}(\Omega)$. Communications on Pure & Applied Analysis, 2012, 11 (2) : 501-516. doi: 10.3934/cpaa.2012.11.501
[19]

Hasib Khan, Cemil Tunc, Aziz Khan. Green function's properties and existence theorems for nonlinear singular-delay-fractional differential equations. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020139
[20]

Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (72)
  • HTML views (117)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences