A note on the Signal-to-noise ratio of $ (n, m) $-functions

Yu Zhou; Xinfeng Dong; Yongzhuang Wei; Fengrong Zhang

doi:10.3934/amc.2020117

Article Contents

2022, Volume 16, Issue 2: 413-437. Doi: 10.3934/amc.2020117

This issue Previous Article Optimal strategies for CSIDH Next Article

A note on the Signal-to-noise ratio of $ (n, m) $-functions

1.
Science and Technology on Communication Security Laboratory, Chengdu 610041, China
2.
Center for Cyber Security, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
3.
Guilin University of Electronic Technology, Guilin 541004, China
4.
School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China

^* Corresponding author: Yu Zhou
^* Corresponding author: Yu Zhou

Received: May 31, 2019

Revised: February 29, 2020

Published: May 2022

Yu Zhou and Xinfeng Dong are supported in part by the National Key R & D Program of China (No. 2017YFB0802000, No. 2017YFB0802004), and in part by Sichuan Science and Technology Program (No. 2020JDJQ0076, 2021ZYD0011). Yongzhuang Wei is supported in part by the National Natural Science Foundation of China (No. 61370203), and in part by the Guangxi Science and Technology Foundation (Guike AB18281019, 2019GXNSFGA245004). Fengrong Zhang is supported in part by the Natural Science Foundation of China (61972400) and in part by the Jiangsu Natural Science Foundation (BK20181352)

Abstract Full Text(HTML) Figure(0) / Table(7) Related Papers Cited by

Abstract

The concept of the signal-to-noise ratio (SNR) as a useful measure indicator of the robustness of $ (n, m) $-functions $ F = (f_1, \ldots, f_m) $ (cryptographic S-boxes) against differential power analysis (DPA), has received extensive attention during the previous decade. In this paper, we give an upper bound on the SNR of balanced $ (n, m) $-functions, and a clear upper bound regarding unbalanced $ (n, m) $-functions. Moreover, we derive some deep relationships between the SNR of $ (n, m) $-functions and three other cryptographic parameters (the maximum value of the absolute value of the Walsh transform, the sum-of-squares indicator, and the nonlinearity of its coordinates), respectively. In particular, we give a trade-off between the SNR and the refined transparency order of $ (n, m) $-functions. Finally, we prove that the SNR of $ (n, m) $-functions is not affine invariant, and data experiments verify this result.

Addendum: The grant no. 2021ZYD0011 is added so it reads “Yu Zhou and Xinfeng Dong are supported in part by the National Key R & D Program of China (No. 2017YFB0802000, No. 2017YFB0802004), and in part by Sichuan Science and Technology Program (No. 2020JDJQ0076, 2021ZYD0011).” We apologize for any inconvenience this may cause.

Keywords:

Mathematics Subject Classification: 06E30, 94C10.

Citation:

Full Text(HTML)

Table 1. Walsh transform of $ f_i $

$ \alpha=(\gamma, \gamma_1, \gamma_2) $	$ (\gamma, 0, 0) $	$ (\gamma, 0, 1) $	$ (\gamma, 1, 0) $	$ (\gamma, 1, 1) $
$ \mathcal{F}(f_1\oplus \varphi_{\alpha}) $	$ 0 $	$ 0 $	$ 0 $	$ 2^2\cdot \mathcal{F}(g\oplus \varphi_{\gamma}) $
$ \mathcal{F}(f_2\oplus \varphi_{\alpha}) $	$ 0 $	$ 0 $	$ 2^2\cdot \mathcal{F}(g\oplus \varphi_{\gamma}) $	$ 0 $
$ \mathcal{F}(f_3\oplus \varphi_{\alpha}) $	$ 0 $	$ 2^2\cdot \mathcal{F}(g\oplus \varphi_{\gamma}) $	$ 0 $	$ 0 $
$ \mathcal{F}(f_4\oplus \varphi_{\alpha}) $	$ 2^2\cdot \mathcal{F}(g\oplus \varphi_{\gamma}) $	$ 0 $	$ 0 $	$ 0 $

| Show Table

DownLoad: CSV

Table 2. The signal-to-noise ratio bounds on S-boxes $ F = (f_1, \ldots, f_m) $

Ref.	$ SNR $	S-Box type
[11]	$ 1\leq SNR\leq 2^{n/2} $	Balanced S-Boxes
Theorem 15	$ SNR< 2^{n/2} $	Balanced S-Boxes
[11]	$ 1/m\leq SNR $	Unbalanced S-Boxes
Theorem 16	$ SNR\leq \frac{m\cdot \sqrt{2^{3n}}}{m\cdot 2^n+2H_F} $	Unbalanced S-Boxes
[11]	$ 2^{n/2}/q\lesssim SNR $	Bent S-Boxes
Corollary 1	$ SNR\leq \frac{2^{n}}{2^{n/2}-m+1} $	Bent S-Boxes
Corollary 2	$ SNR=m\sqrt{\frac{2^{3n}}{\sum_{i=1}^m\mathcal{V}(f_i)}} $	$ f_i $ and $ f_j $ are perfectly
		uncorrelated $ (1\leq i<j\leq m) $

| Show Table

DownLoad: CSV

Table 3. Distribution of the SNR of $ (4, 4) $ S-boxes

$ Class $	SNR(DPA)(F)$ _{(4, 4)} $	$ Number $	$ Per(\%) $
0	1.612137	1	0.33
1	1.663601	2	0.66
2	1.691253	9	2.98
3	1.705606	1	0.33
4	1.783290	1	0.33
5	1.976967	1	0.33
6	2.000000	1	0.33
7	2.023858	57	18.87
8	2.074252	14	4.64
9	2.128608	10	3.31
10	2.187475	43	14.24
11	2.218801	6	1.99
12	2.251512	4	1.32
13	2.398501	42	13.91
14	2.483682	29	9.60
15	2.529822	11	3.64
16	2.578633	16	5.30
17	2.685380	39	12.91
18	2.806586	6	1.99
19	2.945839	7	2.32
20	3.023716	1	0.33
21	3.108115	1	0.33

| Show Table

DownLoad: CSV

Table 4. The SNR of well known S-boxes

Name of algorithm	S-box	SNR(DPA)(S-box)$ _{(4, 4)} $
Lblock [22]	E9F0D4AB128376C5	2.945839
	4BE9FD0A7C562813	2.806586
	1E7CFD06B593248A	2.806586
	768B0F3E9ACD5241	2.945839
	E5F072CD1849BA63	2.945839
	2DBCFE097A631845	2.806586
	B94E0FAD6C573812	2.945839
	DAF0E49B218375C6	2.945839
	87E5FD06BC9A2413	2.806586
	B5F0729D481CEA36	2.945839
PRESENT [4]	C56B90AD3EF84712	2.128608
Piccolo [18]	E4B238091A7F6C5D	3.108115
SKINNY [3]	C6901A2B385D4E7F	2.685380
MANTIS [3]	CAD3EBF789150246	1.663601
Marvin [19]	021B83ED46F5C79A	3.023716
Midori [1]	CAD3EBF789150246	1.663601
	1053E2F7DA9BC846	2.128608
Gift [2]	1A4C6F392DB7508E	2.398501

| Show Table

DownLoad: CSV

Table 5. Representatives for all 16 classes of optimal $ (4, 4) $ S-boxes [14]

Class	$ (4, 4) $ S-boxes
$ G_0 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 11, 12, 9, 3, 14, 10, 5
$ G_1 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 11, 14, 3, 5, 9, 10, 12
$ G_2 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 11, 14, 3, 10, 12, 5, 9
$ G_3 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 12, 5, 3, 10, 14, 11, 9
$ G_4 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 12, 9, 11, 10, 14, 5, 3
$ G_5 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 12, 11, 9, 10, 14, 3, 5
$ G_6 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 12, 11, 9, 10, 14, 5, 3
$ G_7 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 12, 14, 11, 10, 9, 3, 5
$ G_8 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 9, 5, 10, 11, 3, 12
$ G_9 $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 11, 3, 5, 9, 10, 12
$ G_{10} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 11, 5, 10, 9, 3, 12
$ G_{11} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 11, 10, 5, 9, 12, 3
$ G_{12} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 11, 10, 9, 3, 12, 5
$ G_{13} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 12, 9, 5, 11, 10, 3
$ G_{14} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 12, 11, 3, 9, 5, 10
$ G_{15} $	0, 1, 2, 13, 4, 7, 15, 6, 8, 14, 12, 11, 9, 3, 10, 5

| Show Table

DownLoad: CSV

Table 6. The SNR of affine equivalent S-boxes of 16 optimal $ (4, 4) $ S-boxes

