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).
LFSRs are 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:
However, this article is not about LFSRs, but rather something even more fundamental: Boolean Functions.
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.
For a trivial example, imagine we have a function f(x1,x2) = x1+x2 and another function g(x1,x2) = x1 . Clearly, it is easier to correlate the output of g to it's inputs (namely if g = 1 then x1 = 1 and if g = 0 then x1 = 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.
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.
(You can also check this paper out in the Academia.edu link.)
Loading...
Reload document 
Open in new tab
Recent Comments