Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation

Daniel Augot; Pierre Alain Fouque; Pierre Karpman

doi:10.1007/978-3-319-13051-4_15

Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation

Daniel Augot
, Pierre Alain Fouque
, Pierre Karpman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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₂₄) 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.

Original language	English
Title of host publication	Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers
Editors	Antoine Joux, Amr Youssef
Publisher	Springer Verlag
Pages	243-260
Number of pages	18
ISBN (Electronic)	9783319130507
DOIs	https://doi.org/10.1007/978-3-319-13051-4_15
Publication status	Published - 1 Jan 2014
Event	21st International Conference on Selected Areas in Cryptography, SAC 2014 - Montreal, Canada Duration: 14 Aug 2014 → 15 Aug 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8781
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Selected Areas in Cryptography, SAC 2014
Country/Territory	Canada
City	Montreal
Period	14/08/14 → 15/08/14

Keywords

Algebraic curves
Algebraic-geometry codes
Diffusion matrix
SHARK
SIMD
Vector implementation

Access to Document

10.1007/978-3-319-13051-4_15

Cite this

Augot, D., Fouque, P. A., & Karpman, P. (2014). Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation. In A. Joux, & A. Youssef (Eds.), Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers (pp. 243-260). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8781). Springer Verlag. https://doi.org/10.1007/978-3-319-13051-4_15

Augot, Daniel ; Fouque, Pierre Alain ; Karpman, Pierre. / Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation. Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers. editor / Antoine Joux ; Amr Youssef. Springer Verlag, 2014. pp. 243-260 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0c38bc672c214713918f9974ea4c0e37,

title = "Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation",

abstract = "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 F24) 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.",

keywords = "Algebraic curves, Algebraic-geometry codes, Diffusion matrix, SHARK, SIMD, Vector implementation",

author = "Daniel Augot and Fouque, \{Pierre Alain\} and Pierre Karpman",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 21st International Conference on Selected Areas in Cryptography, SAC 2014 ; Conference date: 14-08-2014 Through 15-08-2014",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-13051-4\_15",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "243--260",

editor = "Antoine Joux and Amr Youssef",

booktitle = "Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers",

}

Augot, D, Fouque, PA & Karpman, P 2014, Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation. in A Joux & A Youssef (eds), Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8781, Springer Verlag, pp. 243-260, 21st International Conference on Selected Areas in Cryptography, SAC 2014, Montreal, Canada, 14/08/14. https://doi.org/10.1007/978-3-319-13051-4_15

Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation. / Augot, Daniel; Fouque, Pierre Alain; Karpman, Pierre.
Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers. ed. / Antoine Joux; Amr Youssef. Springer Verlag, 2014. p. 243-260 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8781).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation

AU - Augot, Daniel

AU - Fouque, Pierre Alain

AU - Karpman, Pierre

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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 F24) 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.

AB - 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 F24) 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.

KW - Algebraic curves

KW - Algebraic-geometry codes

KW - Diffusion matrix

KW - SHARK

KW - SIMD

KW - Vector implementation

U2 - 10.1007/978-3-319-13051-4_15

DO - 10.1007/978-3-319-13051-4_15

M3 - Conference contribution

AN - SCOPUS:84918504717

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 243

EP - 260

BT - Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers

A2 - Joux, Antoine

A2 - Youssef, Amr

PB - Springer Verlag

T2 - 21st International Conference on Selected Areas in Cryptography, SAC 2014

Y2 - 14 August 2014 through 15 August 2014

ER -

Augot D, Fouque PA, Karpman P. Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation. In Joux A, Youssef A, editors, Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Revised Selected Papers. Springer Verlag. 2014. p. 243-260. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-13051-4_15

Diffusion matrices from algebraic-geometry codes with efficient SIMD implementation

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this