Speeding up deciphering by hypergraph ordering

Horák, Péter and Tuza, Zsolt (2015) Speeding up deciphering by hypergraph ordering. DESIGNS CODES AND CRYPTOGRAPHY, 75 (1). pp. 175-185. ISSN 0925-1022

Preview

Text 1309.5292v1.pdf Download (163kB) | Preview

Abstract

The " Gluing Algorithm" of Semaev (Des. Codes Cryptogr. 49:47-60, 2008)-that finds all solutions of a sparse system of linear equations over the Galois field {Mathematical expression}-has average running time {Mathematical expression} where {Mathematical expression} is the total number of equations, and {Mathematical expression} is the set of all unknowns actively occurring in the first {Mathematical expression} equations. In order to make the implementation of the algorithm faster, our goal here is to minimize the exponent of {Mathematical expression} in the case where every equation contains at most three unknowns. The main result states that if the total number {Mathematical expression} of unknowns is equal to {Mathematical expression}, then the best achievable exponent is between {Mathematical expression} and {Mathematical expression} for some positive constants {Mathematical expression} and {Mathematical expression} © 2013 Springer Science+Business Media New York.

Actions (login required)

Edit Item