"cardinalities" - 1 õppematerjal

Boolean Functions and their Cryptographic Criteria

2𝑛 , 𝑢 = 0 𝑛 𝑥∈𝔽 𝑛2 Proof. Firstly, we can easily see that if 𝑢 = 0 𝑛 , then all summands are 1 and the sum is 2𝑛 . Now, if 𝑢 ≠ 0 𝑛 , we can look at two sets𝐴 = {𝑥 ∈ 𝔽 𝑛2 ∶ < 𝑥, 𝑢 > = 0 } and 𝐴′ = {𝑥 ∈ 𝔽 𝑛2 ∶ < 𝑥, 𝑢 > = 1 }. Obviously, those sets belong to 𝔽𝑛2 and their cardinalities are the same 2𝑛−1 . Since for any 𝑥 ∈ 𝐴 , the summand is 1 and for any 𝑥 ∈ 𝐴 , the summand is −1, we get the equation. ∎ If and only if the function is balanced the weight of a Boolean function can be expressed though it’s Walsh transform: 1 𝑤𝑡(𝑓) = 2𝑛−1 − 𝑊𝑓 (0𝑛 ) 2 Lemma 3.2