Back to search

University of Waterloo

The Number Field Sieve for Barreto-Naehrig Curves: Smoothness of Norms

Abstract

dc:description.abstract

The security of pairing-based cryptography can be reduced to the difficulty of the discrete logarithm problem (DLP) in finite fields of medium characteristic. The number field sieve is the best known algorithm for this problem. We look at a recent improvement to the number field sieve (NFS) by Joux and Pierrot that applies to finite field DLPs arising from elliptic curves used in pairing-based cryptography. We give specific parameter values for use with Miyaji-Nakabayashi-Takano curves offering 80-bits of security, and Barreto-Naehrig (BN) curves offering 128-bits of security. The running times of the corresponding NFS implementations are compared to the running times arising from prior versions of the NFS, showing that for BN curves the Joux-Pierrot version of the NFS is faster than the conventional version, but that BN curves still provide 128-bits of security. To get a better estimate on the number of relations that can be obtained during the sieving stage, we then analyze the distribution of the sizes of the product of the norms. Using this data, we give some guidelines for choosing which Joux-Pierrot polynomials to use for a specific DLP instance. We attempt to find a model for the distribution in order to further improve on the Joux-Pierrot version of the NFS. Finally, we prove some tighter bounds on the product of the norms.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shantz, Michael

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9372

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shantz, Michael. The Number Field Sieve for Barreto-Naehrig Curves: Smoothness of Norms. University of Waterloo, 2015. http://hdl.handle.net/10012/9372