Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case

DOI10.1007/978-3-662-53018-4_20zbMath1384.94075OpenAlexW2406585997MaRDI QIDQ2835600

Taechan Kim, Razvan Barbulescu

Publication date: 30 November 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-662-53018-4_20

zbMATH Keywords

finite fieldsdiscrete logarithm problemcryptanalysisnumber field sieve

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Related Items (43)

Fast, Compact, and Expressive Attribute-Based Encryption ⋮ Trapdoor DDH groups from pairings and isogenies ⋮ Efficient hash maps to \(\mathbb{G}_2\) on BLS curves ⋮ Generating pairing-friendly elliptic curve parameters using sparse families ⋮ LOVE a pairing ⋮ Improved threshold signatures, proactive secret sharing, and input certification from LSS isomorphisms ⋮ A classification of ECM-friendly families of elliptic curves using modular curves ⋮ Families of SNARK-friendly 2-chains of elliptic curves ⋮ Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation ⋮ A survey of elliptic curves for proof systems ⋮ Individual discrete logarithm with sublattice reduction ⋮ DiSSECT: distinguisher of standard and simulated elliptic curves via traits ⋮ A General Polynomial Selection Method and New Asymptotic Complexities for the Tower Number Field Sieve Algorithm ⋮ Fast hashing to \(\mathbb{G}_2\) on pairing-friendly curves with the lack of twists ⋮ Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation ⋮ Higher-dimensional sieving for the number field sieve algorithms ⋮ Finite field arithmetic in large characteristic for classical and post-quantum cryptography ⋮ 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 ⋮ Adaptively secure non-interactive CCA-secure threshold cryptosystems: generic framework and constructions ⋮ Faster individual discrete logarithms in finite fields of composite extension degree ⋮ An Improvement of Optimal Ate Pairing on KSS Curve with Pseudo 12-Sparse Multiplication ⋮ Improving the efficiency of re-randomizable and replayable CCA secure public key encryption ⋮ Fast, compact, and expressive attribute-based encryption ⋮ ON BOUNDS FOR BALANCED EMBEDDING DEGREE ⋮ An efficient attribute-based access control system with break-glass capability for cloud-assisted industrial control system ⋮ Choosing and generating parameters for pairing implementation on BN curves ⋮ Computing discrete logarithms in \(\mathbb F_{p^6}\) ⋮ Compact structure-preserving signatures with almost tight security ⋮ 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 ⋮ Bloom filter encryption and applications to efficient forward-secret 0-RTT key exchange ⋮ Converting pairing-based cryptosystems from composite to prime order setting -- a comparative analysis ⋮ Lattice sieving in three dimensions for discrete log in medium characteristic ⋮ Refined analysis to the extended tower number field sieve ⋮ A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level ⋮ Hardware implementation of multiplication over quartic extension fields ⋮ TNFS resistant families of pairing-friendly elliptic curves ⋮ New constructions of hinting PRGs, OWFs with encryption, and more ⋮ Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields ⋮ A Brief History of Pairings

Cites Work

• Unnamed Item
• Bounds for resultants of univariate and bivariate polynomials
• Factoring integers with elliptic curves
• A taxonomy of pairing-friendly elliptic curves
• The Tower Number Field Sieve
• A Homomorphic LWE Based E-voting Scheme
• New Complexity Trade-Offs for the (Multiple) Number Field Sieve Algorithm in Non-Prime Fields
• The multiple number field sieve for medium- and high-characteristic finite fields
• Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields
• The Multiple Number Field Sieve with Conjugation and Generalized Joux-Lercier Methods
• High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves
• Solving sparse linear equations over finite fields
• Discrete logarithms and local units
• Implementing Pairings at the 192-Bit Security Level
• Using number fields to compute logarithms in finite fields
• Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
• A Kilobit Special Number Field Sieve Factorization
• A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
• Pairing-Friendly Elliptic Curves of Prime Order
• The Special Number Field Sieve in $\mathbb{F}_{p^{n}}$
• The Number Field Sieve in the Medium Prime Case
• Public Key Cryptography - PKC 2006
• Algorithmic Number Theory

This page was built for publication: Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case