A combinatorial problem related to sparse systems of equations

DOI10.1007/S10623-016-0294-4MaRDI QIDQ2402975zbMATH OpenOpenAlexFDO

Authors Zsolt Tuza, Peter Horák, Igor Semaev

Publication date 15 September 2017

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

Full work available at URL https://arxiv.org/abs/1512.00943, http://real.mtak.hu/44139/1/1512.00943.pdf

zbMATH Keywords

gluing algorithmMaxMinMax problemsparse systems of equations

Mathematics Subject Classification ID

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

Abstract: Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems. It turns out that a combinatorial MaxMinMax problem provides bounds on the average computational complexity of sparse systems. In this paper we initiate a study of a linear algebra variation of this MaxMinMax problem.

Recommendations

• An application of combinatorics in cryptography
• Sparse algebraic equations over finite fields
• Improved agreeing-gluing algorithm
• On solving sparse algebraic equations over finite fields
• MaxMinMax problem and sparse equations over finite fields

Cites work

• scientific article; zbMATH DE number 5604103 (Why is no real title available?)
• A new method to solve MRHS equation systems and its connection to group factorization
• Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
• Improved agreeing-gluing algorithm
• MRHS Equation Systems
• MaxMinMax problem and sparse equations over finite fields
• On solving sparse algebraic equations over finite fields
• Solving multiple right hand sides linear equations
• Speeding up deciphering by hypergraph ordering

Cited in

(4)

• MaxMinMax problem and sparse equations over finite fields
• On solving sparse algebraic equations over finite fields
• An application of combinatorics in cryptography
• Sparse algebraic equations over finite fields

This page was built for publication: A combinatorial problem related to sparse systems of equations

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