Basic theory in construction of Boolean functions with maximum possible annihilator immunity. (English) Zbl 1202.94179
Summary: So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with \(O(n^{2})\) time and \(O(n)\) space complexity.
Keywords:
algebraic attack; algebraic degree; algebraic immunity; annihilator; annihilator immunity; balancedness; Boolean functions; Krawtchouk polynomials; nonlinearity; symmetric Boolean functionsReferences:
| [1] | Armknecht F (2004). Improving fast algebraic attacks. In: FSE 2004, number 3017 in Lecture Notes in Computer Science, pp 65–82. Springer Verlag · Zbl 1079.68536 |
| [2] | Batten LM (2004). Algebraic attacks over GF(q). In: Progress in Cryptology – INDOCRYPT 2004, pp. 84–91, number 3348, Lecture Notes in Computer Science, Springer-Verlag · Zbl 1115.94005 |
| [3] | Botev A (2004). On algebraic immunity of some recursively given sequence of correlation immune functions. In: Proceedings of XV international workshop on Synthesis and complexity of control systems, Novosibirsk, October 18–23, 2004, pp 8–12 (in Russian) |
| [4] | Botev A (2004). On algebraic immunity of new constructions of filters with high nonlinearity. In: Proceedings of VI international conference on Discrete models in the theory of control systems, Moscow, December 7–11, 2004, pp 227–230 (in Russian). |
| [5] | Botev A, and Tarannikov Y (2004). Lower bounds on algebraic immunity for recursive constructions of nonlinear filters. Preprint. |
| [6] | Braeken A, Preneel B (2005). On the algebraic immunity of symmetric Boolean functions. Cryptology ePrint Archive, http://eprint.iacr.org/, No. 2005/245, 26 July, 2005 · Zbl 1153.94353 |
| [7] | Canteaut A (2005). Open problems related to algebraic attacks on stream ciphers. In: WCC 2005, pp 1–10, invited talk |
| [9] | Carlet C (2004). Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions. IACR ePrint server, http://eprint.iacr.org, 2004/276. |
| [10] | Carlet C, Gaborit P (2005). On the construction of balanced Boolean functions with a good algebraic immunity. In: First Workshop on Boolean Functions: Cryptography and Applications, BFCA 05, March 7–9, 2005, LIFAR, University of Rouen, France. |
| [11] | Cheon JH, Lee DH (2004). Resistance of S-boxes against Algebraic Attacks. In: FSE 2004, number 3017 in Lecture Notes in Computer Science, pp 83–94. Springer Verlag · Zbl 1079.68539 |
| [12] | Cho JY, Pieprzyk J (2004). Algebraic attacks on SOBER-t32 and SOBER-128. In: FSE 2004, number 3017 in Lecture Notes in Computer Science, pp 49–64. Springer Verlag · Zbl 1079.68540 |
| [13] | Constantine GM (1987). Combinatorial theory and statistical design. John Wiley & Sons · Zbl 0617.05002 |
| [14] | Courtois N, Pieprzyk J (2002). Cryptanalysis of block ciphers with overdefined systems of equations. In: Advances in Cryptology–ASIACRYPT 2002, number 2501 in Lecture Notes in Computer Science, pp 267–287. Springer Verlag · Zbl 1065.94543 |
| [15] | Courtois N, Meier W (2003). Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology–EUROCRYPT 2003, number 2656 in Lecture Notes in Computer Science, pp 345–359. Springer Verlag · Zbl 1038.94525 |
| [16] | Courtois N (2003). Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology–CRYPTO 2003, number 2729 in Lecture Notes in Computer Science, pp 176–194. Springer Verlag · Zbl 1122.94365 |
| [17] | Courtois N, Debraize B, Garrido E (2005). On exact algebraic [non-]immunity of S-boxes based on power functions. Cryptology ePrint Archive, http://eprint.iacr.org/, No. 2005/203, 28 June, 2005 · Zbl 1176.94036 |
| [18] | Dalai DK, Gupta KC, Maitra S (2004). Results on Algebraic immunity for cryptographically significant boolean functions. In: INDOCRYPT 2004, pp 92–106, number 3348, Lecture Notes in Computer Science, Springer-Verlag · Zbl 1115.94007 |
| [19] | Dalai DK, Gupta KC, Maitra S (2005). Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Fast Software Encryption, FSE 2005, pp 98–111, number 3557, Lecture Notes in Computer Science, Springer-Verlag · Zbl 1140.94334 |
| [20] | Dalai DK, Maitra S, Sarkar S (2005). Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Cryptology ePrint Archive, http://eprint.iacr.org/, No. 2005/229, 15 July, 2005. · Zbl 1202.94179 |
| [21] | Dillon JF (1974). Elementary Hadamard Difference sets. PhD Thesis, University of Maryland |
| [22] | Ding C, Xiao G, Shan W (1991). The stability theory of stream ciphers. Number 561 in Lecture Notes in Computer Science. Springer-Verlag |
| [24] | Lee DH, Kim J, Hong J, Han JW, Moon D (2004). Algebraic attacks on summation generators. In: FSE 2004, number 3017 in Lecture Notes in Computer Science, pp 34–48. Springer Verlag · Zbl 1079.68550 |
| [25] | MacWillams FJ, Sloane NJA (1977). The theory of error correcting codes. North Holland |
| [26] | Maitra S, (2000). Boolean functions with important cryptographic properties. PhD Thesis, Indian Statistical Institute · Zbl 1082.94529 |
| [28] | Meier W, Pasalic E, Carlet C (2004). Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology–EUROCRYPT 2004, number 3027 in Lecture Notes in Computer Science, pp 474–491. Springer Verlag · Zbl 1122.94041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
