9 results sorted by ID
Possible spell-corrected query: nfs
A short-list of pairing-friendly curves resistant to the Special TNFS algorithm at the 192-bit security level
Diego F. Aranha, Georgios Fotiadis, Aurore Guillevic
Implementation
For more than two decades, pairings have been a fundamental tool for designing elegant cryptosystems, varying from digital signature schemes to more complex privacy-preserving constructions. However, the advancement of quantum computing threatens to undermine public-key cryptography. Concretely, it is widely accepted that a future large-scale quantum computer would be capable to break any public-key cryptosystem used today, rendering today's public-key cryptography obsolete and mandating the...
Individual Discrete Logarithm with Sublattice Reduction
Haetham AL ASWAD, Cécile PIERROT
Public-key cryptography
The Number Field Sieve and its numerous variants is the best algorithm to compute discrete logarithms in medium and large characteristic finite fields. When the extension degree $n$ is composite and the characteristic~$p$ is of medium size, the Tower variant (TNFS) is asymptotically the most efficient one. Our work deals with the last main step, namely the individual logarithm step, that computes a smooth decomposition of a given target~$T$ in the finite field thanks to two distinct phases:...
Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computation
Gabrielle De Micheli, Pierrick Gaudry, Cécile Pierrot
Public-key cryptography
The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article,...
A short-list of pairing-friendly curves resistant to Special TNFS at the 128-bit security level
Aurore Guillevic
Public-key cryptography
There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve algorithm (TNFS) for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered.
We revisit the Special variant of TNFS...
On the alpha value of polynomials in the tower number field sieve algorithm
Aurore Guillevic, Shashank Singh
Public-key cryptography
In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness...
Optimal TNFS-secure pairings on elliptic curves with composite embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
TNFS Resistant Families of Pairing-Friendly Elliptic Curves
Georgios Fotiadis, Elisavet Konstantinou
Public-key cryptography
Recently there has been a significant progress on the tower number field sieve (TNFS) method, reducing the complexity of the discrete logarithm problem (DLP) in finite field extensions of composite degree. These new variants of the TNFS attacks have a major impact on pairing-based cryptography and particularly on the selection of the underlying elliptic curve groups and extension fields. In this paper we revise the criteria for selecting pairing-friendly elliptic curves considering these new...
Optimal TNFS-secure pairings on elliptic curves with even embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
Tower Number Field Sieve Variant of a Recent Polynomial Selection Method
Palash Sarkar, Shashank Singh
At Asiacrypt 2015, Barbulescu et al. performed a thorough analysis of the tower number field sieve (TNFS) variant of the number
field sieve algorithm. More recently, Kim and Barbulescu combined the TNFS variant with several polynomial selection methods
including the Generalised Joux-Lercier method and the Conjugation method proposed by Barbulescu et al. at Eurocrypt 2015.
Sarkar and Singh (Eurocrypt 2016) proposed
a polynomial selection method which subsumes both the GJL and the Conjugation...
For more than two decades, pairings have been a fundamental tool for designing elegant cryptosystems, varying from digital signature schemes to more complex privacy-preserving constructions. However, the advancement of quantum computing threatens to undermine public-key cryptography. Concretely, it is widely accepted that a future large-scale quantum computer would be capable to break any public-key cryptosystem used today, rendering today's public-key cryptography obsolete and mandating the...
The Number Field Sieve and its numerous variants is the best algorithm to compute discrete logarithms in medium and large characteristic finite fields. When the extension degree $n$ is composite and the characteristic~$p$ is of medium size, the Tower variant (TNFS) is asymptotically the most efficient one. Our work deals with the last main step, namely the individual logarithm step, that computes a smooth decomposition of a given target~$T$ in the finite field thanks to two distinct phases:...
The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article,...
There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve algorithm (TNFS) for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS...
In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness...
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
Recently there has been a significant progress on the tower number field sieve (TNFS) method, reducing the complexity of the discrete logarithm problem (DLP) in finite field extensions of composite degree. These new variants of the TNFS attacks have a major impact on pairing-based cryptography and particularly on the selection of the underlying elliptic curve groups and extension fields. In this paper we revise the criteria for selecting pairing-friendly elliptic curves considering these new...
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
At Asiacrypt 2015, Barbulescu et al. performed a thorough analysis of the tower number field sieve (TNFS) variant of the number field sieve algorithm. More recently, Kim and Barbulescu combined the TNFS variant with several polynomial selection methods including the Generalised Joux-Lercier method and the Conjugation method proposed by Barbulescu et al. at Eurocrypt 2015. Sarkar and Singh (Eurocrypt 2016) proposed a polynomial selection method which subsumes both the GJL and the Conjugation...