Solving polynomial systems over finite fields: improved analysis of the hybrid approach

No abstract is available for this paper.

• Publication year

  2012

• Venue

  International Symposium on Symbolic and Algebraic Computation

• Publication date

  2012-07-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2442829.2442843
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields

  2012cited by this paper
• Foreword

  2011cited by this paper
• Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials

  2011cited by this paper
• On the complexity of solving quadratic Boolean systems

  2011influential reference
• Algebraic Cryptanalysis of McEliece Variants with Compact Keys

  2010cited by this paper
• Fast Exhaustive Search for Polynomial Systems in F2

  2010cited by this paper
• A new incremental algorithm for computing Groebner bases

  2010cited by this paper
• Cube Attacks on Tweakable Black Box Polynomials

  2009cited by this paper
• Hybrid approach for solving multivariate systems over finite fields

  2009influential reference
• Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics

  2009cited by this paper
• Gröbner Bases , Coding , and Cryptography ”

  2009cited by this paper
• Cryptanalysis of MinRank

  2008cited by this paper
• Algebraic Cryptanalysis of 58-Round SHA-1

  2007cited by this paper
• Algebraic Cryptanalysis of the Data Encryption Standard

  2007cited by this paper
• Algebraic aspects of the advanced encryption standard

  2006cited by this paper
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal

  2006cited by this paper
• Algebraic Aspects of the Advanced Encryption Standard (Advances in Information Security)

  2006cited by this paper
• Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations

  2005cited by this paper
• Theoretical Analysis of XL over Small Fields

  2004cited by this paper
• Comparison Between XL and Gröbner Basis Algorithms

  2004cited by this paper
• On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations

  2004cited by this paper
• On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis

  2004influential reference
• Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie

  2004cited by this paper
• Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases

  2003cited by this paper
• SFLASHv3, a fast asymmetric signature scheme

  2003cited by this paper
• Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2

  2002cited by this paper
• Cryptanalysis of Block Ciphers with Overdefined Systems of Equations

  2002cited by this paper
• A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)

  2002cited by this paper
• Gröbner bases

  2000cited by this paper
• A new efficient algorithm for computing Gröbner bases (F4)

  1999cited by this paper
• Unbalanced Oil and Vinegar Signature Schemes

  1999cited by this paper
• Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization

  1999cited by this paper
• Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms - Extended Version -

  1996cited by this paper
• Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering

  1993cited by this paper
• Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption

  1988cited by this paper
• An inequality for Hilbert series of graded algebras.

  1985cited by this paper
• Computer algebra: Symbolic and algebraic computation

  1982cited by this paper
• Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems

  year unknowninfluential reference

• BAKSHEESH: Similar Yet Different From GIFT (and ZORRO)

  2026cites this paper
• The rise and resilience of multivariate cryptography: Advances, pitfalls, and promising pathways

  2026cites this paper
• Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher

  2025cites this paper
• Algebraic cryptanalysis of symmetric ciphers: modeling and multistep solving strategies

  2025cites this paper
• Disproving the Linearity of the Polynomials after the Pre-image Substitution in the System of the Third Attempt of MAYO

  2025cites this paper
• Attacking Split-and-Lookup-Based Primitives Using Probabilistic Polynomial System Solving Applications to Round-Reduced Monolith and Full-Round Skyscraper

  2025cites this paper
• Designing homomorphic encryptions with rational functions

  2024cites this paper
• Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$

  2024cites this paper
• Preliminary Cryptanalysis of the Biscuit Signature Scheme

  2024cites this paper
• Algebraic Cryptanalysis of the HADES Design Strategy: Application to Poseidon and Poseidon2

  2024influential citation
• Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials

  2023influential citation
• BAKSHEESH: Similar Yet Different From GIFT

  2023cites this paper
• Algebraic cryptanalysis of POSEIDON

  2023cites this paper
• SMT Solving over Finite Field Arithmetic

  2023cites this paper
• A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium

  2023influential citation
• Separating Oil and Vinegar with a Single Trace

  2023cites this paper
• An improvement of algorithms to solve under-defined systems of multivariate quadratic equations

  2023cites this paper
• Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2

  2023cites this paper
• Gröbner Basis Attack on STARK-Friendly Symmetric-Key Primitives: JARVIS, MiMC and GMiMCerf

  2022cites this paper
• Rubato: Noisy Ciphers for Approximate Homomorphic Encryption (Full Version)

  2022cites this paper
• Key recovery attack on Hufu-UOV

  2022cites this paper
• The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over Fnp Preimage Attack on Full Grendel

  2022cites this paper
• Chaghri - A FHE-friendly Block Cipher

  2022cites this paper
• Transciphering Framework for Approximate Homomorphic Encryption

  2021cites this paper
• The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over (F_p)^n

  2021cites this paper
• Cryptanalysis of LRainbow: The Lifted Rainbow Signature Scheme

  2021cites this paper
• SoK: How (not) to Design and Implement Post-Quantum Cryptography

  2021cites this paper
• Recent Developments in Multivariate Public Key Cryptosystems

  2020cites this paper
• Cryptanalysis of The Lifted Unbalanced Oil Vinegar Signature Scheme

  2020cites this paper
• On the Complexity of Solving Generic Over-determined Bilinear Systems

  2020cites this paper
• Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III

  2020influential citation
• A Comparison of NIST 2nd Round Candidates’ MQ-based Signature Schemes

  2019cites this paper
• Efficient public-key operation in multivariate schemes

  2019cites this paper
• Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017

  2019cites this paper
• Handling Vinegar Variables to Shorten Rainbow Key Pairs

  2019cites this paper
• Feistel Structures for MPC , and More Extended Version

  2019influential citation
• Practical post-quantum cryptography

  2019cites this paper
• Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC

  2019cites this paper
• SOFIA: MQ-based signatures in the QROM

  2018cites this paper
• High-rank attack on HMFEv

  2018cites this paper
• Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017

  2018cites this paper
• Field Lifting for Smaller UOV Public Keys

  2017cites this paper
• Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

  2017cites this paper
• Multivariate Public Key Cryptosystems

  2017cites this paper
• MQ Signatures for PKI

  2017cites this paper
• Key Recovery Attacks on Multivariate Public Key Cryptosystems Derived from Quadratic Forms over an Extension Field

  2017cites this paper
• Security Analysis of Improved Cubic UOV Signature Schemes

  2017cites this paper
• Short Solutions to Nonlinear Systems of Equations

  2017cites this paper
• From 5-Pass MQ -Based Identification to MQ -Based Signatures

  2016influential citation
• Bases de Gröbner en Cryptographie Post-Quantique

  2016cites this paper
• Solving polynomial systems in integers

  2015cites this paper
• Algebraic Cryptanalysis of Deterministic Symmetric Encryption

  2015cites this paper
• Cryptanalysis of multi-HFE

  2015cites this paper
• Solving polynomial systems in integers

  2015cites this paper
• Post-Quantum Cryptography

  2014influential citation
• Cryptanalysis of the Multivariate Signature Scheme Proposed in PQCrypto 2013

  2014cites this paper
• Solving Polynomial Systems over Finite Fields: Algorithms, Implementation and Applications

  2013cites this paper
• From a logical approach to internal states of Hash functions how SAT problem can help to understand SHA-⋆ and MD⋆

  2013cites this paper
• On the complexity of the BKW algorithm on LWE

  2012cites this paper
• On the complexity of solving quadratic Boolean systems

  2011cites this paper