Endomorphism rings in cryptography

G. Bisson

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)Academic

Abstract

Modern communications heavily rely on cryptography to ensure data integrity and privacy. Over the past two decades, very efficient, secure, and featureful cryptographic schemes have been built on top of abelian varieties defined over finite fields. this thesis contributes to several computational aspects of ordinary abelian varieties related to their endomorphism ring structure.This strucure plays a crucial role in the construction of abelian varieties with desirable properties. For instance, pairings have recently enabled many advanced cryptographic primitives; generating abelian varieties endowed with efficient pairings requires selecting suitable endomorphism rings, and we show that more such rings can be used than expected. We also address the inverse problem, that of computing the endomorphism ring of a prescribed abelian variety, which has several applications of its own. Prior state-of-the-art methods could only solve this problem in exponential time, and we design several algorithms of subexponential complexity for solving it in the ordinary case. For elliptic curves, our algorithms are very effective and we demonstrate their practicality by solving large problems that were previously intractable. Additionally, we rigorously bound the complexity of our main algorithm assuming solely the extended Riemann hypothesis. As an alternative to one of our subroutines, we also consider a generalization of the subset sum problem in finite groups, and show how it can be solved using little memory. Finally, we generalize our method to higher-dimensional abelian varieties, for which we rely on further heuristic assumptions. Practically speaking, we develop a library enabling the computation of isogenies between abelian varieties; using this important building block in our main algorithm, we apply our generalized method to compute several illustrative and record examples.
LanguageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • TUE : Department of Mathematics and Computer Science
Supervisors/Advisors
  • Lange, Tanja, Promotor
  • Gaudry, P., Copromotor, External person
Award date14 Jul 2011
Place of PublicationEindhoven
Publisher
Print ISBNs978-90-386-2519-5
DOIs
StatePublished - 2011

Fingerprint

Endomorphism Ring
Abelian Variety
Cryptography
Pairing
Isogenies
Subset Sum Problem
Data Integrity
Riemann hypothesis
Exponential time
Elliptic Curves
Building Blocks
Privacy
Galois field
Inverse Problem
Finite Group
High-dimensional
Heuristics
Ring
Generalise
Computing

Cite this

Bisson, G. (2011). Endomorphism rings in cryptography Eindhoven: Technische Universiteit Eindhoven DOI: 10.6100/IR714676
Bisson, G.. / Endomorphism rings in cryptography. Eindhoven : Technische Universiteit Eindhoven, 2011. 185 p.
@phdthesis{5af38059b8204cdab121d328b57a7380,
title = "Endomorphism rings in cryptography",
abstract = "Modern communications heavily rely on cryptography to ensure data integrity and privacy. Over the past two decades, very efficient, secure, and featureful cryptographic schemes have been built on top of abelian varieties defined over finite fields. this thesis contributes to several computational aspects of ordinary abelian varieties related to their endomorphism ring structure.This strucure plays a crucial role in the construction of abelian varieties with desirable properties. For instance, pairings have recently enabled many advanced cryptographic primitives; generating abelian varieties endowed with efficient pairings requires selecting suitable endomorphism rings, and we show that more such rings can be used than expected. We also address the inverse problem, that of computing the endomorphism ring of a prescribed abelian variety, which has several applications of its own. Prior state-of-the-art methods could only solve this problem in exponential time, and we design several algorithms of subexponential complexity for solving it in the ordinary case. For elliptic curves, our algorithms are very effective and we demonstrate their practicality by solving large problems that were previously intractable. Additionally, we rigorously bound the complexity of our main algorithm assuming solely the extended Riemann hypothesis. As an alternative to one of our subroutines, we also consider a generalization of the subset sum problem in finite groups, and show how it can be solved using little memory. Finally, we generalize our method to higher-dimensional abelian varieties, for which we rely on further heuristic assumptions. Practically speaking, we develop a library enabling the computation of isogenies between abelian varieties; using this important building block in our main algorithm, we apply our generalized method to compute several illustrative and record examples.",
author = "G. Bisson",
year = "2011",
doi = "10.6100/IR714676",
language = "English",
isbn = "978-90-386-2519-5",
publisher = "Technische Universiteit Eindhoven",
school = "TUE : Department of Mathematics and Computer Science",

}

