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.
§
 
Search WWH ::




Custom Search