Cryptography Reference
In-Depth Information
A natural choice for the wild set is the set of equivalence classes coming from elements
of the form
hg
x
with
N/
2. Note that the size of the wild set now depends
on the discrete logarithm problem: if
h
−
N/
2
<x
≤
g
0
=
=
1 then the wild set has 1
+
N/
2 elements
g
N/
2
then the wild set has
N
elements. Even more confusingly, sampling from
the wild set by uniformly choosing
x
does not, in general, lead to uniform sampling from
the wild set. This is because the equivalence class
while if
h
=
hg
x
,
(
hg
x
)
−
1
can arise in either one or
two ways, depending on
h
. To analyse the algorithm it is necessary to use a non-uniform
version of the birthday paradox (see, for example, Galbraith and Holmes [
206
]). The main
result of [
211
]
is
an algorithm that solves the DLP in heuristic average-case expected
(1
.
36
{
}
o
(1))
√
N
group operations.
+
14.8 Parallel collision search in other contexts
Van Oorschot and Wiener [
423
] propose a general method, motivated by Pollard's rho
algorithm, for finding collisions of functions using distinguished points and parallelisation.
They give applications to cryptanalysis of hash functions and block ciphers that are beyond
the scope of this topic. But they also give applications of their method for algebraic meet-
in-the-middle attacks, so we briefly give the details here.
First, we sketch the parallel collision search method. Let
f
:
S
→
S
be a function
mapping some set
S
of size
N
to itself. Define a set
D
of distinguished points in
S
.
Each client chooses a random starting point
x
1
∈
S
f
(
x
n
) until it hits a
distinguished point and sends (
x
1
,x
n
,n
) to the server. The client then restarts with a new
random starting point. Eventually, the server gets two triples (
x
1
,x,n
) and (
x
1
,x,n
)for
the same distinguished point. As long as we do not have a “Robin Hood”
13
(i.e., one walk
is a subsequence of another), the server can use the values (
x
1
,n
) and (
x
1
,n
) to efficiently
fi
nd a c
ollision
f
(
x
)
, iterates
x
n
+
1
=
=
f
(
y
) with
x
=
y
. The expected running time for each client is
√
πN/
2
/N
P
+
1
/θ
, using the notation of this chapter. The storage requirement depends
on the choice of
θ
.
We now consider the application to meet-in-the-middle attacks. A general meet-in-the-
middle attack has two sets
S
1
and
S
2
and functions
f
i
:
S
i
→
R
for
i
=
1
,
2. The goal is to
find
a
1
∈
S
1
and
a
2
∈
S
2
such that
f
1
(
a
1
)
f
2
(
a
2
). The standard solution (as in baby-step-
giant-step) is to compute and store all (
f
1
(
a
1
)
,a
1
) in an easily searched structure and then
test, for each
a
2
∈
S
2
, whether
f
2
(
a
2
) is in the structure. The running time is #
=
S
1
+
#
S
2
function evaluations and the storage is proportional to #
S
1
.
The idea of [
423
] is to phrase this as a collision search problem for a single function
f
.For
simplicity we assume that #
S
1
=
#
S
2
=
N
. We write
I
={
0
,
1
,...,N
−
1
}
and assume
one can construct bijective functions
σ
i
:
I
→
S
i
for
i
=
1
,
2. One defines a surjective map
ρ
:
R
→
I
×{
1
,
2
}
13
Robin Hood is a character of English folklore who is expert in archery. His prowess allows him to shoot a second arrow on
exactly the same trajectory as the first so that the second arrow splits the first. Chinese readers may substitute the name Houyi.
