Linear Approximation Table

[ghost]

Hello,

I have problems understanding how the LAT is calculated in PEIGEN. Different papers showed, that the LAT counts, how often XOR(inputvector*X)=XOR(outputvector*Y) where XOR means the bitwise XOR. Page 10: http://cse.iitkgp.ac.in/~debdeep/courses_iitkgp/Crypto/slides/LC.pdf Page 2: https://link.springer.com/content/pdf/10.1007/3-540-60590-8_10.pdf

In case of a 4-bit S-Box, entry (2, f) or (0010, 1111) in binary should be the Linear Approximation x3=y1 XOR y2 XOR y3 XOR y4, where x1/y1 is the Most Significant Bit.

I tried it with a S-Box, where the output is the Input+1 mod 16. The entry (f, f) should be equal to 6, because:

1. XOR(0001)=XOR(0010)=1
2. XOR(0101)=XOR(0110)=0
3. XOR(0111)=XOR(1000)=1
4. XOR(1001)=XOR(1010)=0
5. XOR(1101)=XOR(1110)=1
6. XOR(1111)=XOR(0000)=0

But PEIGEN says it is 4. What was my fault here?

N_plus_1 Sbox:
LUT = {
0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,0x00,
};

...

LAT = 
{
      0|   1|   2|   4|   8|   3|   5|   6|   9|   a|   c|   7|   b|   d|   e|   f| 
{0:  16,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, },
{1:   0,  16,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, },
{2:   0,   0,   0,   0,   0,  16,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, },
{4:   0,   0,   0,   8,   0,   0,   8,   8,   0,   0,   0,   8,   0,   0,   0,   0, },
{8:   0,   0,   0,   0,  12,   0,   0,   0,   4,   4,   4,   0,   4,   4,   4,   4, },
{3:   0,   0,  16,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, },
{5:   0,   0,   0,   8,   0,   0,   8,   8,   0,   0,   0,   8,   0,   0,   0,   0, },
{6:   0,   0,   0,   8,   0,   0,   8,   8,   0,   0,   0,   8,   0,   0,   0,   0, },
{9:   0,   0,   0,   0,   4,   0,   0,   0,  12,   4,   4,   0,   4,   4,   4,   4, },
{a:   0,   0,   0,   0,   4,   0,   0,   0,   4,   4,   4,   0,  12,   4,   4,   4, },
{c:   0,   0,   0,   0,   4,   0,   0,   0,   4,   4,  12,   0,   4,   4,   4,   4, },
{7:   0,   0,   0,   8,   0,   0,   8,   8,   0,   0,   0,   8,   0,   0,   0,   0, },
{b:   0,   0,   0,   0,   4,   0,   0,   0,   4,  12,   4,   0,   4,   4,   4,   4, },
{d:   0,   0,   0,   0,   4,   0,   0,   0,   4,   4,   4,   0,   4,  12,   4,   4, },
{e:   0,   0,   0,   0,   4,   0,   0,   0,   4,   4,   4,   0,   4,   4,   4,  12, },
{f:   0,   0,   0,   0,   4,   0,   0,   0,   4,   4,   4,   0,   4,   4,  12,   4, },
};
Lin: 16, LAT_spectrum: {0:172, 4:56, 8:16, 12:8, 16:4, };
Lin1: 16, LAT1_spectrum: {0:13, 8:1, 12:1, 16:1, };

[pfasante]

There are several possibilities for the entries of the LAT, typically you count how often the XOR sum of the masked input does not equals the XOR sum of the masked output minus how often it does equals.

What I prefer is the notation that the LAT at position (a,b) contains the Fourier coefficient of the S-box at point (a,b) (the Fourier coefficient might also be called Walsh coefficient, or Walsh-Hadamard).

So for position (f, f) we get: 10 times different XOR sum, 6 times equal XOR sum => 10-6 = 4.