{"id":210,"date":"2016-06-30T05:49:22","date_gmt":"2016-06-30T05:49:22","guid":{"rendered":"http:\/\/konukoii.com\/blog\/?p=210"},"modified":"2016-06-30T05:49:22","modified_gmt":"2016-06-30T05:49:22","slug":"calculating-nonlinearity-of-boolean-functions-with-walsh-hadamard-transform","status":"publish","type":"post","link":"https:\/\/konukoii.com\/blog\/2016\/06\/30\/calculating-nonlinearity-of-boolean-functions-with-walsh-hadamard-transform\/","title":{"rendered":"Calculating Nonlinearity of Boolean Functions with Walsh-Hadamard Transform"},"content":{"rendered":"Reading Time: <\/span> 2<\/span> minutes<\/span><\/span>

It was during Winter 2016 that I took an extremely interesting course on Computational Algebra. This course was solely devoted to analyzing topics that ranged from cryptography to error-resistant functions. Among the many topics, one that stood out for me was LFSRs (Linear Feedback Shift Registers).<\/p>\n

LFSRs\u00a0are simple circuits that use their internal state to calculate a linear function. The output of the function is then fed into the circuit's new state, and the cycle continues. Perhaps that sounds a bit to abstract right now. The truth is that I will most likely write about them in the weeks to come. (Because they are fascinating!). Wikipedia has a nice little animation that shows one in action:<\/p>\n

LFSR in Action - Source: Cuddlyable3 @ wikipedia.com\u00a0<\/figcaption><\/figure>\n

However, this article is not about LFSRs, but rather something even more fundamental: Boolean Functions.<\/p>\n

Boolean functions are simply functions whose variables are either a 0 or a 1. While this might seem quite simple, it is the basis of substantially complex cryptographic constructs. In cryptography, researchers are particularly concered on a the \"non-linearity\" property of boolean function. Non-Linearity is a measure by which we are able to determine the inputs of the function given the output.<\/p>\n

For a trivial example, imagine we have a function f(x1<\/sub>,x2<\/sub>)\u00a0= x1<\/sub>+x2<\/sub><\/strong>\u00a0 and another function g(x1<\/sub>,x2<\/sub>)\u00a0= x1\u00a0<\/sub>.\u00a0<\/strong>Clearly, it is easier to correlate the output of g to it's inputs (namely if g = 1 then x1<\/sub> = 1 and if g = 0 then x1<\/sub> = 0) than f with its inputs (although it is not that terribly hard). The overall idea is that the harder it is to figure out the inputs of a function given it's output, the more \"non-linear\" it is and the more cryptographically useful it becomes.<\/p>\n

The following is a \"tutorial\" style paper that explains the basis of boolean functions and how to compute their non-linearity. It explains how to calculate such non-linearity in one of the most refined and proficient ways to do so: with the Fast Walsh-Hadamard Transform. I also included a bit more information on what it means for a function to be \"non-linear\" and what benefits this brings.<\/p>\n

(You can also check this paper out in the Academia.edu link<\/a>.)<\/p>\n