Pairings in Cryptography
(Weizmann Institute of Science, Spring 2006)
Description
We survey the use of pairings over certain elliptic curves to build
cryptosystems. This area of cryptography has seen a great deal of
interest over the last five years, since the publication of Boneh and
Franklin’s identitybased encryption scheme, a challenge posed
by Shamir in 1984. The setting has proved fruitful: for many goals,
pairingbased constructions are either the only ones known or are more
attractive than constructions in other settings.
Like the field of research, the course will be in two parts. The first
considers the mathematics behind elliptic curves and pairings. The second
surveys the cryptographic schemes which have been obtained using pairings.
In the first part, we present the necessary mathematical background
through the proof of Weil Reciprocity, and the relevant algorithms
through Miller’s Algorithm. We favor elementary exposition over
generality. This eliminates commutative algebra and algebraic geometry
as prerequisites, at the cost of some elegance.
In the second part, we survey the cryptography based on pairings. We
will try to note the standard computational assumptions, useful proof
techniques, and important cryptosystems. The schemes we consider include:
identitybased encryption; digital signatures and their variants;
group signatures; broadcast encryption and traitor tracing; ecash;
and fundamental topics such as chosenciphertext secure encryption,
pseudorandom functions, and noninteractive zero knowledge.
Throughout, we note two major thrusts in the field: to obtain schemes
secure without relying on the socalled random oracle model and to
understand the computational assumptions required to prove schemes
secure.
Lecture Outline
The tentative outline for the math portion is as follows:
 Elliptic curves over Char0 fields
 Rational functions and divisors
 Curve points; the group law; ntorsion points
 Elliptic curves over finite fields
 Rational maps: endomorphisms and isogenies; ramification
 The Weil pairing
 The Hasse bound
 Pairings
 Weil reciprocity
 The Tate pairing
 The Weil pairing revisited
 Efficient computation
 BalasubramanianKoblitz
 Miller's algorithm
 Suitable curve families (time permitting)
The outline for the crypto portion follows. For bibliographic
information and links to papers, see bibliography at bottom.
 Preliminaries
 The pairingbased crypto setting
 Computational and Decisional DiffieHellman; JouxNguyen [JN01]
 A motivating example: tripartite key exchange [J00]
 Computational and Decisional Bilinear DiffieHellman [BF01]
 IdentityBased Encryption
 Motivation and model
 BonehFranklin IBE [BF01]
 The BonehBoyen Framework
 BonehBoyen IBE and selectiveID security [BB04a]
 Waters IBE [W05]
 Hierarchical IBE
 HIBE motivation and model [HL02,GS02]
 HIBE extensions of BBIBE and Waters IBE
 Constantsize HIBE (and the BDHI problem) [BBG05]
 Current topics in HIBE research: tight reductions, anonymity
 Transformations from (H)IBE
 Naor: Signatures (teaser) [BF01]
 (Hierarchical) IDbased signatures [GS02]
 Forwardsecure encryption/signatures [CHK03]
 CCAsecure encryption [CHK04,BK05,BCHK]
 Threshold CCA security [BBH06]
 (H)IBErelated constructions
 Nongeneric CCA constructions [BMW05,K06]
 Broadcast encryption [BGW05]
 Fuzzy IBE [SW05]
 Searchable publickey encryption [BdCOP04]
 Signatures
 From Naor transform: BLS, Waters [BLS01,W05]
 Multisignatures and aggregate signatures [B03,BGLS03,LOSSW06]
 The Strong DiffieHellman problem [BB04b]
 BonehBoyen signatures [BB04b]
 The DodisYampolskiy VRF [DY05]
 Group signatures [BBS04]
 Pairing based crypto in groups of composite order
 Setting; homomorphic evaluation of 2DNF [BGN05]
 Perfect NIZKs for NP [GOS06]
 Signature variants without random oracles [BW06,…]
Textbook Information
For the first part of the course, we will refer to the following:
 An Elementary
Introduction to Elliptic Curves, Leonard S. Charlap and David P.
Robbins, IDA CCR Report 31, 1988.
 An Elementary
Introduction to Elliptic Curves, II, Leonard S. Charlap and Raymond
Coley, IDA CCR Report 34, 1990.
 “Pairings”, Steven Galbraith, in
Advances in Elliptic Curve Cryptography,
LMS Lecture Notes 317, 2005.
 “Short Programs for
functions on Curves”, Victor Miller, 1986. Samizdat.
 “The
Weil Pairing, and Its Efficient Calculation”, Victor Miller,
J. Cryptology, 17(4):23561, Sep. 2004.
For the second part, we will read research papers. The best
repository for
these is Paulo Barreto’s PairingBased Crypto Lounge.
Related Resources
Bibliography

[B03]

Alexandra Boldyreva.
Threshold signature, multisignature and blind signature schemes based
on the gapDiffieHellmangroup signature scheme.
In Yvo Desmedt, editor, Proceedings of PKC 2003, volume 2567 of
LNCS, pages 3146. SpringerVerlag, January 2003.
[ .html ]

[BB04a]

Dan Boneh and Xavier Boyen.
Efficient selectiveID secure identity based encryption without
random oracles.
In Christian Cachin and Jan Camenisch, editors, Proceedings of
Eurocrypt 2004, volume 3027 of LNCS, pages 22338. SpringerVerlag,
May 2004.
[ .html ]

[BB04b]

Dan Boneh and Xavier Boyen.
Short signatures without random oracles.
In Christian Cachin and Jan Camenisch, editors, Proceedings of
Eurocrypt 2004, volume 3027 of LNCS, pages 5673. SpringerVerlag,
May 2004.
[ .html ]

[BBG05]

Dan Boneh, Xavier Boyen, and EuJin Goh.
Hierarchical identity based encryption with constant size ciphertext.
In Ronald Cramer, editor, Proceedings of Eurocrypt 2005, volume
3494 of LNCS, pages 44056. SpringerVerlag, May 2005.
[ .html ]

[BBH06]

Dan Boneh, Xavier Boyen, and Shai Halevi.
Chosen ciphertext secure public key threshold encryption without
random oracles.
In David Pointcheval, editor, Proceedings of CTRSA 2006,
volume 3860 of LNCS, pages 22643. SpringerVerlag, February 2006.
[ .html ]

[BBS04]

Dan Boneh, Xavier Boyen, and Hovav Shacham.
Short group signatures.
In Matt Franklin, editor, Proceedings of Crypto 2004, volume
3152 of LNCS, pages 4155. SpringerVerlag, August 2004.
[ .pdf ]

[BCHK]

Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz.
Chosenciphertext security from identitybased encryption.
SIAM J. Computing, 2006.
To appear.
[ .pdf ]

[BdCOP04]

Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano.
Public key encryption with keyword search.
In Christian Cachin and Jan Camenisch, editors, Proceedings of
Eurocrypt 2004, volume 3027 of LNCS, pages 50622. SpringerVerlag,
May 2004.
[ .html ]

[BF01]

Dan Boneh and Matt Franklin.
Identitybased encryption from the weil pairing.
In Joe Kilian, editor, Proceedings of Crypto 2001, volume 2139
of LNCS, pages 21329. SpringerVerlag, August 2001.
Full version: [BF01journal].

[BF01journal]

Dan Boneh and Matt Franklin.
Identitybased encryption from the Weil pairing.
SIAM J. Computing, 32(3):586615, 2003.
[ .html ]

[BGLS03]

Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham.
Aggregate and verifiably encrypted signatures from bilinear maps.
In Eli Biham, editor, Proceedings of Eurocrypt 2003, volume
2656 of LNCS, pages 41632. SpringerVerlag, May 2003.
[ .pdf ]

[BGW05]

Dan Boneh, Craig Gentry, and Brent Waters.
Collusion resistant broadcast encryption with short ciphertexts and
private keys.
In Victor Shoup, editor, Proceedings of Crypto 2005, volume
3621 of LNCS, pages 258275. SpringerVerlag, August 2005.
[ .html ]

[BGN05]

Dan Boneh, EuJin Goh, and Kobbi Nissim.
Evaluating 2DNF formulas on ciphertexts.
In Joe Kilian, editor, Proceedings of TCC 2005, number 3378 in
LNCS, pages 32541. SpringerVerlag, February 2005.
[ .html ]

[BK05]

Dan Boneh and Jonathan Katz.
Improved efficiency for CCAsecure cryptosystems built using
identity based encryption.
In Alfred John Menezes, editor, Proceedings of CTRSA 2005,
volume 3376 of LNCS, pages 87103. SpringerVerlag, February 2005.
Full version: [BCHK].

[BLS01]

Dan Boneh, Ben Lynn, and Hovav Shacham.
Short signatures from the Weil pairing.
In Colin Boyd, editor, Proceedings of Asiacrypt 2001, volume
2248 of LNCS, pages 51432. SpringerVerlag, December 2001.
Full version: [BLS01journal].

[BLS01journal]

Dan Boneh, Ben Lynn, and Hovav Shacham.
Short signatures from the Weil pairing.
J. Cryptology, 17(4):297319, September 2004.
[ .pdf ]

[BMW05]

Xavier Boyen, Qixiang Mei, and Brent Waters.
Direct chosen ciphertext security from identitybased techniques.
In Vijay Atluri, Catherine Meadows, and Ari Juels, editors,
Proceedings of CCS 2005, pages 320329. ACM Press, November 2005.
[ .html ]

