Provable Security of Key Exchange Protocols

Provable Security of Key Exchange Protocols

Cryptographic protocols such as TLS and Signal form the foundation of secure communication, ensuring confidentiality, integrity, and authentication for billions of users worldwide. In this seminar, we will look into the theoretical foundations of the underlying protocols. We will examine recent research papers on key exchange and secure messaging that address advanced cryptographic properties (e.g., deniability), specific functionalities (e.g., password-based or hybrid key exchange), and tight security proofs.

Each student will be assigned a research paper to present with subsequent discussion. Additionally, the talk should be summarized in a two-page handout. Since these papers are often extensive and contain detailed security proofs, students may concentrate on a specific contribution in coordination with the lecturer. To support this process, the seminar will include two introductory sessions with guidance, practical tips, and an example presentation.

Schedule

The seminar takes place on Mondays 16:00-18:00.

Location: E 9.1 (CISPA main building), room 2.22 

Meetings:

• April 28: Kickoff meeting
• May 5: Intro (Part 1) and Paper Assignment [Start at 16:30]
• May 12: Intro (Part 2) [Virtually]
• May 19: No meeting
• May 26: Intro (Part 3)
• June 2: No meeting (optional: virtual Q&A on another weekday)
• June 9: Holiday (optional: virtual Q&A on another weekday)
• June 16: Q&A [Virtually]
• June 23: Presentation 1+2
• June 30: Presentation 3+4
• July 7: Presentation 5+6
• July 14: Presentation 7+8

Unless specified as optional, attendance is mandatory. Zoom links for virtual sessions will be published ahead of time. For additional guidance, we will have two optional Q&A sessions. I will send out a poll to find a suitable date and time in advance.

In the last four weeks of the semester, we will have the final presentations. The order is determined by the order of the list of papers (see below). Talks should be 45 minutes + 15 minutes discussion, and each student is expected to prepare a handout to be submitted on the Thursday before the talk. More details on the expected outcome will be provided in the kickoff and first intro session. 

In the kickoff, I will give an overview of the following papers. Some papers have long and detailed definitions and proofs, and I will outline a potential focus for each paper. Each student should then pick around three papers before the Intro meeting on May 5, so that we can have a fair assignment process. The order is as follows:

1. Non-Interactive Key Exchange (https://eprint.iacr.org/2012/732.pdf) [NIKE]
2. Highly Efficient Key Exchange Protocols with Optimal Tightness (https://eprint.iacr.org/2019/737.pdf) [AKE]
3. Protoss: Protocol for Tight Optimal Symmetric Security (https://eprint.iacr.org/2024/1581.pdf) [PAKE]
4. SweetPAKE: Key exchange with decoy passwords (https://eprint.iacr.org/2024/307.pdf) [PAKE]
5. Unilaterally-Authenticated Key Exchange (https://eprint.iacr.org/2017/109.pdf) [AKE]
6. Privacy-Preserving Authenticated Key Exchange and the Case of IKEv2 (https://eprint.iacr.org/2020/1519.pdf) [AKE]
7. The OPTLS Protocol and TLS 1.3 (https://eprint.iacr.org/2015/978.pdf) [AKE]
8. Post-Quantum TLS Without Handshake Signatures (https://eprint.iacr.org/2020/534.pdf) [AKE]
9. Many a Mickle Makes a Muckle: A Framework for Provably Quantum-Secure Hybrid Key Exchange (https://eprint.iacr.org/2020/099.pdf) [AKE]
10. Obfuscated Key Exchange (https://eprint.iacr.org/2024/1086.pdf) [AKE]
11. Towards post-quantum secure PAKE - A tight security proof for OCAKE in the BPR model (https://eprint.iacr.org/2023/1368.pdf) [PAKE]
12. Bundled Authenticated Key Exchange: A Concrete Treatment of (Post-Quantum) Signal’s Handshake Protocol (https://eprint.iacr.org/2025/040.pdf) [Messaging]
13. Security Analysis of Signal’s PQXDH Handshake (https://eprint.iacr.org/2024/702.pdf) [Messaging]
14. The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol (https://eprint.iacr.org/2018/1037.pdf) [Messaging]
15. Towards Leakage-Resilient Ratcheted Key Exchange (https://eprint.iacr.org/2025/332.pdf) [Messaging]
16. Anamorphic Authenticated Key Exchange: Double Key Distribution under Surveillance (https://eprint.iacr.org/2024/1438.pdf) [AKE]
17. A Deniability Analysis of Signal's Initial Handshake PQXDH (https://eprint.iacr.org/2024/741.pdf) [Messaging]
18. K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures (https://eprint.iacr.org/2024/120.pdf) [Messaging]