• Previous Article
    Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations
  • AMC Home
  • This Issue
  • Next Article
    Two classes of differentially 4-uniform permutations over $ \mathbb{F}_{2^{n}} $ with $ n $ even
February  2020, 14(1): 111-125. doi: 10.3934/amc.2020009

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

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

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 function f and it’s modifications f + s, which shows that if f has low fast algebraic immunity and s has low algebraic immunity then f + s may 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.

Citation: Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009
References:
[1]

F. Armknecht, Improving fast algebraic attacks, Fast Software Encryption, 3017 (2004), 65-82. doi: 10.1007/978-3-540-25937-4_5. Google Scholar

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

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

[4]

A. Braeken, Cryptographic Properties of Boolean Functions and S-Boxes, PhD thesis, Catholic University of Louvain, 2006.Google Scholar

[5]

A. Canteaut and M. Videau, Symmetric Boolean functions, IEEE Transactions on Information Theory, 51 (2005), 2791-2811. doi: 10.1109/TIT.2005.851743. Google Scholar

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

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

[8]

C. CarletX. Y. ZengC. 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. Google Scholar

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

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

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

[12]

D. K. DalaiS. 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. Google Scholar

[13]

J. F. Dillon, Elementary Hadamard Difference Sets, PhD thesis, Univ. of Maryland, 1974,126 pp. Google Scholar

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

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

[16]

K. Q. FengF. LiuL. 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. Google Scholar

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

[18]

S. FuL. QuC. 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. Google Scholar

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

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

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

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

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

[24]

M. C. LiuD. 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. Google Scholar

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

[26]

M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, Report 2005/441, URL http://eprint.iacr.org/2005/441.Google Scholar

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

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

[29]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, J. Cryptology, 1 (1989), 159-176. doi: 10.1007/BF02252874. Google Scholar

[30]

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

[31]

L. J. QuC. 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. Google Scholar

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

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

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

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

[36]

S. H. SuX. 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. Google Scholar

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

[38]

D. TangC. CarletX. 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. Google Scholar

[39]

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

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

show all references

References:
[1]

F. Armknecht, Improving fast algebraic attacks, Fast Software Encryption, 3017 (2004), 65-82. doi: 10.1007/978-3-540-25937-4_5. Google Scholar

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

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

[4]

A. Braeken, Cryptographic Properties of Boolean Functions and S-Boxes, PhD thesis, Catholic University of Louvain, 2006.Google Scholar

[5]

A. Canteaut and M. Videau, Symmetric Boolean functions, IEEE Transactions on Information Theory, 51 (2005), 2791-2811. doi: 10.1109/TIT.2005.851743. Google Scholar

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

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

[8]

C. CarletX. Y. ZengC. 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. Google Scholar

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

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

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

[12]

D. K. DalaiS. 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. Google Scholar

[13]

J. F. Dillon, Elementary Hadamard Difference Sets, PhD thesis, Univ. of Maryland, 1974,126 pp. Google Scholar

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

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

[16]

K. Q. FengF. LiuL. 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. Google Scholar

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

[18]

S. FuL. QuC. 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. Google Scholar

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

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

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

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

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

[24]

M. C. LiuD. 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. Google Scholar

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

[26]

M. Lobanov, Tight bound between nonlinearity and algebraic immunity, IACR Cryptology ePrint Archive, Report 2005/441, URL http://eprint.iacr.org/2005/441.Google Scholar

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

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

[29]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, J. Cryptology, 1 (1989), 159-176. doi: 10.1007/BF02252874. Google Scholar

[30]

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

[31]

L. J. QuC. 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. Google Scholar

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

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

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

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

[36]

S. H. SuX. 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. Google Scholar

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

[38]

D. TangC. CarletX. 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. Google Scholar

[39]

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

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

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

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

[2]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

[3]

Marco Calderini. A note on some algebraic trapdoors for block ciphers. Advances in Mathematics of Communications, 2018, 12 (3) : 515-524. doi: 10.3934/amc.2018030

[4]

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

[5]

Jia Li. A malaria model with partial immunity in humans. Mathematical Biosciences & Engineering, 2008, 5 (4) : 789-801. doi: 10.3934/mbe.2008.5.789

[6]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[7]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[8]

Liman Dai, Xingfu Zou. Effects of superinfection and cost of immunity on host-parasite co-evolution. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 809-829. doi: 10.3934/dcdsb.2017040

[9]

Simeone Marino, Edoardo Beretta, Denise E. Kirschner. The role of delays in innate and adaptive immunity to intracellular bacterial infection. Mathematical Biosciences & Engineering, 2007, 4 (2) : 261-286. doi: 10.3934/mbe.2007.4.261

[10]

Siyu Liu, Xue Yang, Yingjie Bi, Yong Li. Dynamic behavior and optimal scheduling for mixed vaccination strategy with temporary immunity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1469-1483. doi: 10.3934/dcdsb.2018216

[11]

Tao Feng, Zhipeng Qiu, Xinzhu Meng. Dynamics of a stochastic hepatitis C virus system with host immunity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6367-6385. doi: 10.3934/dcdsb.2019143

[12]

Peter Haïssinsky, Kevin M. Pilgrim. An algebraic characterization of expanding Thurston maps. Journal of Modern Dynamics, 2012, 6 (4) : 451-476. doi: 10.3934/jmd.2012.6.451

[13]

Aihua Li. An algebraic approach to building interpolating polynomial. Conference Publications, 2005, 2005 (Special) : 597-604. doi: 10.3934/proc.2005.2005.597

[14]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[15]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[16]

Vu Hoang Linh, Volker Mehrmann. Spectral analysis for linear differential-algebraic equations. Conference Publications, 2011, 2011 (Special) : 991-1000. doi: 10.3934/proc.2011.2011.991

[17]

L. Yu. Glebsky and E. I. Gordon. On approximation of locally compact groups by finite algebraic systems. Electronic Research Announcements, 2004, 10: 21-28.

[18]

Feng Rong. Non-algebraic attractors on $\mathbf{P}^k$. Discrete & Continuous Dynamical Systems - A, 2012, 32 (3) : 977-989. doi: 10.3934/dcds.2012.32.977

[19]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[20]

B. Harbourne, P. Pokora, H. Tutaj-Gasińska. On integral Zariski decompositions of pseudoeffective divisors on algebraic surfaces. Electronic Research Announcements, 2015, 22: 103-108. doi: 10.3934/era.2015.22.103

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]