Class	SNR(DPA)($ G_i $)	$ RV $	$ DN $	Mean	Variance
$ G_0 $	2.945839	[1.600000, 3.108115]	22	2.457354	0.110006
$ G_1 $	2.685380	[1.600000, 3.108115]	22	2.456126	0.108045
$ G_2 $	2.685380	[1.600000, 3.108115]	22	2.456967	0.108855
$ G_3 $	2.685380	[1.612137, 3.108115]	15	2.466327	0.102287
$ G_4 $	3.108115	[1.612137, 3.108115]	17	2.466608	0.102820
$ G_5 $	3.108115	[1.612137, 3.108115]	17	2.466729	0.104456
$ G_6 $	3.108115	[1.612137, 3.108115]	17	2.465285	0.102089
$ G_7 $	2.806586	[1.612137, 3.108115]	16	2.478125	0.092405
$ G_8 $	2.945839	[1.612137, 3.108115]	22	2.456613	0.108452
$ G_9 $	2.685380	[1.612137, 3.108115]	22	2.453230	0.110267
$ G_{10} $	2.685380	[1.612137, 3.108115]	22	2.452648	0.109412
$ G_{11} $	2.685380	[1.612137, 3.108115]	17	2.464596	0.101206
$ G_{12} $	2.685380	[1.612137, 3.108115]	17	2.448995	0.106486
$ G_{13} $	2.945839	[1.612137, 3.108115]	17	2.481046	0.096809
$ G_{14} $	2.945839	[1.612137, 3.108115]	21	2.465687	0.099087
$ G_{15} $	2.945839	[1.600000, 3.108115]	21	2.466658	0.101133

| Show Table

DownLoad: CSV

Table 7. Distribution of the SNR of affine equivalent S-boxes of $ G_0 $

