Cryptography Reference
In-Depth Information
11.5 Constructions of Optimal Systematic Robust Codes
There is a strong relationship between robust codes, nonlinearity, and nonlinear
functions since all robust codes are nonlinear. The parameters of systematic robust
codes depend on the nonlinearity of the encoding function of the codes.
We first review some basic definitions and properties of nonlinearity; a good
survey of nonlinear functions can be found in [80].
Let
f
be a function that maps elements from
GF
2
k
2
r
(
)
to
GF
(
)
.
2
k
2
r
f
:
GF
(
)
→
GF
(
)
:
a
→
b
=
f
(
a
).
The nonlinearity of the function can be measured by using derivatives
D
a
f
(
x
)
=
f
(
x
+
a
)
+
f
(
x
)
.Let
P
f
=
max
max
Pr
(
D
a
f
(
x
)
=
b
),
2
r
2
k
b
∈
GF
(
)
0
=
a
∈
GF
(
)
where
Pr
denotes the fraction of cases when
E
occurred. The smaller the value
of
P
f
, the higher the corresponding nonlinearity of
f
. For linear functions,
P
f
(
E
)
=
1.
2
k
2
r
Definition 11.5
A binary
function f
:
GF
(
)
→
GF
(
)
has perfect nonlinearity
1
iff
P
f
=
2
r
.
2
k
2
r
Theorem 11.2
[213] Let f be a nonlinear function that maps G F
(
)
to G F
(
)
where k
≥
r ; the set of vectors resulting from the concatenation of
x
1
,
x
2
:
(
x
1
,
x
2
=
f
(
x
1
))
2
k
2
r
∈
(
)
∈
(
)
where x
1
GF
and x
2
GF
, forms a robust systematic code with
2
k
P
f
,n
2
k
.
=
=
+
=
R
k
r and M
2
k
2
r
Proof
The error
e
=
(
y
1
,
y
2
)
with
(
y
1
∈
GF
(
),
y
2
∈
GF
(
))
will be masked
2
k
iff
f
y
2
.
From Theorem 11.1, there are at least 2
n
−
k
errors which will be detected with
probability 1 by any systematic code with length
n
and
k
information bits. Thereby
a more strict bound can be derived for systematic codes. In this case we have
(
x
1
+
y
1
)
+
f
(
x
1
)
=
y
2
,
x
1
∈
GF
(
)
, which is exactly when
D
y
1
f
(
x
1
)
=
M
2
2
n
2
n
−
k
−
M
≤
R
(
−
).
(11.4)
Corollary 11.2
A systematic robust code
2
k
2
r
C
={
(
x
1
,
x
2
=
f
(
x
1
))
|
x
1
∈
GF
(
),
x
2
∈
GF
(
)
}
is optimum if the encoding function f is a perfect nonlinear function.
