Cryptography Reference
In-Depth Information
y,w
≈
q
−
1
F
q
, we can now assume that
v
++
In the case of codes over
q
|
H
w
|
.Thus,
the probability
P
that a certain
δ
satisfies the first condition is
(
q
−
t
1)
|
H
w
|
=
Φ
(
δ/σ
++
w
)
t
=
Φ
P
δ
,
qp
++
−
p
++
(1
)
w
w
where
Φ
refers to the standard normal distribution. Therefore, we get the fol-
lowing condition on
|
H
w
|
:
n
w
(
q
−
1
/t
))
2
δ
−
2
q
q
−
1)
w
q
−
k
.
(10)
(
Φ
−
1
(
1
p
++
−
p
++
w
P
(1
)
≤|
H
w
|≤
w
We can assume that half the values of
v
j
,for
j
the non-error positions, are below
the mean of
p
++
w
v
++
y,w
.Any
δ
satisfying both conditions above will probably be
|
p
++
w
−
q
++
. Thus, we expect a success probability of 0
.
95
t
smaller than
w
|
when
a set of size
p
++
w
−
p
++
w
2
.
72
q
q
−
(1
)
|
H
w
|≈
1
·
(
p
++
w
−
q
++
)
2
w
q
2(
q
−
1)
is used (since
Φ
−
1
(0
.
95)
2
≈
2
.
72). Note that this size is a factor of
greater
compared with the binary case.
In Table 1 we present experimental results obtained using our implementation
in Maple.
Table 1.
Experimental results of using Algorithm 3 to decode
t
errors in an (
n,k
)
code over
F
q
. We ran several thousand decoding attempts, each using a sample of size
|
H
|
=
|
w
=
b
H
w
|
= 100.
(
n,k,t
)
q b B
Successful decodings
3
44
46
30.6%
5
51
53
29.8%
7
56
58
36.1%
(64
,
40
,
4)
11
58
60
35.8%
13
59
61
42.7%
53
61
63
29.4%
3
84
88
18.1%
5 100 104
22.9%
7 108 112
23.0%
(128
,
72
,
8)
11 115 119
32.1%
13 117 121
27.8%
53 123 127
37.8%
The results show that in many cases our algorithm decodes successfully, even
though the number of sample vectors
was not very large. Also, the success
probability can be increased by using a larger weight spectrum
B
−
b
. However,
this increases the complexity of testing all binary combinations
v
+
.Notethat
|
H
|
