Cryptography Reference
In-Depth Information
Secondly, we note that the definition of odd error detection needs to be
changed, since
hc
T
∈
F
q
\{
0
}
as well: We define odd error detection at bit
i
as the case when
hc
T
=0and
h
i
= 0. The reason is that since
:
h
(
xc
)
T
=
x
(
hc
T
)and
hc
T
⇔
x
(
hc
T
)
∀
x
∈
F
q
\{
0
}
=0
=0
,
(1)
all values of
hc
T
have the same probability, and they are independent of the
value of
h
i
.
Finally, the original algorithm adds up the vectors
h
in order to compute the
relative frequencies of
p
+
w
and
q
+
w
F
q
would disturb these
frequencies because entries of
h
greater than 1 bias the computation. Instead,
we add
Θ
(
h
)=(
θ
(
h
1
)
,...,θ
(
h
n
−
k
)), where
. Doing the same over
0
x
=0
1 e
.
θ
:
F
q
→
F
q
,x
→
In order to proceed, we introduce some notation. Consider the case where
e
and
a vector
h
are both non-zero in exactly
i
bits. In contrast to the binary case, we
don't have the equivalence
i
even
⇔
hc
T
= 0. Since every non-zero value of
hc
T
has the same probability (and occurs the same number of times when
H
w
=
C
⊥
),
the quantities
(
q,i
)=
(
q
−
1)
i
C
(2)
q
(
q
−
1)
i
C
(
q,i
)=(
q
−
1)
i
−
·
(
q
−
1)
(3)
q
reflect the relative frequencies of non-zero and zero values of
hc
T
, respectively,
where
denotes rounding to the nearest integer. They are well-defined since
1)
i
/q
∈
N
(
q
−
can only occur for
q
=2.
Using equation (1), we can calculate the respective probabilities.
+
{
0
.
5
}
=
j
=1
C
(
q,j
)
t
−
1
j
−
1
n
−
t
(
q
−
1)
w
−
j
w
−
j
p
++
w
(
q,j
)
j
n
−
t
(
q
−
(4)
j
=1
C
1)
w
−
j
w
−
j
(
q,j
)
t
−
1
j
n
−
t
w
−
j
(
q
−
=
j
=1
C
1)
w
−
j
q
++
w
(
q,j
)
j
n
−
t
(
q
−
(5)
j
=1
C
1)
w
−
j
w
−
j
=
j
=0
C
(
q,j
)
t
−
1
j
−
1
n
−
t
(
q
−
1)
w
−
j
w
−
j
p
−−
w
(
q,j
)
j
n
−
t
(
q
−
(6)
j
=0
C
1)
w
−
j
w
−
j
=
j
=0
C
(
q,j
)
t
−
1
n
−
t
w
−
j
(
q
−
1)
w
−
j
j
q
−−
w
(
q,j
)
j
n
−
t
w
−
j
(
q
−
(7)
j
=0
C
1)
w
−
j
Consequently, we redefine
v
++
y,w
|{
h
∈
H
w
:
hc
T
=
=0
}|
(8)
v
−−
y,w
|{
h
∈
H
w
:
hc
T
=0
=
}|
(9)
