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

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]

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]

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

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

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

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

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

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

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

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

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

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.

[12]

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

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

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

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[16]

Franziska Hinkelmann, Reinhard Laubenbacher. Boolean models of bistable biological systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1443-1456. doi: 10.3934/dcdss.2011.4.1443
[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]

Ferenc Szöllősi. On quaternary complex Hadamard matrices of small orders. Advances in Mathematics of Communications, 2011, 5 (2) : 309-315. doi: 10.3934/amc.2011.5.309
[20]

Joško Mandić, Tanja Vučičić. On the existence of Hadamard difference sets in groups of order 400. Advances in Mathematics of Communications, 2016, 10 (3) : 547-554. doi: 10.3934/amc.2016025

2017 Impact Factor: 0.564

Tools

Metrics

  • PDF downloads (49)
  • HTML views (113)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences