Understanding Fourier Coefficient

Question

In Bogdanov's and others, PRESENT: An Ultra-Lightweight Block Cipher, they mention that the S-box in PRESENT fulfill four primary conditions. They denote the Fourier coefficient as $$S_b^W (a) = \sum_{x\in \mathbb{F}_2^4} (-1) ^{\langle b, S(x)\rangle+\langle a,x \rangle}.$$

I am trying to understand what conditions (3) and (4) are trying to say. They are:

(3) For all non-zero $a\in \mathbb{F}_2^4$ and all non-zero $b\in \mathbb{F}_2^4$ it holds that $|S_b^W|\leq 8$.

(4) For all $a \in \mathbb{F}_2^4$ and all non-zero $b \in \mathbb{F}_2^4$ such that $wt(a) = wt(b) = 1$ it holds that $S_b^W (a) = \pm 4$

How does one raise a power to Bogdanov's notation (or compute such sum)?

Answer 1

You have a typo, $x$ is also in $\mathbb{F}_2^4,$ since the Present Sbox is $4\times 4$ bits.

The quantities $S(x),a,b,x$ all lie in $\mathbb{F}_2^4,$ and the inner products such as $\langle b,S(x)\rangle$ etc lie in $\mathbb{F}_2.$ We now treat the inner product values as in $\mathbb{N},$ so we can calculate $(-1)^{\langle b,S(x)\rangle+\langle a,x\rangle}.$

Basically if the two inner products in the exponent match we have a $+1$ in the overall sum, otherwise a $-1$. Thus the sum computes the imbalance function defined as $$2^4-2d_H(\langle b,S(x)\rangle,\langle a,x\rangle)$$ between the two quantities in the exponent as $x$ ranges over $\mathbb{F}_2^4.$

Here $d_H$ is the hamming distance along the truth tables.