Most isogeny-based cryptosystems ultimately rely, for their security, on ℓ- IsoPath, i.e. the problem of finding a secret ℓ-smooth isogeny between two elliptic curves. As cryptographic applications usually employ weaker variants of ℓ-IsoPath for practical reasons, it is natural to ask whether these variants are equally hard from a computational perspective. For example, what happens if the endomorphism ring of one of the curves is known? Does the existence of suitable pairings affect the hardness of ℓ-IsoPath? What happens if some non-trivial endomorphisms of the domain and codomain curves are known? These kinds of questions lead to different problems, some of which are considered throughout this thesis. To prevent anyone from knowing the endomorphism ring of a supersingular elliptic curve, we would need a method to hash in the supersingular isogeny graph, i.e. the graph whose vertices are supersingular elliptic curves (up to isomorphism) and whose edges are isogenies of fixed degree. We give examples of cryptographic protocols that could benefit from this and survey some known methods. Since none of them is at the same time efficient and cryptographically secure, we also point out a few alternative approaches. Later on, we leverage the classic Deuring correspondence between supersingular elliptic curves and quaternion orders to study a weaker version of ℓ-IsoPath, inspired by the study of CM theory from the previous part. We then focus on the construction of pairings of elliptic curves, showing that, in the general case, finding distinct pairings compatible with a secret isogeny is no easier than retrieving the isogeny itself. In the presence of an orientation, on the other hand, we show that the existence of suitable self-pairings, together with a recent attack on the isogeny-based key-exchange SIDH, does lead to efficiently solving ℓ- IsoPath for some class-group-action-based protocols. In particular, we completely characterize the cases in which these selfpairings exist. Finally, we introduce a different graph of elliptic curves, which has not been considered before in isogeny-based cryptography and which does not arise, in fact, from isogenies: the Hessian graph. We give a (still partial) account of its remarkable regularity and discuss potential cryptographic applications.

Graphs and pairings of elliptic curves / Mula, Marzio. - (2024 Feb 22), pp. 1-116. [10.15168/11572_402478]

Graphs and pairings of elliptic curves

Mula, Marzio
2024-02-22

Abstract

Most isogeny-based cryptosystems ultimately rely, for their security, on ℓ- IsoPath, i.e. the problem of finding a secret ℓ-smooth isogeny between two elliptic curves. As cryptographic applications usually employ weaker variants of ℓ-IsoPath for practical reasons, it is natural to ask whether these variants are equally hard from a computational perspective. For example, what happens if the endomorphism ring of one of the curves is known? Does the existence of suitable pairings affect the hardness of ℓ-IsoPath? What happens if some non-trivial endomorphisms of the domain and codomain curves are known? These kinds of questions lead to different problems, some of which are considered throughout this thesis. To prevent anyone from knowing the endomorphism ring of a supersingular elliptic curve, we would need a method to hash in the supersingular isogeny graph, i.e. the graph whose vertices are supersingular elliptic curves (up to isomorphism) and whose edges are isogenies of fixed degree. We give examples of cryptographic protocols that could benefit from this and survey some known methods. Since none of them is at the same time efficient and cryptographically secure, we also point out a few alternative approaches. Later on, we leverage the classic Deuring correspondence between supersingular elliptic curves and quaternion orders to study a weaker version of ℓ-IsoPath, inspired by the study of CM theory from the previous part. We then focus on the construction of pairings of elliptic curves, showing that, in the general case, finding distinct pairings compatible with a secret isogeny is no easier than retrieving the isogeny itself. In the presence of an orientation, on the other hand, we show that the existence of suitable self-pairings, together with a recent attack on the isogeny-based key-exchange SIDH, does lead to efficiently solving ℓ- IsoPath for some class-group-action-based protocols. In particular, we completely characterize the cases in which these selfpairings exist. Finally, we introduce a different graph of elliptic curves, which has not been considered before in isogeny-based cryptography and which does not arise, in fact, from isogenies: the Hessian graph. We give a (still partial) account of its remarkable regularity and discuss potential cryptographic applications.
22-feb-2024
XXXVI
2023-2024
Matematica (29/10/12-)
Mathematics
Murru, Nadir
Pintore, Federico
no
Inglese
Settore MAT/02 - Algebra
File in questo prodotto:
File Dimensione Formato  
PhDThesisSubmitted_14-02-24.pdf

accesso aperto

Descrizione: Graphs and pairings of elliptic curves
Tipologia: Tesi di dottorato (Doctoral Thesis)
Licenza: Altra licenza (Other type of license)
Dimensione 1.36 MB
Formato Adobe PDF
1.36 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/402478
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact