Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Advanced Topics in Cryptology

What is provably-secure public-key encryption?

For your information, some links to relevant texts:

Chapter 11 (Asymmetric encryption) of Bellare and Rogaway's lecture notes
cseweb.ucsd.edu/~mihir/cse207/classnotes.html

Poincheval 's course notes for Advnance Course on Contemporary Cryptology
www.di.ens.fr/~pointche/pub.php

Subtleties in the Definition of IND-CCA: When and How Should Challenge-Decryption be Disallowed?
by Mhir Bellare, Dennis Hofheinz, and Eike Kiltz
eprint.iacr.org/2009/418

Relations Among Notions of Security for Public-Key Encryption Schemes
by M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway (Crypto'98)
cseweb.ucsd.edu/~mihir/papers/relations.html

A Brief History of Provable-Secure Public-Key Encryption
by Alex Dent (Africacrypt'08)
eprint.iacr.org/2009/090

Posted by Martijn Stam at 13:06
Programme

6-10 Martijn Stam
A Brief History of Provably Secure Public-Key Cryptosystems
title borrowed from Alex Dent's
eprint.iacr.org/2009/090

13-10 Khaled Ouafi
On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
by Guilhem Castagnos and Fabien Laguillaumie (Eurocrypt'09, pp 260-277)
www.springerlink.com/content/q30mn13t4267j986/

20-10 Khaled Ouafi
Continuation of 13-10.

27-10 Maxime Augier
Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures
by Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, and Ralf-Phillip Weinmann (Crypto'09, pp428-444)
www.springerlink.com/content/r832007k63707727/

3-11 Behnaz Bostanipour
Reconstructing RSA Private Keys from Random Key Bits
by Nadia Heninger and Hovav Shacham (Crypto'09, pp 1-17)
www.springerlink.com/content/92502191l731q4m7/

10-11 Behnaz Bostanipour
Continuation of 3-11

17-11 Petr Susil
Practical Chosen Ciphertext Secure Encryption from Factoring
by Dennis Hofheinz and Eike Kiltz (Eurocrypt'09, pp 313-332)
www.springerlink.com/content/a3j4u3848087285x/ 

24-11 Petr Susil
Continuation of 17-11

1-12 Seth Flaxman
Improved generic algorithms for 3-collisions
by Antoine Joux and Stefan Lucks (Asiacrypt'09, to appear)
eprint.iacr.org/2009/305

8-12 Maxime Augier
Better price-performance ratios for generalized birthday attacks
by Daniel J. Bernstein (SHARCS'07)
cr.yp.to/rumba20/genbday-20070904.pdf

Posted by Martijn Stam at 13:36
Update on Schnorr's paper

C.P. Schnorr has put on his website an updated version of his paper:

 www.mi.informatik.uni-frankfurt.de/research/papers/SVP1+.pdf

Posted by Martijn Stam at 16:40
Next Lecture 22 September

The next two lectures (on 22 and 29 September) will be devoted to (proposed) methods to factor integers by rephrasing it as a lattice problem. The initial work on this by Schnorr can be found at documents.epfl.ch/users/s/st/stam/www/schnorr93.pdf.

Posted by Martijn Stam at 22:00
Possible Articles

Below is a list of possible articles to pick, as discussed during the first lecture. At the end of the next lecture (Tuesday 22nd) we will make an assignment who will present which paper when.

Related to Symmetric Cryptography

1. Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
by Ueli Maurer and Stefano Tessaro (Crypto'09, pp 355-373)
www.springerlink.com/content/t2xg94n47n317434/

2. How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle
by Ben Morris, Phillip Rogaway, and Till Stegers (Crypto'09, pp 286-302)
www.springerlink.com/content/040v453820835135/

3. Order Preserving Symmetric Encryption
by Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O'Neill (Eurocrypt'09, pp 224-241)
www.springerlink.com/content/y37n442u95067h23/

4. A Leakage-Resilient Mode of Operation
by Krzysztof Pietrzak (Eurocrypt'09, pp 462-482)
www.springerlink.com/content/u5446288477r31rq/

Related to Discrete Logarithm Based Systems

5. How to Hash into Elliptic Curves
by Thomas Icart (Crypto'09, pp 303-316)
www.springerlink.com/content/q42055608861m730/

Related to Factoring Based Systems

6. Reconstructing RSA Private Keys from Random Key Bits
by Nadia Heninger and Hovav Shacham (Crypto'09, pp 1-17)
www.springerlink.com/content/92502191l731q4m7/

7. On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
by Guilhem Castagnos and Fabien Laguillaumie (Eurocrypt'09, pp 260-277)
www.springerlink.com/content/q30mn13t4267j986/

8. Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures
by Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, and Ralf-Phillip Weinmann (Crypto'09, pp428-444)
www.springerlink.com/content/r832007k63707727/

9. Practical Chosen Ciphertext Secure Encryption from Factoring
by Dennis Hofheinz and Eike Kiltz (Eurocrypt'09, pp 313-332)
www.springerlink.com/content/a3j4u3848087285x/

10. Short and Stateless Signatures from the RSA Assumption
by Susan Hohenberger and Brent Waters (Crypto'09, pp 654-670)
www.springerlink.com/content/h7l319733p567318/

Related to Lattice Based Systems

11. Fully homomorphic encryption using ideal lattices
by Craig Gentry (STOC'09, pp 169-178)
 

Posted by Martijn Stam at 17:01
Organization of the course

During the course we will (mainly) discuss recent Eurocrypt and Crypto articles. Each student is expected to pick one (or depending on the time/difficulty two) article(s) and present it to his/her fellow students. A lively discussion is expected to ensue, which requires active participation from all involved.

In the first week (last Tuesday from 10.15 to 12.00) possible articles were discussed (see post below). The coming two weeks we will be discussing the relationship between lattices and integer factorization, spurred by recent work by C.P. Schnorr.

Posted by Martijn Stam at 16:26