Speeding up deciphering by hypergraph ordering

DOI10.1007/S10623-013-9899-ZMaRDI QIDQ2339143zbMATH OpenOpenAlexFDO

Authors Zsolt Tuza, Peter Horák

Publication date 30 March 2015

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5292, http://real.mtak.hu/33639/1/1309.5292v1.pdf

zbMATH Keywords

hypergraph orderingsparse systems of Boolean equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Hypergraphs (05C65)

Abstract: The "Gluing Algorithm" of Semaev [Des. Codes Cryptogr. 49 (2008), 47--60] --- that finds all solutions of a sparse system of linear equations over the Galois field $GF(q)$ --- has average running time $O(m{q}^{maxleftvertcu{p}_1^k{X}_{j}ightvert-k}),$ where $m$ is the total number of equations, and $cu{p}_1^k{X}_j$ is the set of all unknowns actively occurring in the first $k$ equations. Our goal here is to minimize the exponent of $q$ in the case where every equation contains at most three unknowns. %Applying hypergraph-theoretic methods we prove The main result states that if the total number $leftvertcu{p}_1^m{X}_{j}ightvert$ of unknowns is equal to $m$, then the best achievable exponent is between $c_{1}m$ and $c_{2}m$ for some positive constants $c_1$ and $c_2.$

Recommendations

• Improved agreeing-gluing algorithm
• Sparse algebraic equations over finite fields
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• On the complexity of solving quadratic Boolean systems
• scientific article; zbMATH DE number 503245

Cites work

• scientific article; zbMATH DE number 3852305 (Why is no real title available?)
• scientific article; zbMATH DE number 1953444 (Why is no real title available?)
• Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
• MaxMinMax problem and sparse equations over finite fields
• On solving sparse algebraic equations over finite fields
• On the complexity of solving quadratic Boolean systems
• Sparse matrices

Cited in

(4)

• MaxMinMax problem and sparse equations over finite fields
• An application of combinatorics in cryptography
• Improved agreeing-gluing algorithm
• A combinatorial problem related to sparse systems of equations

This page was built for publication: Speeding up deciphering by hypergraph ordering

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