Cryptography Reference
In-Depth Information
. Table 4.1 shows that
n
m
systems is |EI
m
|, which is much smaller than
| <
2
n
m
|EI
m
for most values of l,n, and m. Thus, the independence criteria
in Step 2 reduces the number of trials inside the “if” block of Step 2 by a
substantial factor.
The following Theorem quantifies the amount of time required to recover
the key due to the algorithm.
Theorem 4.2.6. The time complexity of the RecoverKey algorithm is given
by
n
m
n
l
m
2
m
2
+
2
8(l−m)
O
+|EI
m
|
,
where |EI
m
| is given by Theorem 4.2.2.
Proof: According to Proposition 4.2.3, for a complete run of the algo-
rithm, checking the condition at Step 2 has O(m
2
n
m
) time complexity.
| times. Among them,
finding the solution in Step 4 involves O(m
2
) many addition/subtraction op-
erations (the equations being triangular in form). By Proposition 4.2.4, each
system can yield at the most O(⌊
l
Further, the Steps 3, 4 and 5 are executed |EI
m
⌋) many solutions for the key. After the
solution is found, Step 5 involves 2
8(l−m)
many trials. Thus, the total time
consumed by the Steps 3, 4 and 5 for a complete run would be
n
l
m
2
+
2
8(l−m)
O
|EI
m
|
.
Hence, the time complexity of the RecoverKey algorithm is given by
n
m
n
l
m
2
m
2
+
2
8(l−m)
O
+|EI
m
|
.
Next, we estimate the probability of getting a set of independent correct
equations when we run the above algorithm. Suppose for the given system
of equations S
r
[y] = f
y
, y = 0,1,..., n − 1, m ≤ n ≤ r ≤ N, c
r,n
de-
notes the number of independent correct equations and p
r
(y
1
,y
2
,...,y
τ
) de-
notes the joint probability that the τ equations corresponding to the indices
{y
1
,y
2
,...,y
τ
} are correct and the other n − τ equations corresponding to
the indices {0,1,...,n − 1}\{y
1
,y
2
,...,y
τ
} are incorrect. Then one can
immediately state the following result.
n
Proposition 4.2.7. P(c
r,n
≥ m) =
p
r
(y
1
,y
2
,...,y
τ
).
τ=m
{y
1
,y
2
,...,y
τ
}∈EI
τ
|number of terms of the form p
r
(y
1
,y
2
,...,y
τ
)
to get the probability that exactly τ equations are correct, i.e.,
Proof: One needs to sum|EI
τ
P(c
r,n
= τ) =
p
r
(y
1
,y
2
,...,y
τ
).
{y
1
,y
2
,...,y
τ
}∈EI
τ
