# How to generate a 16 X 8 perfectly nonlinear S-box

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?

$$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.
• 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.$ – kodlu Mar 14 at 14:59