Cryptography Reference
In-Depth Information
that; the distribution is much more similar to what holds for binary codes, since
the difference patterns only fail to be binary because of the overall magnitude.
The error correcting strategy described in [BLM10] (algorithm 1) benefits from
this observation, which allows for the correction of
t
errors with high probability
as long as all error magnitudes are equal. The entries on Table 1 describe codes
suitable for McEliece or Niederreiter encryption [Nie86].
One can argue that minimizing keys may not be the best way to reduce
bandwidth occupation. After all, usually one expects to exchange encrypted
messages considerably more often than certified keys, so it pays to minimize the
encryption overhead per message instead. This is particularly easy to achieve
using the Niederreiter cryptosystem, as long as the adopted codes yield short
syndromes. Table 2 lists suggestions for codes that satisfy these requirements
(including protection against structural interpolation attacks), without incurring
unduly long keys. One sees that the choice for short syndromes often implies
longer codes for larger characteristics.
Table 3 describes codes suitable for parallel CFS digital signatures [Fin10,
BCMN10]. The signature size is slightly smaller than the product of the the
syndrome size by the number of parallel signatures, and signing times are
O
(
t
!).
Quasi-monoidic codes in larger characteristics yield either shorter keys and sig-
natures than in the binary case, or else considerably shorter signing times due
to smaller values of
t
.
7E ency
We will show that for all groups
A
relevant to cryptography, the matrix-vector
products involving
A
-adic matrices can be computed in
O
(
N
)operationswitha
multidimensional discrete Fourier transform. As we have seen in Corollary 1, all
relevant groups have the form
A
=
p
. Recall that the ring of
A
-adic matrices
over
R
is isomorphic to the monoid ring
R
[
A
] (hence the name, 'monoidic' ma-
trices and codes). In the following lemma, we show that this has the structure
of a multivariate polynomial quotient ring.
Z
p
]
=
R
[
x
1
,...,x
d
]
/
x
1
−
Lemma 1.
Let
R
be a commutative ring, then
R
[
Z
1
,...,x
d
−
1
.
p
. Consider the following
R
-bases for the left and right ring re-
spectively, left we have [
χ
(
a
1
,...,a
d
)
]
a∈A
and right [
x
a
1
Proof.
Let
A
=
Z
x
a
d
k
···
]
a∈A
,where
a
ranges
1
through all
d
-tuples in
A
for each ring.
We define
ψ
for all basis elements of the left ring to be
ψ
(
χ
(
a
1
,...,a
k
)
)=
x
a
1
1
x
a
k
. This can be extended canonically to an
R
-module isomorphism on
the whole ring. It only remains to check that
ψ
respects multiplication. It suces
to check this for the generators, so let
a, b
···
∈
A
then
ψ
(
χ
b
)=(
x
a
1
1
x
a
d
k
(
x
b
1
x
b
k
)mod
x
1
−
1
,...,x
d
−
ψ
(
χ
a
)
·
···
)
·
···
1
=
x
a
1
+
b
1
mod
p
1
x
a
d
+
b
k
mod
p
d
=
ψ
(
χ
(
a
1
+
b
1
mod
p,...,a
d
+
b
d
mod
p
)
)=
ψ
(
χ
a
·
···
χ
b
)
