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 identity-based encryption scheme, a challenge posed by Shamir in 1984. The setting has proved fruitful: for many goals, pairing-based 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: identity-based encryption; digital signatures and their variants; group signatures; broadcast encryption and traitor tracing; e-cash; and fundamental topics such as chosen-ciphertext secure encryption, pseudorandom functions, and non-interactive zero knowledge.

Throughout, we note two major thrusts in the field: to obtain schemes secure without relying on the so-called 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:

1. Elliptic curves over Char-0 fields
   1. Rational functions and divisors
   2. Curve points; the group law; n-torsion points
2. Elliptic curves over finite fields
   1. Rational maps: endomorphisms and isogenies; ramification
   2. The Weil pairing
   3. The Hasse bound
3. Pairings
   1. Weil reciprocity
   2. The Tate pairing
   3. The Weil pairing revisited
4. Efficient computation
   1. Balasubramanian-Koblitz
   2. Miller's algorithm
   3. Suitable curve families (time permitting)

The outline for the crypto portion follows. For bibliographic information and links to papers, see bibliography at bottom.

1. Preliminaries
   1. The pairing-based crypto setting
   2. Computational and Decisional Diffie-Hellman; Joux-Nguyen [JN01]
   3. A motivating example: tripartite key exchange [J00]
   4. Computational and Decisional Bilinear Diffie-Hellman [BF01]
2. Identity-Based Encryption
   1. Motivation and model
   2. Boneh-Franklin IBE [BF01]
   3. The Boneh-Boyen Framework
      1. Boneh-Boyen IBE and selective-ID security [BB04a]
      2. Waters IBE [W05]
3. Hierarchical IBE
   1. HIBE motivation and model [HL02,GS02]
   2. HIBE extensions of BB-IBE and Waters IBE
   3. Constant-size HIBE (and the BDHI problem) [BBG05]
   4. Current topics in HIBE research: tight reductions, anonymity
4. Transformations from (H)IBE
   1. Naor: Signatures (teaser) [BF01]
   2. (Hierarchical) ID-based signatures [GS02]
   3. Forward-secure encryption/signatures [CHK03]
   4. CCA-secure encryption [CHK04,BK05,BCHK]
   5. Threshold CCA security [BBH06]
5. (H)IBE-related constructions
   1. Non-generic CCA constructions [BMW05,K06]
   2. Broadcast encryption [BGW05]
   3. Fuzzy IBE [SW05]
   4. Searchable public-key encryption [BdCOP04]
6. Signatures
   1. From Naor transform: BLS, Waters [BLS01,W05]
   2. Multisignatures and aggregate signatures [B03,BGLS03,LOSSW06]
   3. The Strong Diffie-Hellman problem [BB04b]
   4. Boneh-Boyen signatures [BB04b]
   5. The Dodis-Yampolskiy VRF [DY05]
   6. Group signatures [BBS04]
7. Pairing based crypto in groups of composite order
   1. Setting; homomorphic evaluation of 2-DNF [BGN05]
   2. Perfect NIZKs for NP [GOS06]
   3. 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):235-61, Sep. 2004.

For the second part, we will read research papers. The best repository for these is Paulo Barreto’s Pairing-Based Crypto Lounge.

Related Resources

• Mihir Bellare's CS 208—Advanced Cryptography at UCSD focused in 2004 on pairing-based crypto.

Bibliography

[B03]

Alexandra Boldyreva. Threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme. In Yvo Desmedt, editor, Proceedings of PKC 2003, volume 2567 of LNCS, pages 31-46. Springer-Verlag, January 2003.
[ .html ]

[BB04a]

Dan Boneh and Xavier Boyen. Efficient selective-ID secure identity based encryption without random oracles. In Christian Cachin and Jan Camenisch, editors, Proceedings of Eurocrypt 2004, volume 3027 of LNCS, pages 223-38. Springer-Verlag, 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 56-73. Springer-Verlag, May 2004.
[ .html ]

[BBG05]

Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical identity based encryption with constant size ciphertext. In Ronald Cramer, editor, Proceedings of Eurocrypt 2005, volume 3494 of LNCS, pages 440-56. Springer-Verlag, 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 CT-RSA 2006, volume 3860 of LNCS, pages 226-43. Springer-Verlag, 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 41-55. Springer-Verlag, August 2004.
[ .pdf ]

