Cryptography Reference
In-Depth Information
Description
Parameter Restriction
Description
Parameter Restriction
Field char
p
prime
t
/m
Goppa roots
p
s
Base field
q
Goppa multiplicity
r
< /
(
tm
)
Qq
m
Extension field
Blocksize
gcd(
t, N
)
b
Np
d
≤ Q/p
Code length
n
b
<N
Group order
Fig. 1.
Parameters for quasi-monoidic GS codes. Let
s, m, >
0. For brevity, we will
focus on the case where
s
= 1 (smallest base field size),
r
=
p −
1 (wild case).
MonoidCauchy
(
p, Q, d
):
1.
F ←−
F
Q
\{
0
}
2.
h
(0)
←− U
(
F
)
3.
For
i
=1
,...,d
:
4.
F ←−
F
Q
\
(
F
p
h
(0) +
F
p
h
(
b
1
)+
···
+
F
p
h
(
b
i−
1
))
5.
←− U
(
F
)
6.
For
c
1
,...,c
d
∈
F
p
:
7.
h
(
c
1
b
1
+
···
+
c
d
b
d
)
←− c
1
h
(
b
1
)+
···
+
c
d
h
(
b
d
)
−
(
c
1
+
···
+
c
d
−
1)
h
(0)
8.
Output
(
h
(0)
−
1
,h
(
a
1
)
−
1
,...,h
(
a
p
d
−
1
)
−
1
)
h
(
b
i
)
A
-adic Cauchy sequences, where
A
=
{
0
,a
1
,...,a
p
d
−
1
}
has set of
Fig. 2.
Choosing
generators
b
1
,...,b
d
.
QuasiMonoidic
(
...
):
1.
h ←−
MonoidCauchy
(
p, Q, d
);
ω ←− U
(
F
Q
)
2.
For
i
=0
,...,t−
1:
β
i
←−
(
h
(
a
i
))
−
1
+
ω
“Goppa roots”
i
=0
,...,N −
1:
γ
i
←−
(
h
(0))
−
1
−
(
h
(
−a
i
))
−
1
+
ω
3.
For
“Goppa support”
4.
τ ←− U
(
S
N/
b
)
“Block permutation”
5.
π
0
,...,π
−
1
←− U
(
{
0
,...,
b
−
1
}
)
“Support permutations”
6.
σ
0
,...,σ
−
1
←− U
(
F
q
)
“Scaling”
7.
For
i
=0
,...,−
1:
γ
i
←−
(
γ
τ
(
i
)
b
,...,γ
τ
(
i
)
b
+
b
−
1
)
“Select blocks”
8.
For
i
=0
,...,−
1:
γ
i
←− γ
i
M
(
χ
a
π
i
)
“Permute support”
9.
H ←−
[
CL
(
β,γ
0
,r
)
σ
0
|···|CL
(
β,γ
−
1
,r
)
σ
−
1
]
“Parity-check matrix”
10.
H ←−
QMTrace
(
q,
b
,H
)
11.
H ←−
QMGauss
(
b
,H
)
12.
H ←−
QMSignature
(
b
,H
)
13.
Output
private
β,γ
0
,...,γ
−
1
,σ
0
,...,σ
−
1
; public
H
Fig. 3.
Choosing quasi-monoidic GS codes with private and public description. Here,
S
N/
b
is the group of permutations on
{
0
,...,N/
b
−
1
}
and
χ
a
π
i
is the characteristic
function of the group element
a
π
i
.