Class	SNR(DPA)($ A\circ G_0 $)	$ Number $	$ Per(\%) $
0	1.600000	48	0.238095
1	1.612137	120	0.595238
2	1.663601	192	0.952381
3	1.691253	312	1.547619
4	1.705606	336	1.666667
5	1.720331	144	0.714286
6	1.783290	72	0.357143
7	2.023858	792	3.928571
8	2.074252	696	3.452381
9	2.128608	624	3.095238
10	2.187475	1968	9.761905
11	2.218801	480	2.380962
12	2.251512	432	2.142857
13	2.398501	2328	11.547619
14	2.483682	912	4.523810
15	2.529822	2928	14.523810
16	2.578633	1368	6.785714
17	2.685380	3768	18.690476
18	2.806586	672	3.333333
19	2.945839	792	3.928571
20	3.023716	240	1.190476
21	3.108115	936	4.642857

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Banik, A. Bogdanov and T. Isobe, et al., Midori: A block cipher for low energy, in Advances in Cryptology - ASIACRYPT 2015. Part II, Lecture Notes in Comput. Sci., 9453, Springer, Heidelberg, 2015,411–436. doi: 10.1007/978-3-662-48800-3_17.
[2]	S. Banik, S. K. Pandey and T. Peyrin, et al., GIFT: A small present - Towards reaching the limit of lightweight encryption, in Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, 10529, Springer, Cham, 2017,321–345. doi: 10.1007/978-3-319-66787-4_16.
[3]	C. Beierle, J. Jean and S. Kölbl, et al., The SKINNY family of block ciphers and its low-latency variant MANTIS, in Advances in Cryptology - CRYPTO 2016. Part II, Lecture Notes in Comput. Sci., 9815, Springer, Berlin, 2016,123–153. doi: 10.1007/978-3-662-53008-5_5.
[4]	A. Bogdanov, L. R. Knudsen and G. Leander, et al., PRESENT: An ultra-lightweight block cipher, in Cryptographic Hardware and Embedded Systems - CHES 2007, Lecture Notes in Comput. Sci., 4727, Springer, 2007,450–466. doi: 10.1007/978-3-540-74735-2_31.
[5]	C. D. Cannière, Analysis and Design of Symmetric Encryption Algorithms, Ph.D thesis, Katholieke Universiteit Leuven, 2007.
[6]	C. Carlet, Boolean functions for cryptography and error-correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010,257-397. doi: 10.1017/CBO9780511780448.011.
[7]	C. Carlet, Vectorial Boolean functions for cryptography, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge University Press, 2010,398-470. doi: 10.1017/CBO9780511780448.012.
[8]	K. Chakraborty, S. Sarkar and S. Maitra, et al., Redefining the transparency order, Des. Codes Cryptogr., 82 (2017), 95-115. doi: 10.1007/s10623-016-0250-3.
[9]	Y. Fei, Q. Luo and A. A. Ding, A statistical model for DPA with novel algorithmic confusion analysis, in Cryptographic Hardware and Embedded Systems - CHES 2012, Lecture Notes in Computer Science, 7428, Springer, 2012,233–250. doi: 10.1007/978-3-642-33027-8_14.
[10]	W. Fischer, B. M. Gammel, O. Kniffler and J. Velten, Differential power analysis of stream ciphers, in Topics in Cryptology - CT-RSA 2007, Lecture Notes in Comput. Sci., 4377, Springer, Berlin, 2006,257–270. doi: 10.1007/11967668_17.
[11]	S. Guilley, P. Hoogvorst and R. Pacalet, Differential power analysis model and some results, in Smart Card Research and Advanced Applications VI, IFIP International Federation for Information Processing, 153, Springer, Boston, MA, 2004,127–142. doi: 10.1007/1-4020-8147-2_9.
[12]	A. Heuser, O. Rioul and S. Guilley, A theoretical study of Kolmogorov-Smirnov distinguishers - Side-channel analysis vs. differential cryptanalysis, in Constructive Side-Channel Analysis and Secure Design, Lecture Notes in Comput. Sci., 8622, Springer, 2014, 9–28. doi: 10.1007/978-3-319-10175-0_2.
[13]	P. Kocher, J. Jaffe and B. Jun, Differential power analysis, in Advances in Cryptology - CRYPTO'99, Lecture Notes in Comput. Sci., 1666, Springer, 1999,388–397. doi: 10.1007/3-540-48405-1_25.
[14]	G. Leander and A. Poschmann, On the classification of 4 bit S-boxes, in Arithmetic of Finite Fields, Lecture Notes in Comput. Sci., 4547, Springer, Berlin, 2007,159–176. doi: 10.1007/978-3-540-73074-3_13.
[15]	E. Pasalic, S. Maitra, T. Johansson and P. Sarkar, New constructions of resilient and correlation immune Boolean functions achieving upper bound on nonlinearity, in International Workshop on Coding and Cryptography, Electron. Notes Discrete Math., 6, Elsevier Sci. B. V., Amsterdam, 2001, 10pp. doi: 10.1016/S1571-0653(04)00167-2.
[16]	E. Prouff, DPA attacks and S-Boxes, in Fast Software Encryption, Lecture Notes in Comput. Sci., 3557, Springer, 2005,424–441. doi: 10.1007/11502760_29.
[17]	P. Sarkar and S. Maitra, Cross-correlation analysis of cryptographically useful Boolean functions and S-boxes, Theory Comput. Syst., 35 (2002), 39–57. doi: 10.1007/s00224-001-1019-1.
[18]	K. Shibutani, T. Isobe and H. Hiwatari, et al., Piccolo: An ultra-lightweight blockcipher, in Cryptographic Hardware and Embedded Systems - CHES 2011, Lecture Notes in Comput. Sci., 6917, Springer, 2011,342–357. doi: 10.1007/978-3-642-23951-9_23.
[19]	M. A. Simplicio Jr., P. D. F. F. S. Barbuda and P. S. L. M. Barreto, et al., The MARVIN message authentication code and the LETTERSOUP authenticated encryption scheme, Security Comm. Networks, 2 (2009), 165–180. doi: 10.1002/sec.66.
[20]	J. J. Son, J. I. Lim, S. Chee and S. H. Sung, Global avalanche characteristics and nonlinearity of balanced Boolean function, Inform. Process. Lett., 65 (1998), 139–144. doi: 10.1016/S0020-0190(98)00009-X.
[21]	Q. Wang and P. Stănică, Transparency order for Boolean functions: Analysis and construction, Des. Codes Cryptogr., 87 (2019), 2043–2059. doi: 10.1007/s10623-019-00604-1.
[22]	W. Wu and L. Zhang, LBlock: A lightweight block cipher, in Applied Cryptography and Network Security, Lecture Notes in Comput. Sci., 6715, Springer, 2011,327–344. doi: 10.1007/978-3-642-21554-4_19.
[23]	X.-M. Zhang and Y. Zheng, GAC–The criterion for global avalanche characteristics of cryptographic functions, J.UCS, 1 (1995), 320–337. doi: 10.1007/978-3-642-80350-5_30.
[24]	Y. Zheng and X.-M. Zhang, On plateaued functions, IEEE Trans. Inform. Theory, 47 (2001), 1215–1223. doi: 10.1109/18.915690.
[25]	Y. Zhou, L. Wang, W. Wang, X. Dong and X. Du, One sufficient and necessary condition on balanced Boolean functions with $\sigma_f = 2^2n+2^{n+3}(m\geq 3)$, Internat. J. Found. Comput. Sci., 25 (2014), 343–353. doi: 10.1142/S0129054114500178.
[26]	Y. Zhou, M. Xie and G. Xiao, On the global avalanche characteristics between two Boolean functions and the higher order nonlinearity, Inform. Sci., 180 (2010), 256–265. doi: 10.1016/j.ins.2009.09.012.
[27]	Y. Zhou, W. Zhang, S. Zhu and G. Xiao, The global avalanche characteristics of two Boolean functions and algebraic immunity, Int. J. Comput. Math., 89 (2012), 2165–2179. doi: 10.1080/00207160.2012.712689.