Cryptography Reference
In-Depth Information
Fig. 11.2
Projective plane of
4
order 2
5
6
2
0
3
1
11.4 Bounds, Optimality, and Perfect Robust Codes
Based on the above definitions of robust codes it is possible to derive the following
main property for an
R
-robust code.
Property 11.1
If the code C is R-robust, then in the multiset S
C
={
x
j
+
x
i
|
x
i
,
x
j
∈
C
,
x
i
=
x
j
}
, any element appears at most R times.
Robust codes are optimal if they have the maximum number of codewords
M
for
agiven
R
and length
n
. From Property 11.1, a relation on
R
,
n
and
M
of the code
can be established:
M
2
2
n
−
M
≤
R
(
−
1
).
(11.2)
Definition 11.2
(
Perfect Robust Code
)An
R
-robust code with
n
bits and
M
code-
words satisfying
M
2
2
n
−
M
=
R
(
−
1
)
is
perfect
.
Perfect robust codes correspond to extensively studied combinatorial structures
known as difference sets and symmetric designs [206].
Definition 11.3
(
Difference Set
)Let
G
be a group of order
v
, and
C
an
M
-subset of
G
. Then
C
is called a
(
v
,
M
,
R
)
-difference set if the list of differences
S
=
(α
−
β
:
α, β
∈
C
,α
=
β)
contains each nonzero element of
G
exactly
R
times.
q
n
q
n
Clearly,
(
,
M
,
R
)
difference sets in
GF
(
)
are exactly perfect
q
-ary
R
-robust
codes of length
n
and
M
codewords.
Despite extensive research on the combinatorial structures it is still not known in
the general case for which parameters such difference sets and hence perfect robust
codes exist, and we note that the perfect robust codes based on the known difference
sets have high complexity of decoding (detecting for a given
x
whether
x
∈
C
or
x
∈
C
). A good summary of existing difference sets can be found in [42].
Example 11.1
[110] is an example of a classic
combinatorial balanced-incomplete design [42] that generates a difference set with
The projective geometry
PG
(
m
,
q
)
