Cryptology ePrint Archive: Report 2016/198

Optimizing S-box Implementations for Several Criteria using SAT Solvers

Ko Stoffelen

Abstract: We explore the feasibility of applying SAT solvers to optimizing implementations of small functions such as S-boxes for multiple optimization criteria, e.g., the number of nonlinear gates and the number of gates. We provide optimized implementations for the S-boxes used in Ascon, ICEPOLE, Joltik/Piccolo, Keccak/Ketje/Keyak, LAC, Minalpher, PRIMATEs, Prø st, and RECTANGLE, most of which are candidates in the secound round of the CAESAR competition. We then suggest a new method to optimize for circuit depth and we make tooling publicly available to find efficient implementations for several criteria. Furthermore, we illustrate with the 5-bit S-box of PRIMATEs how multiple optimization criteria can be combined.

Category / Keywords: secret-key cryptography / S-box, SAT solvers, implementation optimization, multiplicative complexity, circuit depth complexity, shortest linear straight-line program

Original Publication (with minor differences): IACR-FSE-2016

Date: received 24 Feb 2016, last revised 27 Jul 2016

Contact author: k stoffelen at cs ru nl

Available format(s): PDF | BibTeX Citation

Note: Added DOI

Version: 20160727:123044 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]