Cryptography Reference
In-Depth Information
two of them to be convenient. These are Pointcheval's generic conversion [19]
and Fujisaki-Okamoto's generic conversion [8]. Both convert partially trapdoor
one-way functions (PTOWF)
1
to public key cryptosystems fulfilling the CCA2
indistinguishability.
The main disadvantage of both conversions is their high redundancy of data.
Hence, Kobara and Imai developed three further specific conversions (
α
,
β
,
γ
)
decreasing data overhead of the generic conversions even below the values of
the original McEliece PKCs for large parameters. Their work shows clearly that
the Kobara-Imai's specific conversion
γ
(KIC-
γ
) provides the lowest data redun-
dancy for large parameters
n
and
k
. In particular, for parameters
n
= 2304 and
k
= 1280 used in this work for the construction of the quasi-dyadic McEliece-
type PKC the data redundancy of the converted variant is even below that of
the original scheme without conversion.
4
Implementational Aspects
In this section we discuss aspects of our implementation of the McEliece variant
based on quasi-dyadic Goppa codes of length
n
= 2304, dimension
k
= 1280,
and correctable number of errors
t
= 64 over the subfield
F
2
16
providing a
security level of 80 bit. Target platform is the ATxmega256A1, a RISC micro-
controller frequently used in embedded systems. This microcontroller operates
at a clock frequency of up to 32 MHz, provides 16 Kbytes SRAM and 256 Kbytes
Flash memory.
F
2
of
4.1 Field Arithmetic
To implement the field arithmetic on an embedded microcontroller most e-
ciently both representations of the field elements of
F
q
, polynomial and expo-
nential, should be precomputed and stored as
log-
and
antilog
table, respectively.
Each table occupies
m
2
m
bits of storage. Unfortunately, we cannot store the
whole log- and antilog tables for
·
F
2
16
because each table is 128 Kbytes in size.
Neither the SRAM memory of the ATXmega256A1 (16 Kbytes) nor the Flash
memory (256 Kbytes) would be enough to implement the McEliece PKC when
completely storing both tables. Hence, we make use of
tower field arithmetic
.E-
cient algorithms for arithmetic over tower fields are proposed in [2], [17], and [18].
It is possible to view the field
F
2
2
k
as a field extension of degree 2 over
F
2
k
.Thus,
we can consider the finite field
F
2
8
constructed by an
irreducible polynomial
p
(
x
)=
x
2
+
x
+
p
0
where
p
0
∈
F
2
8
.If
β
is a root of
p
(
x
)
in
F
2
16
=
F
(2
8
)
2
as a tower of
F
2
16
then
F
2
16
can be represented as a two dimensional vector space over
F
2
8
and an element
A
∈
F
2
16
can be written as
A
=
a
1
β
+
a
0
where
a
1
,a
0
∈
F
2
8
.To
perform field arithmetic over
F
2
8
and
use them for fast mapping between exponential and polynomial representations
F
2
16
we store the log- and antilog tables for
1
A PTOWF is a function
F
(
x, y
)
→ z
for which no polynomial time algorithm exists
recovering
x
or
y
from their image
z
alone, but the knowledge of a secret enables a
partial inversion, i.e., finding
x
from
z
.
