Cryptography Reference
In-Depth Information
in the past. In other words, our attack does not compromise the security of the
whole KKS scheme. It just points out that the region of weak parameters is
really much larger than previously thought.
2
Terminology and Notation
In the whole paper
q
denotes some prime power and we denote by
F
q
the finite
field with
q
elements. Let
n
be a non-negative integer. The set of integers
i
such
that 1
i
n
is denoted by [1
···
n
]. The cardinality of a set
A
is denoted by
|
=(
y
1
,...,y
m
)is
denoted by (
x
||
y
)
de
=(
x
1
,...,x
n
,y
1
,...,y
m
). The support
supp
(
A
|
x
=(
x
1
,...,x
n
)and
y
. The concatenation of the vectors
q
x
)of
x
∈
F
is
the set of
i
's such that
x
i
=0.The
(Hamming) weight
|
x
|
is the cardinality of
supp
(
x
). For a vector
x
=(
x
i
) and a subset
I
of indices of
x
,wedenoteby
x
I
its restriction to the indices of
I
,thatis:
de
=(
x
i
)
i∈I
.
x
I
We will also use this notation for matrices, in this case it stands for the submatrix
formed by the columns in the index set, i.e. for any
k
×
n
matrix
H
de
=(
h
ij
)
1
i
k
j∈J
H
J
.
n
q
A linear code
C
of type [
n, k, d
]over
F
q
is a linear subspace of
F
of dimension
de
=min
k
and minimum distance
d
where by definition
d
{|
x
|
:
x
∈ C
and
x
are
codewords
. A linear code can be defined either
by a parity check matrix or a generator matrix. A
parity check matrix
=
0
}
. The elements of
C
H
for
C
is an (
n
−
k
)
×
n
matrix such that
C
is the right kernel of
H
:
n
q
c
T
C
=
{
c
∈
F
:
H
=0
}
T
denotes the
transpose
of
where
x
x
. A generator matrix
G
is a
k
×
n
matrix
formed by a basis of
C
.Wesaythat
G
is in
systematic
form if there exists a set
de
=
q
T
T
.
J
such that
G
J
=
I
k
.The
syndrome
s
by
H
of
x
∈
F
is defined as
s
Hx
q
, finds a
A
decoding
algorithm for
H
is an algorithm such that, given
s
in
F
vector
e
of
minimum
weight whose syndrome is
s
.
3
The Kabatianskii-Krouk-Smeets Signature Scheme and
Its Variant
This section is devoted to the description of two code-based signature schemes
proposed in [KKS97] and more recently in [BMJ11], where the latter can be
viewed as a “noisy” version of the former [KKS97]. Our presentation presents
the main ideas without giving all the details which can be found in the original
papers. We first focus on the scheme of [KKS97] whose construction relies on
the following ingredients:
