Cryptography Reference
In-Depth Information
5.2 Hardness of the Underlying Assumptions
Given an SSI (respectively, SSCDH) solver, it is trivial to solve SSCDH (respec-
tively, SSDDH). There is of course no known reduction in the other direction,
and given that the corresponding question of equivalence for discrete logarithms
and Die-Hellman has not yet been completely resolved in all cases, it is rea-
sonable to assume that the question of equivalence of SSI, SSCDH, and SSDDH
is at least hard to resolve. For the purposes of this discussion, we will presume
that SSI is equivalent to SSDDH.
In the context of cryptography, the problem of computing an isogeny between
isogenous supersingular curves was first considered by Galbraith [7] in 1999. The
first published cryptographic primitive based on supersingular isogeny graphs is
the hash function proposal of Charles et al. [4], which remains unbroken to date
(the cryptanalysis of [13] applies only to the LPS graph-based hash function
from [4], and not to the supersingular isogeny graph-based hash functions). The
fastest known algorithm for finding isogenies between supersingular curves in
general takes
O
(
√
p
log
2
p
)time[4,
5.3.1]; however our problem is less general
because the degree of the isogeny is known in advance and is smooth. Since we
are the first to propose using isogenies of this type, there is no existing literature
addressing the security of the isogenies of the special form that we propose.
There is an easy exponential attack against our cryptosystem that improves
upon exhaustive search. To find an isogeny of degree
e
A
between
E
and
E
A
,
an attacker builds two trees of all curves isogenous to
E
(respectively,
E
A
)via
isogenies of degree
e
A
/
2
§
A
. Once the trees are built, the attacker tries to find a
curve lying in both trees. Since the degree of the isogeny
φ
A
is
∼
√
p
(much
shorter than the size of the isogeny graph), it is unlikely that there will be more
than one isogeny path—and thus more than one match—from
E
to
E
A
.Given
two functions
if
:
A
C
with domain of equal size, finding a pair
(
a, b
) such that
if
(
a
)=
g
(
b
)isknownasthe
claw problem
in complexity theory.
The claw problem can obviously be solved in
O
(
→
C
and
g
:
B
→
)space
on a classical computer by building a hash table holding
if
(
a
) for any
a
|
A
|
+
|
B
|
)timeand
O
(
|
A
|
∈
A
A
)=
O
(
√
p
)
classical attack against our cryptosystem. With a quantum computer, one can
B
.Thisgivesa
O
(
e
A
/
2
and looking for hits for
g
(
b
)where
b
∈
do better using the algorithm in [20], which has complexity
O
(
3
|
A
||
B
|
), thus
A
)=
O
(
√
p
) quantum attack against our cryptosystem. These
complexities are optimal for a black-box claw attack [25].
We consider the question of whether the auxiliary data points
φ
A
(
P
B
)and
φ
A
(
Q
B
) might assist an adversary in determining
φ
A
.Since(
P
B
,Q
B
)formsa
basis for
E
0
[
e
B
], the values
φ
A
(
P
B
)and
φ
A
(
Q
B
) allow the adversary to com-
pute
φ
A
on all of
E
0
[
e
B
]. This is because any element of
E
0
[
e
B
]isa(known)
linear combination of
P
B
and
Q
B
(known since extended discrete logarithms are
easy [22]). However, there does not appear to be any way to use this capability
to determine
φ
A
. Even on a quantum computer, where finding abelian hidden
subgroups is easy, there is no hidden subgroup to find, since
φ
A
has degree
e
A
,
and thus does not annihilate any point in
E
0
[
e
B
] other than the identity. Of
course, if one could evaluate
φ
A
on arbitrary points of
E
0
[
e
A
], then a quantum
giving an
O
(
e
A
/
3
