|
P
Pairing-Friendly Elliptic Curves
TheoryBog'liq gu2011 AQLLI SHAHAR, TEST, 1-мактаб тўгарак жадвал, BUYRUQ. YASIN BREND, TAQRIZ YANGI, 2, Tarjima SPLINES, DIFFERENTIAL EQUATIONS, AND OPTIMAL, (11-ozbetinshe K.U.A)Q.Zafar, APPLIKATSIYADA QIRQISHNI HAR HIL USULLARINI BAJARISH, EDUCATION SYSTEM OF UZBEKISTON, O’zbekistonning va jahon hamjamiyati, OCHILOVA NIGORANING, 7 yosh inqirozi uning sabablari va alomatlari, TEXNIKA MADANIYATI, AAAP
Pairing-Friendly Elliptic Curves
Theory
Let n be a prime number, and let
G
= ⟨g
⟩, G
= ⟨g
⟩, G
be (multiplicatively written) cyclic groups of order n.
A pairing is a bilinear map ˆe :
G
× G
→ G
, i.e.,
ˆe
(g
a
, g
b
) = ˆe(g
, g
)
ab
= ˆe (g
b
, g
a
).
Joux’ tripartite key agreement is a generalization of
the
Diffie–Hellman key agreement
in which three parties
Alice (A), Bob (B), and Charlie (C) would like to establish
a shared key K.
. A generates a random value
≤ a ≤ n and computes
f
a
= g
a
and h
a
= g
a
. A sends these values to B and C.
. B generates a random value
≤ b ≤ n and computes
f
b
= g
b
. B sends this value to A and C.
. C generates a random value
≤ a ≤ n and computes
h
c
= g
c
. C sends this value to A and B.
. Upon receipt of f
b
and h
c
, A computes K
A
= ˆe(f
b
, h
c
)
a
.
. Upon receipt of f
a
and h
c
, B computes K
B
= ˆe(f
a
, h
c
)
b
.
. Upon receipt of f
b
and h
a
, C computes K
C
= ˆe(f
b
, h
a
)
c
.
Notice that K
A
= K
B
= K
C
= ˆe(g
, g
)
abc
, so A, B, and
C share this key. An attacker is confronted with the bilin-
ear Diffie–Hellman problem, i.e., the problem of computing
the key given the public information. This is no harder than
the discrete logarithm problem in any of the three groups,
and no harder than the
computational Diffie–Hellman
problem
in any of the three groups.
Similar to the Diffie–Hellman key agreement, the
tripartite key agreement needs to be protected against
man-in-the-middle attacks
.
Applications
Tripartite key agreement can be used in its own if three
parties need to generate a shared key. In this case it is
more efficient than
group key agreement
protocols since
it requires a single round of communication.
If more than three parties want to generate a shared key
at least two rounds are necessary, see the entry on group
key agreement. These protocols use the Diffie–Hellman
key agreement as building blocks; most group key agree-
ment protocols can be altered to use tripartite key agree-
ment instead, see [
–
].
Recommended Reading
. Desmedt Y, Miyaji A () Redesigning group key exchange pro-
tocol based on bilinear pairing suitable for various environments.
In: Lai X and Yung M (eds) The th China international con-
ference on information security and cryptology, Inscrypt ,
Shanghai, October –, Oct . Lecture notes in computer
science, Springer-Verlag. To appear,
. Desmedt Y, Lange T () Revisiting pairing based group key
exchange. In: Tsudik G (ed) Financial cryptography and data
security. th international conference, FC , Cozumel, –
Jan , Revised selected papers, Lecture notes in computer
science, vol , Springer, Berlin, pp –
. Desmedt Y, Lange T, Burmester M () Scalable authenticated
tree based group key exchange for ad-hoc groups. In: Dietrich S
and Dhamija R (eds) Financial cryptography and data security.
th International Conference, FC , and st international
workshop on usable security, USEC , Scarborough, Trinidad
and Tobago, – Feb . Revised selected papers, Lecture
notes in computer science, vol , Springer, Heidelberg, ,
pp –
. Frey G, Rück H-G () A remark concerning m-divisibility
and the discrete logarithm problem in the divisor class group of
curves. Math Comp :–
. Joux A () A one round protocol for tripartite Diffie-Hellman.
In: Bosma W (ed) Algorithmic number theory. Proceedings of the
th International symposium, ANTS-IV, Lecture notes in com-
puter science, vol , Springer, Leiden, The Netherlands, –
July , pp –
. Menezes A, Okamoto T, Vanstone SA () Reducing ellip-
tic curve logarithms to logarithms in a finite field. IEEE Trans
Inform Theory ():–
|
| |
