A Combinatorial Problem Related to Sparse Systems of Equations

2015/12/03 by Peter Horák, Horak, Peter, Igor Semaev +3
Computer Science · Engineering · #05C65 #68Q25 #94A60 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory

paper · doi:10.48550/arxiv.1512.00943

openalex publication_date 2015/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• A New Approximate Min-Max Theorem with Applications in Cryptography
• Solving Sparse Integer Linear Systems
• Speeding up Deciphering by Hypergraph Ordering
• Optimizing Sparsity over Lattices and Semigroups
• Solving Sparse Linear Systems Faster than Matrix Multiplication