# How are boolean functions used in cryptography?

I recently started becoming interested in Boolean functions. Because they are defined as $f: \{0, 1\}^n \rightarrow \{0, 1\}$, or in other words only over $\{0, 1\}$, I guessed they can somehow be applied in cryptography. After all in cryptography (in some sense) we have an input which can be defined as bits, and then we do some kind of operations on those bits to scramble them.

Additionally, many algorithms (like BLAKE, ChaCha20, etc.) use the ARX (addition-rotation-xor) method. And as long as I know some parts of AES does the same. I have already read that Boolean functions are important for the design of S-boxes, but I want to learn how more they are applied in cryptography.

So, how and where (hash functions, block ciphers, stream ciphers, public key cryptosystems, etc.) are the Boolean functions used in cryptography (either for designing algorithms or cryptanalysis)? Can they be used in some more complex algorithms that are based on things like finite field arithmetic, elliptic curves, lattices, etc?

• Actually I think the most common application of boolean functions would be multi-party computation (e.g. who has the largest (number)? do two parties have equal numbers?,...). But I'm not educated too much in this specific area so I'll leave it to others. – SEJPM Apr 28 '16 at 22:38

• Correlation Immunity (CI) and resilience (CI is the maximal nonzero weight for which all Walsh-Hadamard transform coefficients are nonzero, and quantifies resistance to divide and conquer style correlation attacks; resilience is CI plus balancedness). There is a tradeoff between CI and algebraic degree of the boolean function $f$, namely $deg(f)+CI\leq n-1$, for an $n$ variable boolean function, discovered by Xiao and Massey.
• There are links between weight of the complex DFT and linear complexity of sequences (and all sequences can be expressed as Boolean functions after a choice of basis of $GF(2^n)$ over $GF(2)$ and appending zero) called Blahut's theorem.