1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ do you understand the answer $\endgroup$ – kodlu Jan 24 at 22:18
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.