Topics in theoretical cryptography: Pairing-based cryptography
Advanced cryptography: Pairing-based cryptography

This course is listed in Aachen Campus as Advanced Cryptography: pairing-based cryptography, in Bonn Basis as Advanced cryptography: Pairing-based cryptography and as MA-INF 1313 - Topics in Theoretical Cryptography: Pairing-based Cryptography with Exercises.

Responsible

Prof. Dr. Joachim von zur Gathen

Lecture

Michael Nüsken

Tutorial

Daniel Loebenberger

Time & Place

Tuesday 13³⁰-15⁰⁰, b-it Rheinsaal.
Wednesday 13³⁰-15⁰⁰, b-it Rheinsaal.
Tutorial: Tuesday 15¹⁵-16⁴⁵, b-it Rheinsaal.

First meeting: Tuesday, 23 October 2012.

All times subject to agreement in class.

Notes

The screen notes (PDF) contain all handwritten stuff (last updated 30 January 2013, 16:35).

Exercises

Exercise 1 (PDF, last updated 24 October 2012, 15:32).
Exercise 2 (PDF, last updated 31 October 2012, 16:31).
Exercise 3 (PDF, last updated 07 November 2012, 17:22).
Exercise 4 (PDF, last updated 14 November 2012, 16:19).
Exercise 5 (PDF, last updated 21 November 2012, 16:14).
Exercise 6 (PDF, last updated 05 December 2012, 11:27).
Exercise 7 (PDF, last updated 12 December 2012, 16:24).
Exercise 8 (PDF, last updated 20 December 2012, 15:16).
Exercise 9 (PDF, last updated 17 January 2013, 13:24).
Exercise 10 (PDF, last updated 24 January 2013, 10:53).

Prerequisites

Basic knowledge in cryptography is required.

Elliptic curve cryptography is important for a long time now.

But only recently pairings start to play an important role in the design of cryptosystems. They allow to build much more efficient cryptosystems than earlier construction. And these systems usually come with security reductions to mathematical problems that seem to be reasonably difficult. However, they also require the use of very special curves which may open new attack threats.

The course will study examples of cryptosystems using the new techniques. We will explain the basic techniques, algortihms, security reductions, and discuss consequences and dangers.

Structure

Guided by Paterson (2005 PDF), also Paterson (2002 PS).

Basics
1. First examples
  1. Three party key exchange
  2. ID based NI key distribution (Sakai, Ohgishi & Kasahara 2000)
  3. Short signatures (Boneh, Lynn & Shacham 2001/2003)
  4. ID based encryption (Boneh & Franklin 2003)
  5. First discussion of security
2. Elliptic curves (as half transparent boxes ) [see Nüsken 2010, ECC PDF.]
3. Pairings (as black boxes)
4. Miller's algorithm (pairings as half transparent boxes)
  - Nüsken (2010) PDF.
5. Security notions
6. ID based versus public key
  - Paterson & Price (2003) DOC.
All further sections shall describe a system and analyze its security.
Three party key exchange
- Joux (2000) SpringerLINK.
Key distribution (ID based...)
- Sakai, Ohgishi & Kasahara (2000) ???. (See Paterson @ crypt@b-it.)
- Dupont & Enge (2002). eprint 2002/136.
- Smart (2001) eprint 2001/111.
- Google for key distribution.
Encryption (ID based...)
- Boneh & Franklin (2001) PDF.
- Chen & Cheng (2003) eprint 2005/226.
- Boneh & Boyen (2004). DOI 10.1007/978-3-540-28628-8_27. Full version: eprint 2004/173.
- Waters (2005). DOI 10.1007/11426639_7.
- Gentry (2006). DOI 10.1007/11761679_27.
Certificateless public key encryption and key encapsulation.
- Al-Riyami & Paterson (2003). Certificateless public key cryptography. Eprint 2003/126.
  - Zhang & Feng (2005). On the Security of a Certificateless Public-Key Encryption. @CiteSeer.
  - Au, Chen, Liu, Mu, Wong & Yang (2006). Malicious KGC Attack in Certificateless Cryptography. @CiteSeer.
  - Gorantla, Gangishetti, Das & Saxena (2005). An effective certificateless signature scheme based on bilinear pairings. @CiteSeer.
  - Huang & Wong (2007). Generic Certificateless Encryption in the Standard Model. @CiteSeer.
  - Shi, Li & Shi (2006). Constructing Efficient Certificateless Public Key Encryption with Pairing. @CiteSeer.
  - Sun & Zhang (2008). Secure Certificateless Public Key Encryption without Redundancy. @CiteSeer.
  - Dent (2008). A survey of certicateless encryption schemes and security models. International Journal of Information Security 7(5), 349-377. eprint 2006/211.
- Lippold, Boyd & Nieto (2009). Efficient Certificateless KEM in the Standard Model. @CiteSeer.
- Lippold & Nieto (2010). Certificateless Key Agreement in the Standard Model. AISC 2010. PDF. Preprint PDF.
End of course / does not fit any more:
- Short signatures (Pairing based...)
  - Boneh, Lynn & Shacham (2001) PS.
  - ...
  - Paterson & Schuldt (2006). DOI 10.1007/11780656_18.
- Lee, Boyd, Dawson, Kim, Yang & Yoo (2004). Secure Key Issuing in ID-based Cryptography. @CiteSeer.
- Waters (2009). Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. Eprint 2009/385.
- Hierarchical ID based crypto
- ...
- Pereira, Simplício, Barreto (2011). A Family of Implementation-Friendly BN Elliptic Curves. @CiteSeer.

Literature

Kenny G. Paterson (2005). Cryptography from Pairings. In I.F. Blake, G. Seroussi and N.P. Smart (eds.), Advances in Elliptic Curve Cryptography, London Mathematical Society Lecture Note Series Vol. 317, Cambridge University Press, pp. 215-251.

Allocation

4+2 SWS, 8 ECTS credits. Optionally, 3+2 SWS, 6 ECTS credits.

Successful completion of the course yields 8 credit points. For students who only want 6 credit points, a breakpoint at about 3/4 of the teaching time will be defined, and only the course material up to that point will be relevant for their exams and grades.

Media Informatics: Computer and Communication Technology.
Recommendation for diploma students of University of Bonn - Computer Science: A or A1, respectively.
Master students in Computer Science at University of Bonn have to register this course with POS/BASIS.

Topics in theoretical cryptography: Pairing-based cryptography Advanced cryptography: Pairing-based cryptography