-
Previous Article
Trace description and Hamming weights of irreducible constacyclic codes
- AMC Home
- This Issue
-
Next Article
Singleton bounds for R-additive codes
Generalized nonlinearity of $ S$-boxes
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 |
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.
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. |
0.219 | 0.219 | 0.219 | 0.156 | 0.219 | 0.188 | 0.281 | 0.188 | ||
0.494 | 0.494 | 0.497 | 0.489 | 0.494 | 0.491 | 0.494 | 0.494 |
0.219 | 0.219 | 0.219 | 0.156 | 0.219 | 0.188 | 0.281 | 0.188 | ||
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
Other articles
by authors
[Back to Top]