Paper 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\o 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.

Note: Added DOI

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2016
DOI
10.1007/978-3-662-52993-5
Keywords
S-boxSAT solversimplementation optimizationmultiplicative complexitycircuit depth complexityshortest linear straight-line program
Contact author(s)
k stoffelen @ cs ru nl
History
2017-07-13: last of 3 revisions
2016-02-24: received
See all versions
Short URL
https://ia.cr/2016/198
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/198,
      author = {Ko Stoffelen},
      title = {Optimizing S-box Implementations for Several Criteria using SAT Solvers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/198},
      year = {2016},
      doi = {10.1007/978-3-662-52993-5},
      note = {\url{https://eprint.iacr.org/2016/198}},
      url = {https://eprint.iacr.org/2016/198}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.