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

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