Seminar über Kryptographie
Crypto RUB » Lehre (German) » Lehrveranstaltungen
Seminar über Kryptographie
Dozent Zeit Raum
Prof. E. Kiltz Mo, 14:15-16:00 NA 4/24

Zugewiesene Termine:

1Full-domain hash signatures20.4AcarPoettering
3"Optimal" bounds for full-domain hash signatures4.5.WienenKiltz
4Tight bounds for full-domain hash signatures11.5KatzerKiltz
5PKCS#1v1.5 padding18.5.LoopRàfols
7DL-based signatures8.6.EhsanifatmesariPoettering
9Hybrid encryption15.6.HornRàfols
11Cramer-Shoup encryption22.6.GeilichKiltz
12Authentication from hash functions6.7.BöhlPoettering
15Format-preserving encryption13.7.ZomorodpooshPoettering


Eine Vorbesprechung fand am 5. Februar (Do) statt, um 14:00 in Raum NA5/24. Dabei wurden auch die Vortragsthemen für Studierende der Mathematik festgelegt. Die Vortragsthemen für Studierenden der ITS werden über das allgemeine Seminarverteilungssystem vergeben.


Vorteilhaft fuer die Teilnahme am Seminar sind Grundkenntnisse in der theoretischen Kryptographie wie sie etwa in der Vorlesung "Kryptographie I+II" vermittelt werden. Es werden weiterhin Kenntnisse aus den mathematischen Grundvorlesungen der ersten drei bis vier Semester erwartet.


  • Vortrag von ca. 45 min-1 Stunde
  • Anwesenheitspflicht bei allen Vorträgen
  • Keine schriftliche Ausarbeitung
  • spätestens 2,5 Wochen vor dem Vortragstermin 2-seitige Zusammenfassung der Originalarbeit
  • spätestens 2 Wochen vor dem Vortragstermin persönlich beim Betreuer erscheinen, um das Verständnis des Inhalts zu zeigen
  • Spätestens 1 Woche vor dem Vortragstermin die Folien kurz dem Betreuer präsentieren
  • Weniger ist mehr. Versuchen Sie bei Ihrem Vortrag das essentielle Ihres Themas zu vermitteln. Dabei ist es nicht notwendig alle Details zu präsentieren.
  • Je nach Thema eignet sich entweder ein Tafelvortrag oder ein Beamervortrag, oder eine Kombination aus beiden. Bitte mit dem Betreuer absprechen.
  • Vortragssprache ist Deutsch oder Englisch.
  • Viel Spass!

Mögliche Vortragsthemen

Digital signatures

1: Full-domain hash signatures: definition, instantiations, and PKCS#1v1.5

FDH signatures are constructed from a trapdoor permutation (e.g., RSA) and a hash function. They arguably represent the most simple but provably-secure signature scheme.

In the seminar presentation you will first recall the random oracle methodology and the security goals of signature schemes, and then specify the FDH construction and prove it secure. In addition, you present details of the RSA-FDH variant standardised in PKCS#1v1.5.

Literature: Lecture notes by Jon Katz (Sec 14+16) and PKCS#1v2.2 (Sec 8.2)

2: RSA-based full-domain hash signatures with tighter reduction

The basic security argument for full-domain hash signatures assumes generic trapdoor permutations. However, for the RSA permutation specific additional properties hold from which improved security bounds can be derived.

In the seminar presentation you will identify a specific property of the RSA permutation and show how it can be exploited for proving RSA-FDH signatures secure with improved tightness.

Literature: Optimal security proofs for PSS and other signature schemes and Lecture notes by Jon Katz (Sec 16)

3: On the optimality of security bounds for RSA-based full-domain hash signatures

Generally, security reductions only establish lower bounds for the security of a scheme; in principle, the scheme could actually be more secure than formally established. Under certain conditions also upper bounds can be established for RSA-based FDH signatures. As they coincide with the lower bounds of the previous presentation, the security of RSA-FDH is perfectly characterised for the considered cases.

In the seminar presentation you will introduce the meta-reduction technique that allows proving upper bounds for cryptographic schemes. You will then apply this technique to RSA-FDH and derive corresponding security results (for RSA keys of a specific form).

Literature: Optimal security proofs for PSS and other signature schemes

4: Tight security of RSA-based full-domain hash signatures

The previous presentation established upper bounds for the security of RSA-FDH with RSA keys from a specific class. The bounds to not hold for keys outside this class; perhaps surprisingly, for such cases tight security can be proven.

In the seminar presentation you will introduce a special subclass of trapdoor permutations and prove tight security for the corresponding FDH signatures. You will argue that this class can be instantiated in the RSA setting.

Literature: Optimal security proofs for full domain hash, revisited

5: A closer look at PKCS#1v1.5 padding for RSA-based signatures

The cryptographic standard PKCS#1v1.5 defines a specific hash function to be used in the FDH construction. Unfortunately, for this particular function all upper and lower bounds established in the earlier presentations do not apply. As PKCS#1v1.5 signatures belong to the most-used cryptographic schemes in practice, a more thorough analysis is due.

