Cryptography Reference
In-Depth Information
We remark that given a generator
R
A
=[
m
A
]
P
A
+[
n
A
]
Q
A
, it is easy to solve
for (
m
A
,n
A
), since
E
0
has smooth order and thus extended discrete logarithms
are easy in
E
0
[22].
Problem 5.2 (Supersingular Computational Die-Hellman (SSCDH) problem).
Let
φ
A
:
E
0
→
E
A
be an isogeny whose kernel is
[
m
A
]
P
A
+[
n
A
]
Q
A
,and
let
φ
B
:
E
0
→
E
B
be an isogeny whose kernel is
[
m
B
]
P
B
+[
n
B
]
Q
B
,where
/
e
A
m
A
,n
A
(respectively
m
B
,n
B
) are chosen at random from
Z
Z
(respectively
/
e
B
Z
Z
) and not both divisible by
A
(respectively
B
). Given the curves
E
A
,
E
B
and the points
φ
A
(
P
B
)
,φ
A
(
Q
B
)
,φ
B
(
P
A
)
,φ
B
(
Q
A
), find the
j
-invariant of
E
0
/
[
m
A
]
P
A
+[
n
A
]
Q
A
,
[
m
B
]
P
B
+[
n
B
]
Q
B
.
Problem 5.3 (Supersingular Decision Die-Hellman (SSDDH) problem).
Given
a tuple sampled with probability 1
/
2 from one of the following two distributions:
-
(
E
A
,E
B
,φ
A
(
P
B
)
,φ
A
(
Q
B
)
,φ
B
(
P
A
)
,φ
B
(
Q
A
)
,E
AB
), where
E
A
,E
B
,
φ
A
(
P
B
)
,
φ
A
(
Q
B
)
,φ
B
(
P
A
)
,φ
B
(
Q
A
) are as in the SSCDH problem and
E
AB
=
E
0
/
[
m
A
]
P
A
+[
n
A
]
Q
A
,
[
m
B
]
P
B
+[
n
B
]
Q
B
,
-
(
E
A
,E
B
,φ
A
(
P
B
)
,φ
A
(
Q
B
)
,φ
B
(
P
A
)
,φ
B
(
Q
A
)
,E
C
), where
E
A
,E
B
,
φ
A
(
P
B
)
,
φ
A
(
Q
B
)
,φ
B
(
P
A
)
,φ
B
(
Q
A
) are as in the SSCDH problem and
E
C
=
E
0
/
[
m
A
]
P
A
+[
n
A
]
Q
A
,
[
m
B
]
P
B
+[
n
B
]
Q
B
,
/
e
A
where
m
A
,n
A
(respectively
m
B
,n
B
) are chosen at random from
Z
Z
/
e
B
) and not both divisible by
A
(respectively
B
),
determine from which distribution the triple is sampled.
(respectively
Z
Z
We conjecture that these problems are computationally infeasible, in the sense
that for any polynomial-time solver algorithm, the advantage of the algorithm
is a negligible function of the security parameter log
p
. The resulting security
assumptions are referred to as the SSI, SSCDH, and SSDDH assumptions, re-
spectively. Using the methods of Stolbunov [18], it is a routine exercise to prove
that the protocols of Section 3 are secure under SSDDH:
Theorem 5.4.
Under the SSDDH assumption, the key-agreement protocol of
Section 3.1 is session-key secure in the authenticated-links adversarial model of
Canetti and Krawczyk [3].
Theorem 5.5.
If the SSDDH assumption holds, and the hash function family
H
is entropy-smoothing, then the public-key cryptosystem of Section 3.2 is IND-
CPA.
Remark 5.6.
As in the ordinary case [14,19], our protocols do not provide au-
thentication. One possible workaround for the time being is to use classical
public-key authentication schemes in conjunction with the standard observa-
tion [16,
6.2] that the authentication step only needs to be secure against the
adversary at the time of the initial connection.
§