I want to generate a 16,8 perfectly nonlinear S-box for an encryption algorithm I am working on. I don't have a background in math, and I'm an undergrad, so a lot of the math involved is very confusing.

I want the perfectly nonlinear S-box to have 16 bits of input and 8 bits of output.

I have been reading Kaisa Nyberg's 1991 paper Perfect nonlinear S-boxes, and I am having trouble understanding the method described.

In Section 4, A Construction based on Maiorana-McFarland method, the implementation is described as:

  • Take n bits of input (where n >= 2m)
  • Split the n bits into two parts (x1 and x2)
  • Obtain the first digit of the output (of length m) by doing x1 • x2
  • And the second digit of the output by shifting a n/2 size LFSR (with a primitive feedback polynomial) once, and the calculating • between LFSR's content and x2.

I am having trouble understanding how the two digits are to be used since both would be of length m..

  • concatenating them would make the output size 2m

Which is not right. The problems I face are:

  • Should there be a • operation between the two digits to produce an m-bit output? In a construction based on Maiorana-McFarland method?
  • Which (per my understanding modular) operation would be the optimal?

  • Is there anything else I should be considering in addition to perfect nonlinearity?


1 Answer 1


$A:\mathbb{F}_2^m\rightarrow \mathbb{F}_2^m$ is the state space map induced by the primitive length $m$ LFSR.

Thus it maps the zero vector of length $m$ to itself and in general the LFSR state $(a_0,a_1, \ldots,a_{m-1})$ to $(a_1,\ldots,a_m)$. $A^i$ is just $A$ iterated $i$ times (shift LFSR $i$ times).

Then, the APN map $z=(z_1,\ldots,z_n)=F(x_1,x_2)$ where $x_1,x_2,z,\in \mathbb{F}_2^m$ is given by $$ z_i=A^{i-1}(x_1)\cdot x_2,\quad i=1,\ldots,m $$ where $z_i$ are individual bits.

  • $\begingroup$ Thanks for the definition, It was most helpful! Please correct me if I'm wrong but the operation between the two bits (output from LFSR and the bits from x2) will be a XOR, right? $\endgroup$
    – Sid
    Commented Mar 14, 2020 at 11:22
  • $\begingroup$ In the equation for bit $z_i$ we have a dot product of two binary vectors of length $m$. For simplicity call them $a$ and $b$. The definition of dot product is $a\cdot b=a_1 b_1 \oplus a_2 b_2 \oplus \cdots \oplus a_m b_m.$ $\endgroup$
    – kodlu
    Commented Mar 14, 2020 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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