A lower bound for the distance between a bijunctive function and a function with the fixed algebraic immunity | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 4(34). DOI: 10.17223/20710410/34/3

Let / = /(x₁,... , X_n) be a bijunctive Boolean function, that is, the multiplication of some disjunctions of two variables or their negations, Lf = {i₁,..., i\_Lf |} с {1,..., n}, and, for y = (y₁,...,y|L_/1) S F2, the Boolean function /У ' obtained by substitution of y₁,..., y\_Lf \ instead of x^,..., Xj|_L | respectively into /(x₁,..., X_n) is not const and is equivalent relatively the Jevons group to the function d y,m, - * (Х1 V X2) · ... · (X2dy-1 V X2dy) · X2dy+1 · ... · X2dy+my, if 1 ^ dy ^ |_n/2j , 1 ^ m_y ^ n - 2d_y; x₁ · ... · X_m, if d_y = 0,1 ^ m_y ^ n; (X1 V X2) · ... · (X2dy-1 V X2dy), if 1 ^ dy ^ Ln/2J , my = 0. Let /₀ = /₀(x₁, ..., X_n) be a Boolean function with the algebraic immunity AI(/₀) satisfying the condition 1 < k = AI(/₀) - 2|Lf |, C = |{(y₁,..., y\_Lf\) S f2 1 : fy , 'i\bf' = const}|, d dist(f, f₀) is the Hamming distance between / and f₀. Then с E H) + E fet, H)+ = y€F2f ^ il.....< | L_f | =fy y y / _|r . ч + E E (2 (y)(-|Lf |-2dyy)) - p=0 j=2dy+m.y+p-fc+1 fy y fc-1-p , _л\ E E (2 ()(/pyy^ < dist (/, /0) . p=0 j=0 у In cryptography, functions like f₀ and / are widely used for solving systems of Boolean equations by respectively linearization and statistical approximation methods.