Arnau Gàmez-Montolio (City, University of London; Activision Research), Enric Florit (Universitat de Barcelona), Martin Brain (City, University of London), Jacob M. Howe (City, University of London)

Polynomials over fixed-width binary numbers (bytes, Z/2 wZ, bit-vectors, etc.) appear widely in computer science including obfuscation and reverse engineering, program analysis, automated theorem proving, verification, errorcorrecting codes and cryptography. As some fixed-width binary numbers do not have reciprocals, these polynomials behave differently to those normally studied in mathematics. In particular, polynomial equality is harder to determine; polynomials having different coefficients is not sufficient to show they always compute different values. Determining polynomial equality is a fundamental building block for most symbolic algorithms. For larger widths or multivariate polynomials, checking all inputs is computationally infeasible. This paper presents a study of the mathematical structure of null polynomials (those that evaluate to 0 for all inputs) and uses this to develop efficient algorithms to reduce polynomials to a normalized form. Polynomials in such normalized form are equal if and only if their coefficients are equal. This is a key building block for more mathematically sophisticated approaches to a wide range of fundamental problems.

View More Papers

On the Feasibility of CubeSats Application Sandboxing for Space...

Gabriele Marra (CISPA Helmholtz Center for Information Security), Ulysse Planta (CISPA Helmholtz Center for Information Security and Saarbrücken Graduate School of Computer Science), Philipp Wüstenberg (Chair of Space Technology, Technische Universität Berlin), Ali Abbasi (CISPA Helmholtz Center for Information Security)

Read More

LARMix: Latency-Aware Routing in Mix Networks

Mahdi Rahimi (KU Leuven), Piyush Kumar Sharma (KU Leuven), Claudia Diaz (KU Leuven)

Read More

Performance, Correctness, Exceptions: Pick Three

Andrea Gussoni (Politecnico di Milano), Alessandro Di Federico (Politecnico di Milano), Pietro Fezzardi (Politecnico di Milano), Giovanni Agosta (Politecnico di Milano)

Read More

Sharing cyber threat intelligence: Does it really help?

Beomjin Jin (Sungkyunkwan University), Eunsoo Kim (Sungkyunkwan University), Hyunwoo Lee (KENTECH), Elisa Bertino (Purdue University), Doowon Kim (University of Tennessee, Knoxville), Hyoungshick Kim (Sungkyunkwan University)

Read More