A study on tighter and more efficient isogeny-based cryptographic protocols
Doctoral thesis
Permanent lenke
https://hdl.handle.net/11250/3060410Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
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.
Består av
Paper 1: de Kock, Bor; Gjøsteen, Kristian; Veroni, Mattia. Practical Isogeny-Based Key-Exchange with Optimal Tightness. Lecture Notes in Computer Science (LNCS) 2021 ;Volum 12804. s. 451-479 https://doi.org/10.1007/978-3-030-81652-0_18Paper 2: Wissam Ghantous, Shuichi Katsumata, Federico Pintore, Mattia Veroni. Collisions in Supersingular Isogeny Graphs and the SIDH-based Identification Protocol
Paper 3: Wissam Ghantous, Federico Pintore, Mattia Veroni. Sigh: faster and shorter SIDH signatures.
Paper 4: Deuring for the People: Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková, Mattia Veroni. Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic.
Paper 5: Wissam Ghantous, Federico Pintore, Veroni, Mattia Efficiency of SIDH-based signatures (yes,SIDH)