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

EyeSeeIdentity: Exploring Natural Gaze Behaviour for Implicit User Identification...

L Yasmeen Abdrabou (Lancaster University), Mariam Hassib (Fortiss Research Institute of the Free State of Bavaria), Shuqin Hu (LMU Munich), Ken Pfeuffer (Aarhus University), Mohamed Khamis (University of Glasgow), Andreas Bulling (University of Stuttgart), Florian Alt (University of the Bundeswehr Munich)

Read More

On Precisely Detecting Censorship Circumvention in Real-World Networks

Ryan Wails (Georgetown University, U.S. Naval Research Laboratory), George Arnold Sullivan (University of California, San Diego), Micah Sherr (Georgetown University), Rob Jansen (U.S. Naval Research Laboratory)

Read More

TEE-SHirT: Scalable Leakage-Free Cache Hierarchies for TEEs

Kerem Arikan (Binghamton University), Abraham Farrell (Binghamton University), Williams Zhang Cen (Binghamton University), Jack McMahon (Binghamton University), Barry Williams (Binghamton University), Yu David Liu (Binghamton University), Nael Abu-Ghazaleh (University of California, Riverside), Dmitry Ponomarev (Binghamton University)

Read More

WIP: Savvy: Trustworthy Autonomous Vehicles Architecture

Ali Shoker, Rehana Yasmin, Paulo Esteves-Verissimo (Resilient Computing & Cybersecurity Center (RC3), KAUST)

Read More