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

DOI10.1007/978-3-319-69453-5_30MaRDI QIDQ1698673zbMATH OpenOpenAlexFDO

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

Publication date 16 February 2018

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

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)

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.

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

Cites work

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

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)