Fast exhaustive search for polynomial systems in F₂

DOI10.1007/978-3-642-15031-9_14MaRDI QIDQ3583450zbMATH OpenOpenAlexFDO

Authors Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, Bo-Yin Yang

Publication date 17 August 2010

Published in Cryptographic Hardware and Embedded Systems, CHES 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15031-9_14

zbMATH Keywords

exhaustive searchGraphic Processing Units (GPUs)multivariate polynomialsparallelizationsolving systems of equations

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Recommendations

• Fast exhaustive search for quadratic systems in \(\mathbb {F}_2\) on FPGAs
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• On the complexity of solving quadratic Boolean systems
• Implementing Joux-Vitse's crossbred algorithm for solving \(\mathcal M\mathcal Q\) systems over \(\mathbb F_2\) on GPUs
• Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU

Cited in

(29)

• Solving non-linear Boolean equation systems by variable elimination
• The nested subset differential attack. A practical direct attack against LUOV which forges a signature within 210 minutes
• Cryptanalytic applications of the polynomial method for solving multivariate equation systems over \(\mathrm{GF}(2)\)
• Cryptanalysis of the GPRS encryption algorithms GEA-1 and GEA-2
• Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
• The inverse of \(\chi\) and its applications to Rasta-like ciphers
• Preimage attacks on 4-round Keccak by solving multivariate quadratic systems
• Refined cryptanalysis of the GPRS ciphers GEA-1 and GEA-2
• On the efficiency of solving Boolean polynomial systems with the characteristic set method
• Improved agreeing-gluing algorithm
• Efficient public-key operation in multivariate schemes
• Fast exhaustive search for quadratic systems in \(\mathbb {F}_2\) on FPGAs
• An improved algebraic attack on Hamsi-256
• General Fault Attacks on Multivariate Public Key Cryptosystems
• A multivariate based threshold ring signature scheme
• Solving polynomial systems with noise over \(\mathbb{F}_2\): revisited
• An estimator for the hardness of the MQ problem
• Algebraic attacks on Rasta and Dasta using low-degree equations
• New attacks on LowMC instances with a single plaintext/ciphertext pair
• Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields
• A three-stage MITM attack on LowMC from a single plaintext-ciphertext pair
• The regular multivariate quadratic problem
• Improved algebraic attacks on round-reduced LowMC with single-data complexity
• Algorithm 1052: evaluating a Boolean polynomial on all possible inputs
• A hybrid algorithm for the regular syndrome decoding problem
• A simple noncommutative UOV scheme
• New attacks on LowMC using partial sets in the single-data setting
• An analysis of the Crossbred algorithm for the MQ problem
• Low-data cryptanalysis of LowMC instances with full S-box layers

This page was built for publication: Fast exhaustive search for polynomial systems in \({\mathbb{F}_2}\)

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