Paper 2014/551

Diffusion Matrices from Algebraic-Geometry Codes with Efficient SIMD Implementation

Daniel Augot, Pierre-Alain Fouque, and Pierre Karpman


This paper investigates large linear mappings with very good diffusion and efficient software implementations, that can be used as part of a block cipher design. The mappings are derived from linear codes over a small field (typically $F^{2^4}$) with a high dimension (typically 16) and a high minimum distance. This results in diffusion matrices with equally high dimension and a large branch number. Because we aim for parameters for which no MDS code is known to exist, we propose to use more flexible algebraic-geometry codes. We present two simple yet efficient algorithms for the software implementation of matrix-vector multiplication in this context, and derive conditions on the generator matrices of the codes to yield efficient encoders. We then specify an appropriate code and use its automorphisms as well as random sampling to find good such matrices. We provide concrete examples of parameters and implementations, and the corresponding assembly code. We also give performance figures in an example of application which show the interest of our approach.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.Selected Areas in Cryptography 2014
Diffusion matrixalgebraic-geometry codesalgebraic curvesSIMDvector implementationSHARK
Contact author(s)
pierre karpman @ gmail com
2014-07-24: last of 2 revisions
2014-07-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Augot and Pierre-Alain Fouque and Pierre Karpman},
      title = {Diffusion Matrices from Algebraic-Geometry Codes with Efficient SIMD Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/551},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.