A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic

DOI10.1007/978-3-642-55220-5_1zbMath1326.11080OpenAlexW1758781646WikidataQ56041342 ScholiaQ56041342MaRDI QIDQ5418686

Antoine Joux, Pierrick Gaudry, Razvan Barbulescu, Emmanuel Thomé

Publication date: 27 May 2014

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

Full work available at URL: https://hal.inria.fr/hal-00835446/file/article.pdf

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (61)

Effective compression maps for torus-based cryptography ⋮ Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields ⋮ Implicit Zero-Knowledge Arguments and Applications to the Malicious Setting ⋮ Classifying and generating exact coset representatives of \(\operatorname{PGL}_2(\mathbb{F}_q)\) in \(\operatorname{PGL}_2(\mathbb{F}_{q^2})\) ⋮ New discrete logarithm computation for the medium prime case using the function field sieve ⋮ Factor base discrete logarithms in Kummer extensions ⋮ Computational Number Theory and Cryptography ⋮ Jacobian coordinates on genus 2 curves ⋮ Generating sets for the multiplicative groups of algebras over finite fields and expander graphs ⋮ Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression ⋮ Subgroup Security in Pairing-Based Cryptography ⋮ Efficient Distributed Tag-Based Encryption and Its Application to Group Signatures with Efficient Distributed Traceability ⋮ Failure of the Point Blinding Countermeasure Against Fault Attack in Pairing-Based Cryptography ⋮ Field extensions and index calculus on algebraic curves ⋮ A survey of elliptic curves for proof systems ⋮ Individual discrete logarithm with sublattice reduction ⋮ Quasi-subfield polynomials and the elliptic curve discrete logarithm problem ⋮ Index calculus in the trace zero variety ⋮ LRPC codes with multiple syndromes: near ideal-size KEMs without ideals ⋮ A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm ⋮ Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation ⋮ Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation ⋮ Solving discrete logarithms on a 170-bit MNT curve by pairing reduction ⋮ On the discrete logarithm problem in finite fields of fixed characteristic ⋮ Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity ⋮ Collecting relations for the number field sieve in ⋮ Decentralized multi-authority ABE for \(\mathsf{NC}^1\) from BDH ⋮ Adaptively simulation-secure attribute-hiding predicate encryption ⋮ Faster individual discrete logarithms in finite fields of composite extension degree ⋮ On the Selection of Polynomials for the DLP Quasi-Polynomial Time Algorithm for Finite Fields of Small Characteristic ⋮ Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions ⋮ ON BOUNDS FOR BALANCED EMBEDDING DEGREE ⋮ HYPERELLIPTIC CURVES, CARTIER — MANIN MATRICES AND LEGENDRE POLYNOMIALS ⋮ Choosing and generating parameters for pairing implementation on BN curves ⋮ Computing discrete logarithms in \(\mathbb F_{p^6}\) ⋮ Rigorous analysis of a randomised number field sieve ⋮ Polynomial time bounded distance decoding near Minkowski's bound in discrete logarithm lattices ⋮ Structure-Preserving Chosen-Ciphertext Security with Shorter Verifiable Ciphertexts ⋮ Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree ⋮ Short Generators Without Quantum Computers: The Case of Multiquadratics ⋮ Updating key size estimations for pairings ⋮ Indiscreet logarithms in finite fields of small characteristic ⋮ Converting pairing-based cryptosystems from composite to prime order setting -- a comparative analysis ⋮ Cryptographic Assumptions: A Position Paper ⋮ Lattice sieving in three dimensions for discrete log in medium characteristic ⋮ Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography ⋮ Computation of a 30750-bit binary field discrete logarithm ⋮ Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules ⋮ Faster initial splitting for small characteristic composite extension degree fields ⋮ Refined analysis to the extended tower number field sieve ⋮ Design in Type-I, Run in Type-III: Fast and Scalable Bilinear-Type Conversion Using Integer Programming ⋮ Koblitz curves over quadratic fields ⋮ Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case ⋮ A probabilistic analysis on a lattice attack against DSA ⋮ Selecting polynomials for the Function Field Sieve ⋮ Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields ⋮ Point compression for the trace zero subgroup over a small degree extension field ⋮ Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic ⋮ A Brief History of Pairings ⋮ On Sets of Irreducible Polynomials Closed by Composition ⋮ The multiple number field sieve for medium- and high-characteristic finite fields

This page was built for publication: A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic