# Converting a 5-bit s-box to its bit-sliced format

I'm currently trying to convert a 5-bit sbox (the one from this cipher: http://primates.ae/wp-content/uploads/primatesv1.02.pdf) to its bit-sliced format (i.e. to a boolean network).

Most papers only address techniques for converting up to 4-bit s-boxes into their bitsliced format.

I have done some work trying to brute-force my way to the results, as a 5-bit s-box does not seem as much, this however still proved tricky, as their is in the end an infinite possibility og AND, NOT, OR and XOR that you can do on the 5 input bits... Is there any accepted/known way of doing this, or does it come down to trying to bruteforce different combinations till a matching one is found? (I hope not, as I have no guarantee on it being the optimal then).

I have considered trying to make truth tables and synthesize the logic network from them. I'm not sure this is the way to go though.

A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4.

In summary: you first encode the existence of a bitsliced implementation as a SAT problem, use an off-th-shelf SAT-solver to solve it and finally retrieve the bitsliced encoding from the output of the SAT-solver.

[1]: http://eprint.iacr.org/2016/198.pdf "Optimizing S-box Implementations for Several Criteria using SAT Solvers", Ko Stoffelen, Proceedings of Fast Software Encryption 2016

• and in the paper there is even a link to github repo...
– Kris
Commented May 3, 2016 at 20:16
• I cannot thank you enough for that answer. It has really helped me out. It describes well how to also optimize the s-box afterwards, so I can do some testing in terms of efficiency with the different variations of the s-box. Thanks! Commented May 7, 2016 at 15:26
• Another FSE paper you may want to check eprint.iacr.org/2017/101
– hola
Commented Sep 30, 2018 at 17:56

Try to generate the Algebraic Normal Form (ANF) from the sbox step by step (i.e., with 2 bits and so on) or use something like http://cis.sjtu.edu.cn/index.php/A_Simple_Python_Script_for_Translating_Sbox_to_ANF_Boolean_Functions