Solving discrete logarithms on a 170-bit MNT curve by pairing reduction

DOI10.1007/978-3-319-69453-5_30zbMATH Open1418.11159arXiv1605.07746OpenAlexW2963925737MaRDI QIDQ1698673FDOQ1698673

Authors: Aurore Guillevic, François Morain, Emmanuel Thomé 

Publication date: 16 February 2018

Abstract: Pairing based cryptography is in a dangerous position following the breakthroughs on discrete logarithms computations in finite fields of small characteristic. Remaining instances are built over finite fields of large characteristic and their security relies on the fact that the embedding field of the underlying curve is relatively large. How large is debatable. The aim of our work is to sustain the claim that the combination of degree 3 embedding and too small finite fields obviously does not provide enough security. As a computational example, we solve the DLP on a 170-bit MNT curve, by exploiting the pairing embedding to a 508-bit, degree-3 extension of the base field.

Full work available at URL: https://arxiv.org/abs/1605.07746

Recommendations

• Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in \({\mathbb F}_{2^{4 \cdot 1223}}\) and \({\mathbb F}_{2^{12 \cdot 367}}\))
• Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields
• Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography
• The Special Number Field Sieve in $\mathbb{F}_{p^{n}}$
• Cryptanalysis of pairing-based cryptosystems over small characteristic fields

zbMATH Keywords

discrete logarithmfinite fieldnumber field sieveMNT elliptic curve

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50)

Cites Work

• A taxonomy of pairing-friendly elliptic curves
• Title not available (Why is that?)
• Title not available (Why is that?)
• Breaking Pairing-Based Cryptosystems Using η T Pairing over GF(397)
• A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Pairing-Friendly Elliptic Curves of Prime Order
• Title not available (Why is that?)
• New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields
• Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
• Advances in Elliptic Curve Cryptography
• Reducing elliptic curve logarithms to logarithms in a finite field
• Bounds for resultants of univariate and bivariate polynomials
• Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in \({\mathbb F}_{2^{4 \cdot 1223}}\) and \({\mathbb F}_{2^{12 \cdot 367}}\))
• HT90 and ``simplest number fields
• Elliptic curves suitable for pairing based cryptography
• Title not available (Why is that?)
• An Implementation of the Number Field Sieve
• A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
• Algorithmic Number Theory
• Title not available (Why is that?)
• Function field sieve method for discrete logarithms over finite fields
• Building curves with arbitrary small MOV degree over finite prime fields
• Extended tower number field sieve: a new complexity for the medium prime case
• The Number Field Sieve in the Medium Prime Case
• Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve
• Discrete logarithms and local units
• Ordinary Abelian varieties having small embedding degree
• The tower number field sieve
• Computing individual discrete logarithms faster in \(\mathrm{GF}(p^n)\) with the NFS-DL algorithm
• Nearly sparse linear algebra and application to discrete logarithms computations
• Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
• A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm
• Collecting relations for the number field sieve in \(\text{GF}(p^6)\)
• Algorithms and Arithmetic Operators for Computing the ηT Pairing in Characteristic Three
• Virtual logarithms
• Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
• The Special Number Field Sieve in $\mathbb{F}_{p^{n}}$
• Public Key Cryptography - PKC 2006

Cited In (9)

• Secure and Efficient Pairing at 256-Bit Security Level
• Solving a Discrete Logarithm Problem with Auxiliary Input on a 160-Bit Elliptic Curve
• Updating key size estimations for pairings
• Solving 114-bit ECDLP for a Barreto-Naehrig curve
• Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
• Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
• Pairing inversion for finding discrete logarithms
• On the Minimal Embedding Field
• Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in \({\mathbb F}_{2^{4 \cdot 1223}}\) and \({\mathbb F}_{2^{12 \cdot 367}}\))

This page was built for publication: Solving discrete logarithms on a 170-bit MNT curve by pairing reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698673)