Paper 2016/422

A deeper understanding of the XOR count distribution in the context of lightweight cryptography

Sumanta Sarkar and Siang Meng Sim

Abstract

In this paper, we study the behavior of the XOR count distributions under different bases of finite field. XOR count of a field element is a simplified metric to estimate the hardware implementation cost to compute the finite field multiplication of an element. It is an important criterion in the design of lightweight cryptographic primitives, typically to estimate the efficiency of the diffusion layer in a block cipher. Although several works have been done to find lightweight MDS diffusion matrices, to the best of our knowledge, none has considered finding lightweight diffusion matrices under other bases of finite field apart from the conventional polynomial basis. The main challenge for considering different bases for lightweight diffusion matrix is that the number of bases grows exponentially as the dimension of a finite field increases, causing it to be infeasible to check all possible bases. Through analyzing the XOR count distributions and the relationship between the XOR count distributions under different bases, we find that when all possible bases for a finite field are considered, the collection of the XOR count distribution is invariant to the choice of the irreducible polynomial of the same degree. In addition, we can partition the set of bases into equivalence classes, where the XOR count distribution is invariant in an equivalence class, thus when changing bases within an equivalence class, the XOR count of a diffusion matrix will be the same. This significantly reduces the number of bases to check as we only need to check one representative from each equivalence class for lightweight diffusion matrices. The empirical evidence from our investigation says that the bases which are in the equivalence class of the polynomial basis are the recommended choices for constructing lightweight MDS diffusion matrices.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. AFRICACRYPT 2016
DOI
10.1007/978-3-319-31517-1_9
Keywords
lightweight cryptographyfinite field multiplicationbasis of finite fieldXOR countMDS matricesdiffusion layer
Contact author(s)
sumanta sarkar1 @ tcs com
History
2016-05-01: received
Short URL
https://ia.cr/2016/422
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/422,
      author = {Sumanta Sarkar and Siang Meng Sim},
      title = {A deeper understanding of the XOR count distribution in the context of lightweight cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/422},
      year = {2016},
      doi = {10.1007/978-3-319-31517-1_9},
      note = {\url{https://eprint.iacr.org/2016/422}},
      url = {https://eprint.iacr.org/2016/422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.