On the Theory and Design of Post-Quantum Authenticated Key-Exchange, Encryption and Signatures

  • Cyprien P R Delpech De Saint Guilhem

Student thesis: Doctoral ThesisDoctor of Philosophy (PhD)


This thesis presents contributions to three areas of cryptography under the common concern for security against quantum adversaries. It discusses authentication in key-exchange protocols, isogeny-based schemes and protocols, and signature schemes based on the MPC-in-the-head paradigm.
In the first part, nuances of authentication in key-exchange protocols are explored and a transformation to add authentication to existing non-authenticated protocols is proposed. In Chapter 3, the Bellare-Rogaway model of security in a modern formulation, augmented to accommodate new definitions, is presented. In Chapter 4, new definitions for nuances of authentication which had remained undefined until this work are introduced, relations between them are studied and a folklore composition theorem is proven. In Chapter 5, the new definitions are applied to the study of existing protocols and a new secure transformation is presented.
In the second part, constructions for secure public-key encryption schemes and oblivious transfer protocols based on isogenies of supersingular elliptic curves are presented. In Chapter 6, a new one-way function family is defined and an IND-CCA-secure encryption scheme is constructed. In Chapter 7, a new framework of semi-commutative structures, which captures both isogeny-based and exponentiation-based protocols, is defined and different instantiations corresponding to the literature are discussed. In Chapter 8, two oblivious transfer protocols built from these structures are then presented together with their proof of security in the framework of universally composable security.
In the third and final part, improvements to signature schemes built from the MPC-in-the-head proof paradigm are explored. In Chapter 9, the impact of using the AES block cipher within Picnic signatures is studied. In Chapter 10, new verification techniques for this paradigm are used to both study the use of the Legendre PRF and re-visit the efficiency of using the AES block cipher.
Date of Award21 Mar 2021
Original languageEnglish
Awarding Institution
  • The University of Bristol
SupervisorNigel P Smart (Supervisor) & Bogdan Warinschi (Supervisor)

Cite this