Let F denote the finite field with 256 elements, and let n be a positive integer relatively prime to 255. Let A be a random bijective F_2 linear transformation from F to F. Let S(x)=A*(x^n). Then S is a permutation of F. In this visualization, the quantity n is denoted as 'power'.
If j is an element of F, then let f_j(x)=S(j+x)-S(j). Then the animation shows the spectrum of \sum_j f_j where each f_j is considered as a permutation matrix and where we take the sum over all elements of F. Each of these spectra contains two outliers (one of these outliers occurs since the permutations f_j all leave 0 fixed), so we remove these two outliers in the animation.
When n=255-2^i for some i less than 8, the function S closely resembles the AES S-box as the AES S-box is of the form S(x)=A*(x^(-1))+b for a well-chosen matrix A and vector b . In this case, the spectrum of S forms a circular pattern because the sum \sum_j f_j is nearly orthogonal after scaling. When n=255-2^i, we also observe that all of the eigenvalues of \sum_j f_j except for the two outliers have magnitude around 16. This distribution of the eigenvalues is beneficial for the security of the AES S-box. Consider the Markov chain on F^2 where we transition from (x,y) to (j+S(x),j+S(y)) where j is randomly selected from F. Since the eigenvalues of \sum_j f_j (except for the outliers) are all around 16, this Markov chain will have a very fast mixing time, and such a fast mixing time is what we want for cryptography. We also observe that for the AES S-box, we get improved cryptographic security by using S(x)=A*x^(-1) for some invertible matrix A instead of S(x)=x^(-1) since for S(x)=x^(-1), the eigenvalues of \sum_j f_j will have magnitude up to 18 after we remove the outliers.
If n=2^i for some i, then the mapping S is linear, and in this case, the function S cannot be used for any cryptographic purpose.
Unless otherwise stated, all algorithms featured on this channel are my own. You can go to
github.com/sponsors/jvanname to support my research on machine learning algorithms. I am also available to consult on the use of safe and interpretable AI for your business. I am designing machine learning algorithms for AI safety such as LSRDRs. In particular, my algorithms are designed to be more predictable and understandable to humans than other machine learning algorithms, and my algorithms can be used to interpret more complex AI systems such as neural networks. With more understandable AI, we can ensure that AI systems will be used responsibly and that we will avoid catastrophic AI scenarios. There is currently nobody else who is working on LSRDRs, so your support will ensure a unique approach to AI safety.
@blinking_dodo
2 months ago
Point of constructive feedback: have the x/y axis fixed. A line of y=x should be 45 degrees, and a point at 15,10 should be at the same screen location regardless which graph it's on. I am seeing ovals where they should probably be more like circles.... And as always, thanks for the nice patterns in the video and magic spells in the description. π
2 |