Bisson, G 2011, 'Endomorphism rings in cryptography', Doctor of Philosophy, TUE : Department of Mathematics and Computer Science, Eindhoven. DOI: 10.6100/IR714676

Endomorphism rings in cryptography. / Bisson, G.

Eindhoven : Technische Universiteit Eindhoven, 2011. 185 p.

Research output: ThesisPhd Thesis 1 (Research TU/e / Graduation TU/e)Academic

TY - THES

T1 - Endomorphism rings in cryptography

AU - Bisson,G.

PY - 2011

Y1 - 2011

N2 - Modern communications heavily rely on cryptography to ensure data integrity and privacy. Over the past two decades, very efficient, secure, and featureful cryptographic schemes have been built on top of abelian varieties defined over finite fields. this thesis contributes to several computational aspects of ordinary abelian varieties related to their endomorphism ring structure.This strucure plays a crucial role in the construction of abelian varieties with desirable properties. For instance, pairings have recently enabled many advanced cryptographic primitives; generating abelian varieties endowed with efficient pairings requires selecting suitable endomorphism rings, and we show that more such rings can be used than expected. We also address the inverse problem, that of computing the endomorphism ring of a prescribed abelian variety, which has several applications of its own. Prior state-of-the-art methods could only solve this problem in exponential time, and we design several algorithms of subexponential complexity for solving it in the ordinary case. For elliptic curves, our algorithms are very effective and we demonstrate their practicality by solving large problems that were previously intractable. Additionally, we rigorously bound the complexity of our main algorithm assuming solely the extended Riemann hypothesis. As an alternative to one of our subroutines, we also consider a generalization of the subset sum problem in finite groups, and show how it can be solved using little memory. Finally, we generalize our method to higher-dimensional abelian varieties, for which we rely on further heuristic assumptions. Practically speaking, we develop a library enabling the computation of isogenies between abelian varieties; using this important building block in our main algorithm, we apply our generalized method to compute several illustrative and record examples.

AB - Modern communications heavily rely on cryptography to ensure data integrity and privacy. Over the past two decades, very efficient, secure, and featureful cryptographic schemes have been built on top of abelian varieties defined over finite fields. this thesis contributes to several computational aspects of ordinary abelian varieties related to their endomorphism ring structure.This strucure plays a crucial role in the construction of abelian varieties with desirable properties. For instance, pairings have recently enabled many advanced cryptographic primitives; generating abelian varieties endowed with efficient pairings requires selecting suitable endomorphism rings, and we show that more such rings can be used than expected. We also address the inverse problem, that of computing the endomorphism ring of a prescribed abelian variety, which has several applications of its own. Prior state-of-the-art methods could only solve this problem in exponential time, and we design several algorithms of subexponential complexity for solving it in the ordinary case. For elliptic curves, our algorithms are very effective and we demonstrate their practicality by solving large problems that were previously intractable. Additionally, we rigorously bound the complexity of our main algorithm assuming solely the extended Riemann hypothesis. As an alternative to one of our subroutines, we also consider a generalization of the subset sum problem in finite groups, and show how it can be solved using little memory. Finally, we generalize our method to higher-dimensional abelian varieties, for which we rely on further heuristic assumptions. Practically speaking, we develop a library enabling the computation of isogenies between abelian varieties; using this important building block in our main algorithm, we apply our generalized method to compute several illustrative and record examples.

U2 - 10.6100/IR714676

DO - 10.6100/IR714676

M3 - Phd Thesis 1 (Research TU/e / Graduation TU/e)

SN - 978-90-386-2519-5

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Bisson G. Endomorphism rings in cryptography. Eindhoven: Technische Universiteit Eindhoven, 2011. 185 p. Available from, DOI: 10.6100/IR714676