Cryptography Reference
In-Depth Information
from Bob, Alice computes an isogeny
φ
A
:
E
B
→
E
AB
having kernel equal to
; Bob proceeds
mutatis mutandis
. Alice and Bob
can then use the common
j
-invariant of
[
m
A
]
φ
B
(
P
A
)+[
n
A
]
φ
B
(
Q
A
)
E
AB
=
φ
B
(
φ
A
(
E
0
)) =
φ
A
(
φ
B
(
E
0
)) =
E
0
/
[
m
A
]
P
A
+[
n
A
]
Q
A
,
[
m
B
]
P
B
+[
n
B
]
Q
B
to form a secret shared key. For specific details of how each of the above com-
putations can be performed eciently, we refer the reader to Section 4.
The full protocol is given in Figure 1. We denote by
A
and
B
the identifiers
of Alice and Bob, and use sID to denote the unique session identifier.
3.2 Public-Key Encryption
The key-exchange protocol of Section 3.1 can easily be adapted to yield a public-
key cryptosystem, in much the same way that Elgamal encryption follows from
Die-Hellman. We briefly give the details here. All notation is the same as above.
Stolbunov [19] uses a similar construction, upon which ours is based.
Setup:
Choose
p
=
e
A
e
B
·
f
±
1,
E
0
,
{
P
A
,Q
A
}
,
{
P
B
,Q
B
}
as above. Let
H
=
{
be a hash function family indexed by a finite set
K
,where
each
H
k
is a function from
H
k
:
k
∈
K
}
w
.
F
p
2
to the message space
{
0
,
1
}
/
e
A
Key generation.
Choose two random elements
m
A
,n
A
∈
R
,notboth
divisible by
A
. Compute
E
A
,φ
A
(
P
B
)
,φ
A
(
Q
B
)asabove,andchoosearan-
dom element
k
Z
Z
∈
R
K
. The public key is (
E
A
,φ
A
(
P
B
)
,φ
A
(
Q
B
)
,k
)andthe
private key is (
m
A
,n
A
,k
).
Encryption.
Given a public key (
E
A
,φ
A
(
P
B
)
,φ
A
(
Q
B
)
,k
) and a message
m
∈
/
e
B
w
, choose two random elements
m
B
,n
B
∈
R
Z
{
0
,
1
}
Z
, not both divisible
by
B
, and compute
h
=
H
k
(
j
(
E
AB
))
,
c
=
h
⊕
m.
The ciphertext is (
E
B
,φ
B
(
P
A
)
,φ
B
(
Q
A
)
,c
).
Decryption.
Given a ciphertext (
E
B
,φ
B
(
P
A
)
,φ
B
(
Q
A
)
,c
)andaprivatekey
(
m
A
,n
A
,k
), compute the
j
-invariant
j
(
E
AB
)andset
h
=
H
k
(
j
(
E
AB
))
,
m
=
h
⊕
c.
The plaintext is
m
.
4 Algorithmic Aspects
We now give specific algorithms to implement the abovementioned steps e-
ciently.
