A note on the fast algebraic immunity and its consequences on modified majority functions

Deng Tang

doi:10.3934/amc.2020009

Article Contents

2020, Volume 14, Issue 1: 111-125. Doi: 10.3934/amc.2020009

This issue Previous Article Two classes of differentially 4-uniform permutations over $ \mathbb{F}_{2^{n}} $ with $ n $ even Next Article Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations

A note on the fast algebraic immunity and its consequences on modified majority functions

Deng Tang^1,2,

1.
School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China
2.
Guangxi Key Laboratory of Cryptography and Information Security, Guilin 541000, China

Received: October 2018

Published: August 2019

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

Abstract

Boolean functions used as nonlinear filters and/or combiners in LFSR-based stream ciphers should satisfy several desired cryptographic properties simultaneously, to withstand all known cryptographic attacks. In the past decade, the algebraic and fast algebraic immunities are the most infusive criteria on the design of cryptographic Boolean functions, due to the high efficiency of the algebraic and fast algebraic attacks on stream ciphers. Up to now, Boolean functions with optimal algebraic immunity have been built in several ways, but there are not many known results on their fast algebraic immunities. In this paper, we first derive a relation on the fast algebraic immunity between a Boolean functionfand it’s modificationsf+s, which shows that iffhas low fast algebraic immunity and s has low algebraic immunity thenf+smay also have low fast algebraic immunity in general. Thanks to this relation, we obtain some upper bounds on the fast algebraic immunity of several known classes of modified majority functions.

Keywords:

Mathematics Subject Classification: Primary: 06E30, 94A60; Secondary: 11T71.

Citation:

Full Text(HTML)

Table 1. Upper bound on the fast algebraic immunity of $ f_m $

$ n $	4	5	8	9	10	11	16	17	18	19	20	21
Theorem 3.7	4	4	6	6	8	8	10	10	12	12	14	14
$ n $	22	23	32	33	34	35	36	37	38	39	40	41
Theorem 3.7	16	16	18	18	20	20	22	22	24	24	26	26
$ n $	42	43	44	45	46	47	64	65	66	67	68	69
Theorem 3.7	28	28	30	30	32	32	34	34	36	36	38	38
$ n $	70	71	72	73	74	75	76	77	78	79	80	81
Theorem 3.7	40	40	42	42	44	44	46	46	48	48	50	50
$ n $	82	83	84	85	86	87	88	89	90	91	92	93
Theorem 3.7	52	52	54	54	56	56	58	58	60	60	62	62
$ n $	94	95	128	129	130	131	132	133	134	135	136	137
Theorem 3.7	64	64	66	66	68	68	70	70	72	72	74	74
$ n $	138	139	140	141	142	143	144	145	146	147	148	149
Theorem 3.7	76	76	78	78	80	80	82	82	84	84	86	86

| Show Table

DownLoad: CSV

Table 2. Upper bounds on the fast algebraic immunity of modified majority functions

even $ n $	12-14	16	18	20	22	24-30	32	34	36	38	40	42	44
$ FAI(f_D) $	10	12	14	16	18	18	20	22	24	26	28	30	32
$ FAI(f_{C_1}) $	14	16	18	20	22	22	24	26	28	30	32	34	36
$ FAI(f_{C_2}) $	14	16	18	20	22	22	24	26	28	30	32	34	36
$ FAI(f_{C_3}) $	12	14	16	18	20	20	22	24	26	28	30	32	34
even $ n $	46	48-62	64	66	68	70	72	74	76	78	80	82	84
$ FAI(f_D) $	34	34	36	38	40	42	44	46	48	50	52	54	56
$ FAI(f_{C_1}) $	38	38	40	42	44	46	48	50	52	54	56	58	60
$ FAI(f_{C_2}) $	38	38	40	42	44	46	48	50	52	54	56	58	60
$ FAI(f_{C_3}) $	36	36	38	40	42	44	46	48	50	52	54	56	58
even $ n $	86	88	90	92	94	96-126	128	130	132	134	136	138	140
$ FAI(f_D) $	58	60	62	64	66	66	68	70	72	74	76	78	80
$ FAI(f_{C_1}) $	62	64	66	68	70	70	72	74	76	78	80	82	84
$ FAI(f_{C_2}) $	62	64	66	68	70	70	72	74	76	78	80	82	84
$ FAI(f_{C_3}) $	60	62	64	66	68	68	70	72	74	76	78	80	82
even $ n $	142	144	146	148	150	152	154	156	158	160	162	164	166
$ FAI(f_D) $	82	84	86	88	90	92	94	96	98	100	102	104	106
$ FAI(f_{C_1}) $	86	88	90	92	94	96	98	100	102	104	106	108	110
$ FAI(f_{C_2}) $	86	88	90	92	94	96	98	100	102	104	106	108	110
$ FAI(f_{C_3}) $	84	86	88	90	92	94	96	98	100	102	104	106	108
even $ n $	168	170	172	174	176	178	180	182	184	186	188	190	192-254
$ FAI(f_D) $	108	110	112	114	116	118	120	122	124	126	128	130	130
$ FAI(f_{C_1}) $	112	114	116	118	120	122	124	126	128	130	132	134	134
$ FAI(f_{C_2}) $	112	114	116	118	120	122	124	126	128	130	132	134	134
$ FAI(f_{C_3}) $	110	112	114	116	118	120	122	124	126	128	130	132	132

| Show Table

DownLoad: CSV

Table 3. Upper bounds on the fast algebraic immunity of $ f_S $

odd $ n $	13-15	17	19	21	23	25-31	33	35	37	39	41	43	45
$ FAI(f_S) $	12	14	16	18	20	20	22	24	26	28	30	32	34
odd $ n $	47	49-63	65	67	69	71	73	75	77	79	81	83	85
$ FAI(f_S) $	36	36	38	40	42	44	46	48	50	52	54	56	58
odd $ n $	87	89	91	93	95	97-127	129	131	133	135	137	139	141
$ FAI(f_S) $	60	62	64	66	68	68	70	72	74	76	78	80	82
odd $ n $	143	145	147	149	151	153	155	157	159	161	163	165	167
$ FAI(f_S) $	84	86	88	90	92	94	96	98	100	102	104	106	108
odd $ n $	169	171	173	175	177	179	181	183	185	187	189	191	193-255
$ FAI(f_S) $	110	112	114	116	118	120	122	124	126	128	130	132	132

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Armknecht, Improving fast algebraic attacks, Fast Software Encryption, 3017 (2004), 65-82. doi: 10.1007/978-3-540-25937-4_5.
[2]	F. Armknecht, C. Carlet, P. Gaborit, S. Künzli, W. Meier and O. Ruatta, Efficient computation of algebraic immunity for algebraic and fast algebraic attacks, in Advances in Cryptology-EUROCRYPT 2006, Springer, 4004 (2006), 147–164. doi: 10.1007/11761679_10.
[3]	A. Braeken and B. Preneel, On the algebraic immunity of symmetric Boolean functions, in Progress in Cryptology-INDOCRYPT 2005, Springer, 3797 (2005), 35–48. doi: 10.1007/11596219_4.
[4]	A. Braeken, Cryptographic Properties of Boolean Functions and S-Boxes, PhD thesis, Catholic University of Louvain, 2006.
[5]	A. Canteaut and M. Videau, Symmetric Boolean functions, IEEE Transactions on Information Theory, 51 (2005), 2791-2811. doi: 10.1109/TIT.2005.851743.
[6]	C. Carlet, On a weakness of the Tu-Deng function and its repair, IACR Cryptology EPrint Archive, Report 2009/606, URL http://eprint.iacr.org/2009/606.
[7]	C. Carlet and D. Tang, Enhanced Boolean functions suitable for the filter model of pseudo-random generator, Designs, Codes and Cryptography, 76 (2015), 571-587. doi: 10.1007/s10623-014-9978-9.
[8]	C. Carlet, X. Y. Zeng, C. L. Li and L. Hu, Further properties of several classes of Boolean functions with optimum algebraic immunity, Designs, Codes and Cryptography, 52 (2009), 303-338. doi: 10.1007/s10623-009-9284-0.
[9]	Y. Chen and P. Lu, Two classes of symmetric Boolean functions with optimum algebraic immunity: Construction and analysis, IEEE transactions on information theory, 57 (2011), 2522-2538. doi: 10.1109/TIT.2011.2111810.
[10]	N. T. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology-CRYPTO 2003, Springer, 2729 (2003), 176–194. doi: 10.1007/978-3-540-45146-4_11.
[11]	N. T. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology–EUROCRYPT 2003, Springer, 2656 (2003), 345–359. doi: 10.1007/3-540-39200-9_21.
[12]	D. K. Dalai, S. Maitra and S. Sarkar, Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Designs, Codes and Cryptography, 40 (2006), 41-58. doi: 10.1007/s10623-005-6300-x.
[13]	J. F. Dillon, Elementary Hadamard Difference Sets, PhD thesis, Univ. of Maryland, 1974,126 pp.
[14]	C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Lecture Notes in Computer Science, 561. Springer-Verlag, Berlin, 1991. doi: 10.1007/3-540-54973-0.
[15]	D. Dong, S. Fu, L. Qu and C. Li, A new construction of Boolean functions with maximum algebraic immunity, in Information Security, Springer, (2009), 177–185.
[16]	K. Q. Feng, F. Liu, L. J. Qu and L. Wang, Constructing symmetric Boolean functions with maximum algebraic immunity, IEEE Transactions on Information Theory, 55 (2009), 2406-2412. doi: 10.1109/TIT.2009.2015999.
[17]	S. Fu, C. Li, K. Matsuura and L. Qu, Construction of rotation symmetric Boolean functions with maximum algebraic immunity, in Cryptology and Network Security, Springer, (2009), 402–412.
[18]	S. Fu, L. Qu, C. Li and B. Sun, Balanced rotation symmetric Boolean functions with maximum algebraic immunity, IET Information Security, 5 (2011), 93-99. doi: 10.1049/iet-ifs.2010.0048.
[19]	P. Hawkes and G. G. Rose, Rewriting variables: The complexity of fast algebraic attacks on stream ciphers, in Advances in Cryptology–CRYPTO 2004, Springer, 3152 (2004), 390–406. doi: 10.1007/978-3-540-28628-8_24.
[20]	N. Li and W.-F. Qi, Construction and analysis of Boolean functions of $2t+1$ variables with maximum algebraic immunity, in Advances in Cryptology–ASIACRYPT 2006, Springer, 4284 (2006), 84–98. doi: 10.1007/11935230_6.
[21]	M. C. Liu and D. D. Lin, Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Trans. Inform. Theory, 57 (2011), 4817–4821, arXiv: 0910.4632. doi: 10.1109/TIT.2011.2145690.
[22]	M. C. Liu and D. D. Lin, Almost perfect algebraic immune functions with good nonlinearity, in 2014 IEEE International Symposium on Information Theory (ISIT), (2014), 1837–1841. doi: 10.1109/ISIT.2014.6875151.
[23]	M. C. Liu and D. D. Lin, Results on highly nonlinear boolean functions with provably good immunity to fast algebraic attacks, Information Sciences, 421 (2017), 181–203, URL http://www.sciencedirect.com/science/article/pii/S002002551730926X. doi: 10.1016/j.ins.2017.08.097.
[24]	M. C. Liu, D. D. Lin and D. Y. Pei, Fast algebraic attacks and decomposition of symmetric Boolean functions, IEEE Transactions on Information Theory, 57 (2011), 4817-4821. doi: 10.1109/TIT.2011.2145690.
[25]	M. C. Liu, Y. Zhang and D. D. Lin, Perfect algebraic immune functions, in Advances in Cryptology–ASIACRYPT 2012, Springer, 7658 (2012), 172–189. doi: 10.1007/978-3-642-34961-4_12.
[26]	M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, Report 2005/441, URL http://eprint.iacr.org/2005/441.
[27]	J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, 15 (1969), 122-127. doi: 10.1109/tit.1969.1054260.
[28]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Advances in Cryptology-EUROCRYPT 2004, Springer, 3027 (2004), 474–491. doi: 10.1007/978-3-540-24676-3_28.
[29]	W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, J. Cryptology, 1 (1989), 159-176. doi: 10.1007/BF02252874.
[30]	J. Peng, Q. S. Wu and H. B. Kan, On symmetric Boolean functions with high algebraic immunity on even number of variables, IEEE Transactions on Information Theory, 57 (2011), 7205-7220. doi: 10.1109/TIT.2011.2132113.
[31]	L. J. Qu, C. Li and K. Q. Feng, A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables, IEEE Transactions on Information Theory, 53 (2007), 2908-2910. doi: 10.1109/TIT.2007.901189.
[32]	S. Ronjom and T. Helleseth, A new attack on the filter generator, IEEE Transactions on Information Theory, 53 (2007), 1752-1758. doi: 10.1109/TIT.2007.894690.
[33]	S. Sarkar and S. Maitra, Construction of rotation symmetric Boolean functions on odd number of variables with maximum algebraic immunity, in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, 4851 (2007), 271–280. doi: 10.1007/978-3-540-77224-8_32.
[34]	T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Transactions on Computers, 34 (1985), 81-85. doi: 10.1109/TC.1985.1676518.
[35]	S. H. Su and X. H. Tang, Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Designs, Codes and Cryptography, 71 (2014), 183-199. doi: 10.1007/s10623-012-9727-x.
[36]	S. H. Su, X. H. Tang and X. Y. Zeng, A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed-Muller code, Designs, Codes and Cryptography, 72 (2014), 653-673. doi: 10.1007/s10623-013-9801-z.
[37]	D. Tang, C. Carlet and X. H. Tang, A class of 1-resilient Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, International Journal of Foundations of Computer Science, 25 (2014), 763–780, http://dx.doi.org/10.1142/S0129054114500324. doi: 10.1142/S0129054114500324.
[38]	D. Tang, C. Carlet, X. H. Tang and Z. C. Zhou, Construction of highly nonlinear 1-resilient Boolean functions with optimal algebraic immunity and provably high fast algebraic immunity, IEEE Transactions on Information Theory, 63 (2017), 6113-6125.
[39]	D. Tang, R. Luo and X. N. Du, The exact fast algebraic immunity of two subclasses of the majority function, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 99 (2016), 2084-2088. doi: 10.1587/transfun.E99.A.2084.
[40]	Q. C. Wang and T. Johansson, A note on fast algebraic attacks and higher order nonlinearities, in Information Security and Cryptology, Springer, 6584 (2010), 404–414. doi: 10.1007/978-3-642-21518-6_28.