Cryptography Reference
In-Depth Information
In addition to that, we briefly describe two techniques how additional struc-
ture of the underlying code or the solution can be exploited to increase the
algorithm eciency.
Organization of the paper.
We recall some preliminaries and notations from
code-based cryptography in Section 2. In the subsequent Section 3 we present our
generalized algorithm and the corresponding statistical properties. Experimental
results are given in Section 4, and we conclude in Section 5.
2 Preliminaries and Notation
In this section, we recall standard definitions from code-based cryptography.
Definition 1 (Linear code).
Alinearcode
C
of length
n
and dimension
k
over a finite field
F
q
is defined as a
k
-dimensional subspace of the
n
-dimensional
F
q
vector space
.
C
is denoted a
(
n,k
)
code over
F
q
.
Definition 2 (Generator and parity check matrix).
Amatrix
G
∈
F
k
×
n
q
{
mG
:
m
∈
F
q
}
of full if rank is call if generator matrix for an
(
n,k
)
code
C
if
C
=
.
(
n
−
k
)
×
n
q
A parity check matrix for
C
is any full l rank matrix
H
∈
F
such that
{
x
∈
F
q
:
Hx
T
=0
C
=
}
. A parity check matrix
H
is a generator matrix for the
C
⊥
.
dual code
Definition 3 (Hamming distance).
The Hamming weight
wt(
x
)
of a vector
x
is defined as the number of non-zero entries, and the Hamming distance
d
(
x,y
)
between two vectors
x
and
y
is
wt(
x
−
y
)
. The minimum distance
d
of a code
C
is given by
d
:= min
x
∈C\{
0
}
wt(
x
)
.Let
t
:=
(
d
−
1)
/
2
,then
C
is also denoted
an
(
n,k,t
)
code.
Definition 4 (General decoding problem).
The general decoding problem
is defined as fol lows: Given a vector
c
∈
F
q
and an
(
n,k,t
)
code
C
over
F
q
, find
x
∈C
such that
d
(
c,x
)
is minimal. If
d
(
c,x
)
≤
t
, then this decoding is unique.
For any vector
h
, the entry at position
i
is denoted by
h
i
.Wewrite
H
·
i
for the
i
i-th column of a matrix
H
.Let
I
⊆{
,then
H
·
I
denotes the submatrix
of
H
consisting of the columns indexed by
I
. Similarly,
h
I
1
,...,n
}
denotes the vector
consisting of the corresponding entries of
h
.
3 Statistical Decoding
The idea of statistical decoding is as follows: After receiving a codeword with
error
c
=
mG
+
e
,where
m
and
e
are unknown, a precomputed set
H
w
⊆C
⊥
is
used as a mask to obtain information about
e
.Since
GH
w
=0,wehave
H
w
c
T
=
H
w
e
T
.
