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

Facilitating Threat Modeling by Leveraging Large Language Models

Isra Elsharef, Zhen Zeng (University of Wisconsin-Milwaukee), Zhongshu Gu (IBM Research)

Read More

Exploiting Sequence Number Leakage: TCP Hijacking in NAT-Enabled Wi-Fi...

Yuxiang Yang (Tsinghua University), Xuewei Feng (Tsinghua University), Qi Li (Tsinghua University), Kun Sun (George Mason University), Ziqiang Wang (Southeast University), Ke Xu (Tsinghua University)

Read More

o-glassesX: Compiler Provenance Recovery with Attention Mechanism from a...

Yuhei Otsubo (National Police Agency, Tokyo, Japan), Akira Otsuka (Institute of information Security, Japan), Mamoru Mimura (National Defense Academy, Japan), Takeshi Sakaki (The University of Tokyo, Japan), Hiroshi Ukegawa (National Police Agency, Tokyo, Japan)

Read More

Crafter: Facial Feature Crafting against Inversion-based Identity Theft on...

Shiming Wang (Shanghai Jiao Tong University), Zhe Ji (Shanghai Jiao Tong University), Liyao Xiang (Shanghai Jiao Tong University), Hao Zhang (Shanghai Jiao Tong University), Xinbing Wang (Shanghai Jiao Tong University), Chenghu Zhou (Chinese Academy of Sciences), Bo Li (Hong Kong University of Science and Technology)

Read More