Breaking `128-bit secure' supersingular binary curves. (Or how to solve discrete logarithms in F₂^4 1223 and F₂^12 367)

DOI10.1007/978-3-662-44381-1_8MaRDI QIDQ2874534zbMATH OpenOpenAlexFDO

Authors Robert Granger, Thorsten Kleinjung, Jens Zumbrägel

Publication date 7 August 2014

Published in Advances in Cryptology – CRYPTO 2014 (Search for Journal in Brave)

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

zbMATH Keywords

discrete logarithm problemfinite fieldspairingssupersingular binary curves

Mathematics Subject Classification ID

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

Abstract: In late 2012 and early 2013 the discrete logarithm problem (DLP) in finite fields of small characteristic underwent a dramatic series of breakthroughs, culminating in a heuristic quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thom'e. Using these developments, Adj, Menezes, Oliveira and Rodr'iguez-Henr'iquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature, which were originally thought to be $128$-bit secure. In particular, they suggested that the new algorithms have no impact on the security of a genus one curve over ${mathbbF}_{2^{1223}}$, and reduce the security of a genus two curve over ${mathbbF}_{2^{367}}$ to $94.6$ bits. In this paper we propose a new field representation and efficient general descent principles which together make the new techniques far more practical. Indeed, at the `128-bit security level' our analysis shows that the aforementioned genus one curve has approximately $59$ bits of security, and we report a total break of the genus two curve.

Recommendations

• Weakness of $\mathbb{F}_{3^{6 \cdot 509}}$ for Discrete Logarithm Cryptography
• Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography
• Solving discrete logarithms on a 170-bit MNT curve by pairing reduction
• scientific article; zbMATH DE number 2081083
• Solving a 6120 -bit DLP on a Desktop Computer

Cited in

(27)

• Smoothness test for polynomials defined over small characteristic finite fields
• Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
• Solving discrete logarithms on a 170-bit MNT curve by pairing reduction
• Computing discrete logarithms in \(\mathbb F_{p^6}\)
• Indiscreet logarithms in finite fields of small characteristic
• Updating key size estimations for pairings
• Almost perfect nonlinear trinomials and hexanomials
• Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields
• New discrete logarithm computation for the medium prime case using the function field sieve
• Faster initial splitting for small characteristic composite extension degree fields
• Structure-preserving public-key encryption with leakage-resilient CCA security
• Still wrong use of pairings in cryptography
• Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression
• Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography
• Efficient distributed tag-based encryption and its application to group signatures with efficient distributed traceability
• On constructing parameterized families of pairing-friendly elliptic curves with =1
• Classifying and generating exact coset representatives of \(\operatorname{PGL}_2(\mathbb{F}_q)\) in \(\operatorname{PGL}_2(\mathbb{F}_{q^2})\)
• Indiscreet discrete logarithms
• On the discrete logarithm problem in finite fields of fixed characteristic
• Faster individual discrete logarithms in finite fields of composite extension degree
• Computation of a 30750-bit binary field discrete logarithm
• Structure-Preserving Chosen-Ciphertext Security with Shorter Verifiable Ciphertexts
• A survey of elliptic curves for proof systems
• Individual discrete logarithm with sublattice reduction
• Roots of certain polynomials over finite fields
• On the alpha value of polynomials in the tower number field sieve algorithm
• Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity

This page was built for publication: 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}}\))

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