Cryptography Reference
In-Depth Information
simple polynomial evaluation method. Unfortunately, in our case
n<<
2
m
such
that the complexity of the Chien search becomes
(2
16
t
) which is enormous
compared to the complexity of the simple polynomial evaluation method. An-
other disadvantage of both the Berlekamp trace algorithm and the Chien search
is that after root extraction the found roots have to be located within the sup-
port sequence to identify error positions. That is not the case when evaluating
the error locator polynomial on the support set directly. In this case we know the
positions of the elements
L
i
and can correct errors directly by flipping the cor-
responding bits in the ciphertext. The only algorithm which actually decreases
the computation costs of the simple evaluation method in the case of punctured
codes is the Horner scheme [12]. The complexity of the Horner scheme does not
depend on the extension degree of the field but on the number of possible root
candidates, which is
n
. In addition, as the Horner scheme evaluates the error lo-
cator polynomial on the support set
L
∗
, the root positions within
L
∗
are known
such that errors can be corrected more eciently. Hence, we have implemented
this root finding algorithm. After a root
L
i
O
·
of
σ
(
x
) has been found we perform
L
i
). We observed that the polynomial
the polynomial division of
σ
(
x
)by(
x
−
L
i
) can be performed sequentially reusing values computed in
previous iteration steps. In the first step we compute the coecient
y
t−
2
of the
searched polynomial
y
(
x
). In every iteration step
j
we use the previous coecient
y
t−j
+1
to compute
y
t−j
=
y
t−j
+1
L
i
+
σ
t−j
. The whole procedure requires
t
division by (
x
−
−
3
L
i
.
The main advantage of performing polynomial division each time a root has
been found is that the degree of the error locator polynomial decreases. Hence,
the next evaluation steps require less operations.
multiplications and
t
−
2 additions to divide a degree-
t
polynomial by
x
−
γ
4.3
Implementation of the KIC-
For the implementation of Kobara-Imai's specific conversion
γ
[13] two param-
eters have to be chosen: the length of the random value
r
and the length of the
public constant
Const
. The length of
r
should be equal to the output length of
the used hash function. Here we choose the Blue Midnight Wish (BMW) hash
function, because of the availability of a fast assembly implementation. As we
have
|
r
|
= 256 and
|
Const
|
= 160, the message to be encrypted should be of the
|≥
log
2
t
+
k
+
length
= 1281 bits. Hence, we encrypt messages
of length 1288 bits = 161 bytes. In this case the data redundancy is even below
of that of the McEliece scheme without conversion: 1288
/
2304
|
m
|
r
|−|
Const
|
1280
/
2304.
The first steps of the KIC-
γ
encryption function are the generation of a ran-
dom seed
r
for the function
Gen
(
r
), as well as the one-time-pad encryption of the
message
m
padded with the public constant
Const
and the output of
Gen
(
r
).
The result is a 1288 + 160 = 1448 bits = 181 bytes value
y
1
. In the next step
the hash value of
y
1
is added to the random seed
r
by the xor operation to
obtain the value
y
2
.
k
= 1280 bits from (
y
2
||
≤
Y
1
) are used as input for McEliece
and from the remaining 424 bits the error vector is constructed by the constant
weight encoding function
Conv
[22,11].
