Differential & linear characteristics for integer multiplication What are the probabilities of differential &amp; linear characteristics for the function that XORs the high and low bits from a $n \times n \rightarrow 2n$ bit multiplication?

I remember reading somewhere that this function (which seems very fast in software) has excellent non-linearity.  This suggests applications in (say) a Feistel network (where invertability is not required).
This is the code i used to simulate your Sbox (no intelligence, pure application with lots of mask for security).

virtual uint8 apply_s(uint16 input, int numBits) {
    uint16 mask = 1;
    for (int i = 1; i &lt; numBits; ++i)
    { 
        mask |= mask &lt;&lt; 1;
    } 
    uint32 res = input &amp; mask; 
    res = res * res;
    res = (res &gt;&gt; numBits) ^ (res &amp; mask);
    return res &amp; mask;
};


And these are the linear and differential results (not all equations are printed but the most probables ones):



Linear Cryptanalysis : 4 bits

    |   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
---------------------------------------------------------------------
  0 |   8   2   2       2  -2   2  -2   2   2              -2  -4  -2 
  1 |       2   2                       2   2          -2       2     
  2 |      -2   4   2   2  -2           2  -2   2   2      -2   2     
  3 |      -2      -2           2  -2  -2   2   2   2   2   4       2 
  4 |       2   2      -2  -2  -2  -2   2   2   4   4       2      -2 
  5 |       2  -2   4       4  -4       2   2           2      -2     
  6 |       2       2  -2   2           2   2   2  -2      -2   2     
  7 |       2       2           2   6  -2  -2  -2   2  -2           2 
  8 |           2  -2   2       2       2          -2           4     
  9 |          -2   2  -4  -2       2   2       4   2   2  -2   2   2 
 10 |                   2   4   4   2  -2  -4   2  -4   4       2  -2 
 11 |                   4   2  -2       2      -2       2   2         
 12 |      -4   2   2   2       2      -2           2               4 
 13 |       4   2   2       2       2  -2           2  -2   2  -2  -2 
 14 |          -4  -4   2           2   2      -2       4   4   2   2 
 15 |                       2   2      -2   4  -2      -2   2       4 
X0 ⊕ X1 ⊕ X2 = Y0 ⊕ Y1 ⊕ Y2  : 6
X1 ⊕ X2 ⊕ X3 = Y1  : -4
X1 ⊕ X3 = Y0 ⊕ Y1 ⊕ Y3  : -4
X1 ⊕ X2 ⊕ X3 = Y0 ⊕ Y1  : -4
X0 ⊕ X2 = Y1 ⊕ Y2  : -4
X0 ⊕ X3 = Y2  : -4
X2 ⊕ X3 = Y0  : -4
X1 ⊕ X3 = Y0 ⊕ Y3  : -4




Differential Cryptanalysis : 4 bits

    |   0   1   2   3   4   5   6   7   8   9   a   b   c   d   e   f 
---------------------------------------------------------------------
  0 |  16                                                             
  1 |   2   2           2           2       2   2       2   2         
  2 |       2           2       2   2   2       4       2             
  3 |               2       2   4           2   2   2           2     
  4 |       4   2                   2       2   2   2       2         
  5 |   2                       4   2   2                   4       2 
  6 |       2       2       2   2                   4   2   2         
  7 |       2   2                   4   2           2   4             
  8 |                   2   2   2   2   2           2       2   2     
  9 |       2   2       2   2               2   4   2                 
  a |   2   2   2                   2       2               2       4 
  b |   4           2       2                       2       2   4     
  c |           2       2   2   2           2           6             
  d |   2   2       2       2           4           2   2             
  e |           2   2           4       2       2           2   2     
  f |   2       2               2   2       2   2                   4 
1011 =&gt; 1110 : 4 / 16
0011 =&gt; 0110 : 4 / 16
0110 =&gt; 1011 : 4 / 16
0101 =&gt; 1101 : 4 / 16
0010 =&gt; 1010 : 4 / 16
0100 =&gt; 0001 : 4 / 16
0101 =&gt; 0110 : 4 / 16
0111 =&gt; 1100 : 4 / 16
0111 =&gt; 0111 : 4 / 16
1100 =&gt; 1100 : 6 / 16
1010 =&gt; 1111 : 4 / 16
1011 =&gt; 0000 : 4 / 16
1001 =&gt; 1010 : 4 / 16
1110 =&gt; 0110 : 4 / 16
1111 =&gt; 1111 : 4 / 16
1101 =&gt; 1000 : 4 / 16




Linear Cryptanalysis : 8 bits

X0 ⊕ X3 ⊕ X5 ⊕ X7 = Y6  : -40
X0 ⊕ X2 ⊕ X3 ⊕ X6 = Y4  : -38
X1 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y1 ⊕ Y3 ⊕ Y7  : -34
X1 ⊕ X4 ⊕ X7 = Y1  : -34
X0 ⊕ X1 ⊕ X2 ⊕ X3 ⊕ X5 ⊕ X7 = Y2 ⊕ Y3  : -33
X4 ⊕ X6 = Y3 ⊕ Y4 ⊕ Y7  : 32
X1 ⊕ X3 ⊕ X5 ⊕ X7 = Y1 ⊕ Y2 ⊕ Y5 ⊕ Y6  : 32
X0 ⊕ X2 ⊕ X4 ⊕ X6 = Y0 ⊕ Y3 ⊕ Y4 ⊕ Y6 ⊕ Y7  : -32
X1 ⊕ X2 ⊕ X5 ⊕ X6 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y3 ⊕ Y5  : -32




Differential Cryptanalysis : 8 bits

00000010 =&gt; 01001011 : 8 / 256
00000100 =&gt; 10010000 : 6 / 256
00000110 =&gt; 11010000 : 8 / 256
00000110 =&gt; 11010010 : 10 / 256
00000100 =&gt; 10100100 : 8 / 256
00011000 =&gt; 00111001 : 8 / 256
00000110 =&gt; 11010110 : 8 / 256
00000010 =&gt; 10001010 : 8 / 256
00000010 =&gt; 00101001 : 8 / 256
00000010 =&gt; 00101010 : 8 / 256


We can compare these results the S-box analysis of AES :

Linear analysis

X3 ⊕ X6 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y5 ⊕ Y6 ⊕ Y7  : 16
X1 ⊕ X2 ⊕ X6 = Y1 ⊕ Y6 ⊕ Y7  : 16
X0 ⊕ X2 = Y0 ⊕ Y1 ⊕ Y2 ⊕ Y3  : 16
X0 ⊕ X2 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 = Y1 ⊕ Y4 ⊕ Y5  : 16
X1 ⊕ X2 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y0 ⊕ Y1 ⊕ Y4 ⊕ Y5 ⊕ Y6 ⊕ Y7  : 16
X0 ⊕ X2 ⊕ X3 ⊕ X5 = Y0 ⊕ Y1 ⊕ Y4 ⊕ Y5 ⊕ Y6 ⊕ Y7  : 16
X0 ⊕ X5 = Y0 ⊕ Y1 ⊕ Y3 ⊕ Y5 ⊕ Y6 ⊕ Y7  : 16
X0 ⊕ X3 ⊕ X7 = Y0 ⊕ Y2 ⊕ Y3 ⊕ Y5  : 16
X1 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X6 ⊕ X7 = Y0 ⊕ Y1 ⊕ Y3 ⊕ Y4  : 16
X1 ⊕ X2 ⊕ X3 ⊕ X4 ⊕ X5 ⊕ X7 = Y2 ⊕ Y5 ⊕ Y6  : 16


Differential Cryptanalysis

01010111 =&gt; 00111000 : 4 / 256
01000111 =&gt; 11000011 : 4 / 256
00000110 =&gt; 00001100 : 4 / 256
00011011 =&gt; 11001100 : 4 / 256
01001000 =&gt; 00110001 : 4 / 256
01110100 =&gt; 11110001 : 4 / 256
11000100 =&gt; 01111111 : 4 / 256
10111011 =&gt; 10001001 : 4 / 256
00101010 =&gt; 10000110 : 4 / 256
01011000 =&gt; 00001001 : 4 / 256


TL;DR : In both case (linear &amp; differential), the Sbox of AES is better by a nice margin against cryptanalysis.

I did not pursue the analysis for higher values of $n$ because the RAM required to find the equations increases exponentially...