In the seminar presentation you will recall the details of the PKCS#1v1.5 padding and indicate why generic formal security arguments do not apply. Using specific number-theoretic properties of RSA you will establish security bounds for partial-domain signatures, a much better approximation of the PKCS#1v1.5 standard.

Literature: Security proof for partial-domain hash signature schemes

6: Probabilistic signatures: RSA-PSS

In cryptography, introducing randomness sometimes allows constructing schemes with improved security bounds. A prime example for this are the widely used RSA-based PSS signatures.

In the seminar presentation you will specify the details of the PSS padding and prove tight security for corresponding signatures.

Literature: The Exact Security of Digital Signatures - How to Sign with RSA and Rabin and PKCS#1v2.2 (Sec 9.1)

7: Signatures based on the discrete logarithm problem

The most efficient and compact signatures in use today (ECDSA) are not based on RSA, but instead on the discrete logarithm problem on elliptic curves. Proving their security requires a specific technique: the Forking Lemma.

In the seminar presentation you will introduce and prove the Forking Lemma and apply it to the Schnorr signature scheme.

Literature: Multi-signatures in the plain public-key model and a general forking lemma

Public key encryption

8: Encrypting with RSA-OAEP

The widely standardised OAEP padding transforms the RSA trapdoor permutation into one of the most efficient available public key encryption schemes. It provides strong security (IND-CCA) with tight bounds. A variant of OAEP that is easier to analyse is OAEP+.

In the seminar presentation you will expose OAEP and OAEP+, compare them, and prove RSA-OAEP+ secure.

Literature: OAEP reconsidered and PKCS#1v2.2 (Sec 7.1)

9: Hybrid encryption and the RSA-KEM

In the hybrid encryption paradigm a public key encryption scheme is constructed from an (asymmetric) key encapsulation mechanism and a (symmetric) data encapsulation mechanism. This approach allows modularity both in design and analysis.

In the seminar presentation you will define KEMs and DEMs as cryptographic primitives, together with corresponding security notions. You will explain why KEMs and DEMs in combination yield secure public key encryption schemes. Finally you specify RSA-KEM and prove it secure in the proposed model.

Literature: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack (Sec 7) and Preliminary Proposal of ISO 18033-2 (Sec 20)

10: Hashed ElGamal: ECIES

ECIES is a particularly efficient encryption scheme defined in the discrete logarithm setting. For proving its security, the standard Diffie-Hellman assumption does not seem to be sufficient; rather, the proof involves an interactive assumption and crucially relies on the programmability of the random oracle.

In the seminar presentation you will detail the specification of ECIES and then formally establish the scheme's security.

Literature: The oracle Diffie-Hellman assumptions and an analysis of DHIES and Preliminary Proposal of ISO 18033-2 (Sec 15)

11: Cramer-Shoup encryption

The encryption scheme of Cramer and Shoup is defined in the discrete logarithm setting and provides IND-CCA security. It improves over its relative ElGamal in many aspects.

In the seminar presentation you will expose the details of the scheme and formally establish its CCA1 security based on the decisional Diffie-Hellman assumption.

Literature: Lecture notes by Jon Katz (Sec 9) and Preliminary Proposal of ISO 18033-2 (Sec 17)

Message authentication

12: Message authentication from hash functions

NMAC and its variant HMAC are pseudorandom functions constructed from the compression functions of common hash functions (e.g., MD5 or SHA1).

In the seminar presentation you will specify the details of NMAC and HMAC and discuss their practical differences. You will then propose a security requirement for the compression function and use it to prove that both NMAC and HMAC are secure pseudorandom functions.

Literature: Keying Hash Functions for Message Authentication and New proofs for NMAC and HMAC: Security without collision-resistance

13: Message authentication from blockciphers

CBC-MAC is a blockcipher-based message authentication code derived from the CBC (encryption) mode of operation. It is secure only for messages of fixed length. Its variants ECBC,FCBC,XCBC are improved versions that cover arbitrary message lengths.

In the seminar presentation you will specify the details of CBC-MAC and show that it is not secure in general. You then introduce the variant XCBC and formally establish that it is secure for arbitrary message lengths. You conclude by sketching the differences to the widely standardised CMAC mode.

Literature: CBC MACs for arbitrary-length messages: The three-key constructions and OMAC: One-Key CBC MAC

Symmetric encryption

14: Key wrapping

Key wrapping schemes allow the secure storage of cryptographic secret keys (e.g., RSA signing keys stored on a harddrive). The primitive is similar in spirit with regular symmetric encryption but differs in specific aspects (for instance, it is not randomized).

In the seminar presentation you will expose the key wrapping problem, compare it to symmetric key encryption, and specify its security requirements. You then provide the details of a specific construction and prove it secure.

Literature: A Provable-Security Treatment of the Key-Wrap Problem

15: Format-preserving encryption

The message and ciphertext spaces of blockciphers and encryption schemes are typically binary strings of fixed or variable length. In some applications, for instance when credit card numbers (16 decimal digits) shall be stored in a database, such binary encodings are not a suitable option. Format-preserving encryption schemes allow the secure encryption for specifically structured message/ciphertext spaces.

In the seminar presentation you will study a specific scheme that provides format-preserving encryption. You will present a security model, detail out a construction, and establish corresponding security results.

Literature: Format-preserving encryption