4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – SEJPM Apr 28 '16 at 22:38
7
$\begingroup$

Many properties of boolean functions are used in stream and block cipher design, e.g., when they are used as filtering and combining functions. Some important examples are:

  • Nonlinearity (minimal Hamming distance of the truth table of the boolean function from affine functions), must be high for resisting linear/affine approximation attacks.
  • 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.
  • There is a fantastic recent book on applications of boolean functions in cryptography, "Cryptographic Boolean Functions and Applications" by Stanica and Cusick. Older relevant books include "Analysis and Design of Stream Ciphers" by Rueppel and "Stability Theory of Stream Ciphers" by Ding, Shan and Xiao. Any issue of Designs, Codes and Cryptography, and quite a few Crypto conferences will regularly have papers on these topics. See the IACR eprint server as well.

Finally, Sboxes are just vectorial (vector output) boolean functions, see the chapter entitled Propagation and Correlation in the AES Proposal, a version of which also appears in the book "The Design of Rijndael" by Rijndael designers Daemen and Rijmen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.