A study on tighter and more efficient isogeny-based cryptographic protocols

Abstract

This PhD thesis addresses the following research questions: • RQ 1: Can we prove tight reductions on isogeny-based schemes? • RQ 2: How sound are the assumptions underlying some computational problems in isogeny-based cryptography? • RQ 3: Can we obtain faster isogeny-based cryptography? The findings and contributions of this thesis consist in five scientific papers. More specifically, this thesis presents an adaptation of Cohn-Gordon et al. [CCG+19] construction to supersingular elliptic curves over Fp, obtaining an isogeny-based authenticated KEX protocol with an optimally tight proof. The thesis tests the reliability of certain assumptions and questions the security proof of the identification protocol based on SIDH. It also analyses the security proofs available in the literature for the SIDH-based identification protocol, together with their effects on the security of the digital signatures obtained via the Fiat-Shamir transform. A different approach to restore the security of an isogeny-based identification protocol is presented: relying on the Generalised Riemann Hypothesis, a new extractor is introduced, for which rigorous proof special-soundness property is given. In one of the papers included in the thesis, there is a proposal of an isogeny-based signature scheme whose security relies on the computational supersingular isogeny problem. The protocol is obtained by applying the Fiat-Shamir transform to the SIDH-identification protocol, and then performing a series of optimisations both on the signature size and on the signing algorithm. The thesis also presents a design of an algorithm to solve the constructive Deuring correspondence for general primes p, translating an ideal in the quaternion algebra ramified at p and 1 into an isogeny. In that work several optimisations are applied for speeding up the existing algorithms that work for more general primes than the ones carefully crafted in SQISign. Finally, the practicality of SIDH-based signatures is analysed in light of the new attacks against SIKE and the underlying KEX protocol. In particular, the last contribution shows how, despite the application of several optimisations to reduce the signature size and some minor improvements on the signing time, the design of efficient SIDH-based protocols is still an open problem.