Cryptology ePrint Archive: Report 2017/376

Determining the Minimum Degree of an S-box

P. R. Mishra, Sumanta Sarkar and Indivar Gupta

Abstract: S-boxes are important building blocks in block ciphers. For secure design one should not choose an S-box that has low degree. In this work we consider minimum degree of an S-box which is the minimum value of the degree of the nonzero component functions of the S-box. For an S-box $F : {F_2}^n \rightarrow {F_2}^m$, there are $2^m - 1$ nonzero component functions, we show that there is a better way to determine the minimum degree of an S-box which does not require to check all the $2^m - 1$ component functions. To the best of our knowledge, this is the best algorithm for determining the minimum degree of an S-box in the literature.

Category / Keywords: Boolean function, S-box, degree, row echelon form, linear span.

Date: received 27 Apr 2017, last revised 27 Apr 2017

Contact author: indivar_gupta at yahoo com

Available format(s): PDF | BibTeX Citation

Version: 20170501:134121 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]