CSE 208B: Pairings in Cryptography

Winter 2010


Instructor: Hovav Shacham, hovav@cs.ucsd.edu
Lectures: Tuesdays and Thursdays, 11:00 AM – 12:20 PM in TM 102 Center Hall 224A.
Office hours: Wednesdays, 4:00–6:00 PM in EBU 3B 3124
Final: (none)

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 decade 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 is TBA, and will be posted here.

Textbook Information

For the first part of the course, we will refer to the following:

For the second part, we will read research papers. Links to these papers will be posted here.

Assignments

Students will be expected to attend lecture and to take scribe notes. A first draft of scribe notes is due one week after the lecture; corrected scribe notes will be posted to this page.


Navigation: CSE // CSE 208B