[BW06]

Xavier Boyen and Brent Waters.
Compact group signatures without random oracles.
In Serge Vaudenay, editor, Proceedings of Eurocrypt 2006,
volume 4004 of LNCS. SpringerVerlag, May 2006.
To appear.
[ http ]

[CHK03]

Ran Canetti, Shai Halevi, and Jonathan Katz.
A forwardsecure publickey encryption scheme.
In Eli Biham, editor, Proceedings of Eurocrypt 2003, volume
2656 of LNCS, pages 255271. SpringerVerlag, May 2003.
[ .ps ]

[CHK04]

Ran Canetti, Shai Halevi, and Jonathan Katz.
Chosenciphertext security from identitybased encryption.
In Christian Cachin and Jan Camenisch, editors, Proceedings of
Eurocrypt 2004, volume 3027 of LNCS, pages 20722. SpringerVerlag,
May 2004.
Full version: [BCHK].

[CL04]

Jan Camenisch and Anna Lysyanskaya.
Signature schemes and anonymous credentials from bilinear maps.
In Matt Franklin, editor, Proceedings of Crypto 2004, volume
3152 of LNCS, pages 5672. SpringerVerlag, August 2004.
[ .pdf ]

[DY05]

Yevgeniy Dodis and Aleksandr Yampolskiy.
A verifiable random function with short proofs and keys.
In Serge Vaudenay, editor, Proceedings of PKC 2005, volume 3386
of LNCS, pages 41631. SpringerVerlag, January 2005.
[ .ps ]

[GOS06]

Jens Groth, Rafail Ostrovsky, and Amit Sahai.
Perfect noninteractive zero knowledge for NP.
In Serge Vaudenay, editor, Proceedings of Eurocrypt 2006,
volume 4004 of LNCS. SpringerVerlag, May 2006.
To appear.
[ http ]

[GS02]

Craig Gentry and Alice Silverberg.
Hierarchical IDbased cryptography.
In Yuliang Zheng, editor, Proceedings of Asiacrypt 2002, volume
2501 of LNCS, pages 54866. SpringerVerlag, December 2002.
[ http ]

[HL02]

Jeremy Horwitz and Ben Lynn.
Toward hierarchical identitybased encryption.
In Lars Knudsen, editor, Proceedings of Eurocrypt 2002, volume
2332 of LNCS, pages 46681. SpringerVerlag, May 2002.
[ .html ]

[J00]

Antoine Joux.
A one round protocol for tripartite DiffieHellman.
In Wieb Bosma, editor, Proceedings of ANTS IV, volume 1838 of
LNCS, pages 38594. SpringerVerlag, July 2000.
Full version: [J00journal].

[J00journal]

Antoine Joux.
A one round protocol for tripartite DiffieHellman.
J. Cryptology, 17(4):26376, September 2004.

[JN01eprint]

Antoine Joux and Kim Nguyen.
Separating decision DiffieHellman from DiffieHellman in
cryptographic groups.
Cryptology ePrint Archive, Report 2001/003, 2001.
http://eprint.iacr.org/.

[JN01journal]

Antoine Joux and Kim Nguyen.
Separating decision DiffieHellman from computational
DiffieHellman in cryptographic groups.
J. Cryptology, 16(4):23947, September 2003.

[K06]

Eike Kiltz.
Chosenciphertext security from tagbased encryption.
In Shai Halevi and Tal Rabin, editors, Proceedings of TCC 2006,
volume 3876 of LNCS, pages 581600. SpringerVerlag, March 2006.

[L02]

Anna Lysyanskaya.
Unique signatures and verifiable random functions from the DHDDH
separation.
In Moti Yung, editor, Proceedings of Crypto 2002, volume 2442
of LNCS, pages 597612. SpringerVerlag, August 2002.
[ .pdf ]

[LOSSW06]

Steve Lu, Rafail Ostrovsky, Amit Sahai, Hovav Shacham, and Brent Waters.
Sequential aggregate signatures and multisignatures without random
oracles.
In Serge Vaudenay, editor, Proceedings of Eurocrypt 2006,
volume 4004 of LNCS. SpringerVerlag, May 2006.
To appear.
[ http ]

[SW05]

Amit Sahai and Brent Waters.
Fuzzy identity based encryption.
In Ronald Cramer, editor, Proceedings of Eurocrypt 2005, volume
3494 of LNCS, pages 45773. SpringerVerlag, May 2005.
[ http ]

[W05]

Brent Waters.
Efficient identitybased encryption without random oracles.
In Ronald Cramer, editor, Proceedings of Eurocrypt 2005, volume
3494 of LNCS, pages 11427. SpringerVerlag, May 2005.
[ http ]