University of Waterloo
The Number Field Sieve for Barreto-Naehrig Curves: Smoothness of Norms
Abstract
dc:description.abstractThe 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 × 4Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/9372