Cryptography Reference
In-Depth Information
Since we sum up
Θ
(
h
)(insteadof
h
), the variance of
v
remains unchanged, i.e.
σ
++
w
=
p
++
w
−
p
++
w
)
v
++
y,w
(1
.
Algorithm 3 is the generalized version for statistical decoding over
F
q
.
Algorithm 3.
Generalized algorithm for statistical decoding over a non-binary
field
F
q
.
INPUT: Generator matrix
G
for an (
n,k,t
)code
C
,
H
=
w
=
b
H
w
⊆C
⊥
and
c
∈
F
q
OUTPUT:
m
∈
F
q
such that wt(
c
−
mG
)
≤
t
Let
1
=(1
,...,
1)
∈{
0
,
1
}
n
for
w
=
b
→
B
do
(
σ
++
w
)
2
=
p
++
w
(1
−
p
++
w
)
v
y,w
(
σ
−−
w
)
2
=
p
−−
w
(1
−
p
−−
w
)
v
y,w
Let
H
w
=
{
h
∈
H
w
:
hc
T
=0
}
and
H
w
=
H
w
\
H
w
v
w
←
h
∈
H
w
(
Θ
(
h
)
−
p
++
w
1
)
/σ
+
w
∈
R
n
v
w
+
B
←−
h
∈
H
w
(
Θ
(
h
)
−
p
−−
w
1
)
/σ
−
w
∈
R
n
end for
for
all binary combinations
v
+
of the different
v
i
do
Choose
I
=
{
positions of the
k
smallest entries of
v
}
s.t.
G
·
I
is invertible
m
←
c
I
G
−
1
·
I
if
wt(
c
−
mG
)
≤
t
then
Return
m
end if
end for
3.3 Exploiting Additional Structure
Many types of additional structure have been proposed in code-based cryptog-
raphy in order to reduce the public key size or to increase e
ciency. Algorithm 3
allows to exploit various types of such structures. We will give two examples and
briefly describe the corresponding techniques:
(Quasi-)cyclic matrices.
In the last years, quasi-cyclic (QC) matrices have
been used in many proposals in code-based cryptography (e.g. [2,5]). A QC ma-
trix is a block matrix, where each block is cyclic. A cyclic matrix is a matrix
where every row is a cyclic shift of the previous. Since the first row of every
block of a QC matrix generates the full block, this allows a compact representa-
tion, decreasing the size of the public key. We will describe the technique using
cyclic matrices, but it applies to QC matrices as well, and also to other types of
structured matrices like quasi-dyadic matrices.
Let
γ
(
v
) denote the cyclic shift of vector
v
. A cyclic code
allows to choose
a cyclic parity check matrix
H
. Therefore, for every
h
∈C
⊥
,
γ
(
h
)
C
∈C
⊥
.
