1
\$\begingroup\$

Lightweight block ciphers are usually optimized for compact hardware implementations and sbox values are computed by implementing circuit using basic logic gates(AND, XOR, OR, NOR etc).

What is the method to find an efficient hardware implementation of a 4-bit sbox?

For example, the Sbox of the Piccolo cipher is

enter image description here

which can be computed in hardware by

enter image description here

The solution I could think of is "find Algebraic Normal Form(ANF) of all boolean functions, and then make the circuit". But this does not seem to produce a compact representation.

\$\endgroup\$
  • \$\begingroup\$ Seems like schematics by cryptologists are almost as bad as those by physicists ... but for different reasons. \$\endgroup\$ – brhans Mar 7 '19 at 13:11
  • \$\begingroup\$ I'm voting to close this question as off-topic because we closed this exact same question by the same guy 44 minutes ago, which he since then deleted. \$\endgroup\$ – Marcus Müller Mar 7 '19 at 13:29
  • \$\begingroup\$ It pains me a bit, however, because hardyrama actully gave a good, more general answer! It would be salomonic to rephase the question to perfectly fit the answer. \$\endgroup\$ – Marcus Müller Mar 7 '19 at 13:30
  • \$\begingroup\$ @MarcusMüller I was asked to post question at electrical engineering forum, when i posted here moderators migrated the origanl question also which resulted in duplication. So i deleted the other one. \$\endgroup\$ – khan Mar 7 '19 at 13:40
2
\$\begingroup\$

What is the method to find efficient hardware implementaion of a 4-bit sbox?

finding efficient hardware implementation is by looking on :

  • Multiplicative complexity: the smallest number of nonlinear gates
  • Bitslice gate complexity: the smallest number of operations in {AND, OR, XOR, NOT} required to compute this function
  • Gate complexity: the smallest number of logic gates required to compute this function
  • Circuit depth complexity: the length of the longest paths from an input gate to an output gate

There are methods used to find efficient implementation such as SAT solving [ref][source code]1 (the sat solver has been applied on Piccolo sbox) and Logic Minimization Techniques ref which has been to find bit-slice implementation of AES sbox.
for further reading , I also recommend you to read SoK: Peigen – a Platform for Evaluation, Implementation, and Generation of S-boxes

\$\endgroup\$
1
\$\begingroup\$

If you have the GF(2) description for the SBOX, you can do the reductions to get to a minimal circuit discussion. Pulling from a description of how I implemented the AES S-Box, this is the basic method:

\$GF(2)\$ polynomials represent rings of numbers and the logic reductions used in this work are based \$GF(2)\$ polynomials. The computations on \$GF(2^8)\$ are done by lower order composite field reduction using \begin{align} \label{eqn:GFdecomposition} GF(2^2)&\rightarrow GF(2)&:x^2+x+1\nonumber \\ GF((2^2)^2)&\rightarrow GF(2^2)&:x^2+x+\varphi\\ GF(((2^2)^2)^2)&\rightarrow GF((2^2)^2)&:x^2+x+\lambda \nonumber \end{align} where \$\varphi=\{10\}_2\$ and \$\lambda=\{1100\}_2\$. As previously stated, \$GF(2^2)\$ polynomials can be decomposed to lower-order composite fields where \$n_1x+n_0\$. Therefore, any binary number, \$k\$, can be split into \$k_Hx+k_L\$. As an example, for \$k=\{1001\}_2\$, the value \$k\$ is \$k_Hx+k_L\$, resulting in \$\{10\}_2x+\{01\}_2\$, which can be further reduced to \$\{1\}_2x+\{0\}_2\$ and \$\{0\}_2x+\{1\}_2\$ as high and low terms.

Given the mathematics, and a few hours, you can get a minimal circuit implementation.

\$\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.