Construction and applications of elliptic curves with small embedding degree

Abstract

Pairing-based cryptography relies on a bilinear map, called a pairing, defined from groups of elliptic curves over finite fields to the multiplicative group of a finite field extension. To ensure that such pairings are both efficient and secure, the embedding degree, which determines the degree of the extension, must be chosen with care. The main emphasis of this work is the theory of complex multiplication, which provides a way to construct elliptic curves over finite fields with a prescribed number of rational points. We also explain how pairings are defined and how they can be applied in the design of cryptographic schemes. We present algorithms based on the complex multiplication method that construct elliptic curves suitable for pairing-based cryptography. 1

Kryptografie založena na párování využívá bilineární zobrazení, zvané párování, definované z grup eliptických křivek nad konečnými tělesy do multiplikativní grupy rozšíření konečného tělesa. Aby bylo párování efektivní a zároveň bezpečné, je nutné pečlivě zvolit stupeň vnoření, který určuje stupeň tělesového rozšíření. Hlavním tématem práce je teorie komplexní multiplikace, která umožňuje kon- struovat eliptické křivky nad konečnými tělesy s předepsaným počtem bodů. Také vysvětlujeme, jak je párování definováno a jak se používá pro budování kryptosys- témů. Popisujeme algoritmy, které využívají metodu komplexní multiplikace pro konstrukci křivek vhodných k párování. 1