Cryptography Reference
In-Depth Information
where:
f
(
u, v
)=min
{|
u
−
v
|
,k
−|
u
−
v
|}
(7.6)
Function
f
is introduced to take into account the circular nature of the
addresses. Finally, we call
S
min
thesmallestofthevaluesof
S
(
j
1
,j
2
)
, for all
the possible pairs
j
1
and
j
2
:
S
min
=min
j
1
,j
2
{
S
(
j
1
,j
2
)
}
(7.7)
It is proved in [7.19] that an upper bound of
S
min
is:
sup
S
min
=
√
2
k
(7.8)
This upper bound is only reached in the case of a regular permutation and
with conditions:
P
=
P
0
=
√
2
k
(7.9)
and:
P
0
2
k
=
mod
P
0
(7.10)
Let us now consider a sequence of any weight that, after permutation, can be
written:
k−
1
d
(
D
)=
a
j
D
j
(7.11)
j
=0
where
a
j
can take the binary value 0 (no error) or 1 (one error) and, before
permutation:
k−
1
k−
1
a
i
D
i
=
d
(
D
)=
a
Π(
j
)
D
Π(
j
)
(7.12)
i
=0
j
=0
We denote
j
min
and
j
max
the
j
indices corresponding to the first and last non-
null values
a
j
in
d
(
D
)
. Similarly, we define
i
min
and
i
max
for sequence
d
(
D
)
.
Then, the regular permutation satisfying (7.9) and (7.10) guarantees the prop-
erty:
i
min
)
>
√
2
k
(7.13)
This is because
d
(
D
)
and
d
(
D
)
, both considered between min and max indices,
contain at least 2 bits whose accumulated spatial distance, as defined by (7.5),
(
j
max
−
j
min
)+(
i
max
−
is maximum and equal to
√
2
k
. We must now consider two cases: