Cryptography Reference
In-Depth Information
The relevant parameters used for this process are described in Figure 1 and the
corresponding algorithm is presented in Figure 3. We will continue by explaining
some details including the QM-subroutines used therein and conclude with a
clarifying example.
We start the generation process by choosing a random fully monoidic Goppa
code of length
N
. Then we split the support in blocks of length
b
and select
such blocks at random to comprise the support of our quasi-monoidic code. To
each chosen support block, we apply a random monoidic permutation, i.e., we
multiply with the matrix
M
(
χ
a
π
), where
χ
a
π
is the characteristic function of the
group element
a
π
, for a randomly chosen
π
.Since
χ
is a characteristic function,
this matrix will have a single non-zero coecient being 1 per row and column,
so it is a permutation matrix. Furthermore, this transformation preserves the
monoidic structure of the block and indeed all monoidic permutations have this
form.
We continue by creating the parity-check matrix
H
of our code consisting of
the
scaled Cauchy layered matrices corresponding to each block. The resulting
matrix consists of
tr/
b
×
monoidic blocks of size
b
and we will keep this quasi-
monoidic structure intact for the remainder. Note that if
q>
2, i.e., we have
non-trivial scaling factors, then the code defined via our parity-check matrix
need not be Goppa anymore, but it is always a Generalized Srivastava code.
The first subroutine
QMTrace
will generate a parity-check matrix for the
corresponding subfield subcode over the base field
for some irreducible polynomial
f
of degree
m
. We can identify each matrix coef-
ficient
h
i,j
with its representative polynomial
h
i,j,
0
+
h
i,j,
1
x
+
F
q
. Recall that
F
Q
=
F
q
[
x
]
/
f
+
h
i,j,m−
1
x
m−
1
of smallest degree. We expand the matrix rows by a factor of
m
and distribute
the entries as follows
h
new
···
h
i,j,k
,i.e., in order to keep the block structure
intact, we first take all constant terms of coecients in a block then all linear
terms and so on.
The second subroutine
QMGauss
will compute the quasi-monoidic system-
atic form of the parity-check matrix. It does so by identifying each monoidic block
with an element of the corresponding ring of monoidic matrices and performing
the usual Gauss algorithm on those elements. Since this ring is not necessarily an
integral domain, the algorithm may find that a pivot element is not invertible.
In this case, the systematic form we seek does not exist and the algorithm has
to loop back to the “Block permutation” step. Fortunately, the chance of this is
small. The probability that the matrix is nonsingular is
k−
1
kt
+
i,j
←−
1
/p
k−j
,which
approaches a constant (to be determined numerically) for large
k
. This constant
is different for each
p
but tends to 1 for large
p
. In order to avoid redundancy,
this subroutine omits those columns of the systematic form, which we know to
be the identity matrix.
The third and final subroutine
QMSignature
will simply extract the
monoidic signature of each block, i.e., its first column. For the whole quasi-
monoidic matrix, this simply amounts to extracting each
b
-th column. This
concludes our description of the algorithm.
j
=0
1
−