[BCHK]

Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based 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 506-22. Springer-Verlag, May 2004.
[ .html ]

[BF01]

Dan Boneh and Matt Franklin. Identity-based encryption from the weil pairing. In Joe Kilian, editor, Proceedings of Crypto 2001, volume 2139 of LNCS, pages 213-29. Springer-Verlag, August 2001. Full version: [BF01-journal].

[BF01-journal]

Dan Boneh and Matt Franklin. Identity-based encryption from the Weil pairing. SIAM J. Computing, 32(3):586-615, 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 416-32. Springer-Verlag, 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 258-275. Springer-Verlag, August 2005.
[ .html ]

[BGN05]

Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. In Joe Kilian, editor, Proceedings of TCC 2005, number 3378 in LNCS, pages 325-41. Springer-Verlag, February 2005.
[ .html ]

[BK05]

Dan Boneh and Jonathan Katz. Improved efficiency for CCA-secure cryptosystems built using identity based encryption. In Alfred John Menezes, editor, Proceedings of CT-RSA 2005, volume 3376 of LNCS, pages 87-103. Springer-Verlag, 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 514-32. Springer-Verlag, December 2001. Full version: [BLS01-journal].

[BLS01-journal]

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

[BMW05]

Xavier Boyen, Qixiang Mei, and Brent Waters. Direct chosen ciphertext security from identity-based techniques. In Vijay Atluri, Catherine Meadows, and Ari Juels, editors, Proceedings of CCS 2005, pages 320-329. 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. Springer-Verlag, May 2006. To appear.
[ http ]

[CHK03]

Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In Eli Biham, editor, Proceedings of Eurocrypt 2003, volume 2656 of LNCS, pages 255-271. Springer-Verlag, May 2003.
[ .ps ]

[CHK04]

Ran Canetti, Shai Halevi, and Jonathan Katz. Chosen-ciphertext security from identity-based encryption. In Christian Cachin and Jan Camenisch, editors, Proceedings of Eurocrypt 2004, volume 3027 of LNCS, pages 207-22. Springer-Verlag, 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 56-72. Springer-Verlag, 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 416-31. Springer-Verlag, January 2005.
[ .ps ]

[GOS06]

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

[GS02]

Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In Yuliang Zheng, editor, Proceedings of Asiacrypt 2002, volume 2501 of LNCS, pages 548-66. Springer-Verlag, December 2002.
[ http ]

[HL02]

Jeremy Horwitz and Ben Lynn. Toward hierarchical identity-based encryption. In Lars Knudsen, editor, Proceedings of Eurocrypt 2002, volume 2332 of LNCS, pages 466-81. Springer-Verlag, May 2002.
[ .html ]

[J00]

Antoine Joux. A one round protocol for tripartite Diffie-Hellman. In Wieb Bosma, editor, Proceedings of ANTS IV, volume 1838 of LNCS, pages 385-94. Springer-Verlag, July 2000. Full version: [J00-journal].

[J00-journal]

Antoine Joux. A one round protocol for tripartite Diffie-Hellman. J. Cryptology, 17(4):263-76, September 2004.

[JN01-eprint]

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

[JN01-journal]

Antoine Joux and Kim Nguyen. Separating decision Diffie-Hellman from computational Diffie-Hellman in cryptographic groups. J. Cryptology, 16(4):239-47, September 2003.

[K06]

Eike Kiltz. Chosen-ciphertext security from tag-based encryption. In Shai Halevi and Tal Rabin, editors, Proceedings of TCC 2006, volume 3876 of LNCS, pages 581-600. Springer-Verlag, March 2006.

[L02]

Anna Lysyanskaya. Unique signatures and verifiable random functions from the DH-DDH separation. In Moti Yung, editor, Proceedings of Crypto 2002, volume 2442 of LNCS, pages 597-612. Springer-Verlag, 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. Springer-Verlag, 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 457-73. Springer-Verlag, May 2005.
[ http ]

[W05]

Brent Waters. Efficient identity-based encryption without random oracles. In Ronald Cramer, editor, Proceedings of Eurocrypt 2005, volume 3494 of LNCS, pages 114-27. Springer-Verlag, May 2005.
[ http ]