Monoidic Codes in Cryptography - Post-Quantum Cryptography - page 196

A An Exemplary Quasi-Monoidic Srivastava Code

For our example, let p =3 ,s =1 ,m =4 ,d =3 ,t =3.Weusetheextensionfield
F 3 4

3 of size N = p d = 27, with set of
generators b 1 =(1 , 0 , 0), b 2 =(0 , 1 , 0), b 3 =(0 , 0 , 1).
We randomly select the images of the

F 3 [ u ] / u 4 +2 u 3 +2

, the group A =

Z

=

F 3 -linearly dependent

h (0) − 1 = u 3 + u 2 + u +2 , h ( b 1 ) − 1 = u 2 +2 u +1 ,

h ( b 2 ) − 1 = u 3 +2 u 2 + u +1 , h ( b 3 ) − 1 = u 2 +1 .

We also select a shift ω = u 3 +2 u + 2, compute β =(2 u 3 + u 2 +1 ,u 3 + u 2 +
u, u 2 +2 u +2), and γ =( γ 0 ,...,γ 8 )with

γ 0 =( u 3 +2 u +2 , 1 , 2 u 3 + u ) , γ 1 =( u 3 + u 2 +2 u +1 ,u 2 , 2 u 3 + u 2 + u +2) ,

γ 2 =( u 3 +2 u 2 +2 u, 2 u 2 +2 , 2 u 3 +2 u 2 + u +1) , =( u +1 , 2 u 3 +2 u, u 3 +2) ,

3

γ 4 =( u 2 + u, 2 u 3 + u 2 +2 u +2 ,u 3 + u 2 +1) , γ 5 =(2 u 2 + u +2 , 2 u 3 +2 u 2 +2 u +1 ,u 3 +2 u 2 ) ,

γ 6 =(2 u 3 ,u 3 + u +2 , 2 u +1) , γ 7 =(2 u 3 + u 2 +2 ,u 3 + u 2 + u +1 ,u 2 +2 u ) ,

γ 8 =(2 u 3 +2 u 2 +1 ,u 3 +2 u 2 + u, 2 u 2 +2 u +2) .

where the group indices are ordered 0 = (0 , 0 , 0) ,a 1 =(1 , 0 , 0) ,a 2 =(2 , 0 , 0) ,...,
a p d − 1 =(2 , 2 , 2). Our blocksize is b =gcd( t, N ) = 3 and we randomly choose the

permutation τ = 012345678

567834012 .Weuseonlythefirst =6blockschosenbythe
permutation, i.e., blocks 5 , 6 , 7 , 8 , 3 , 4, resulting in a code of length n = b = 18.
We continue and select the support permutations

π 0 =0 , 1 =2 , 2 =1 , 3 =2 , 4 =0 , 5 =1 .

corresponding to the monoidic permutation matrices M ( χ a π i ), where

⎛ ⎞ ⎛ ⎞ ⎛ ⎞

100
010
001

001
100
010

010
001
100

⎝ ⎠ , ⎝ ⎠ , ⎝ ⎠ .

M ( χ a 0 )= M ( χ a 1 )= M ( χ a 2 )=

We compute

γ 0 =(2 u 2 + u +2 , 2 u 3 +2 u 2 +2 u +1 ,u 3 +2 u 2 ) , γ 1 =( u 3 + u +2 , 2 u +1 , 2 u 3 ) ,

γ 2 =( u 2 +2 u, 2 u 3 + u 2 +2 ,u 3 + u 2 + u +1) , γ 3 =( u 3 +2 u 2 + u, 2 u 2 +2 u +2 , 2 u 3 +2 u 2 +1) ,

γ 4 =( u +1 , 2 u 3 +2 u, u 3 +2) , γ 5 =( u 3 + u 2 +1 ,u 2 + u, 2 u 3 + u 2 +2 u +2) .

Afterwards, we have to set the scaling factors σ and to compute the layered
parity-check matrix from the sequence β and γ . Since we would like to end up

with a Goppa code (to be able to use the superior error-correction capabilities
of “equal magnitude” decoding described in Appendix B), we will set all σ i =1
and the Cauchy layered exponent to be r =1.