# Understanding Fourier Coefficient

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)?

• do you understand the answer – kodlu Jan 24 at 22:18

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.