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

Detecting Voice Cloning Attacks via Timbre Watermarking

Chang Liu (University of Science and Technology of China), Jie Zhang (Nanyang Technological University), Tianwei Zhang (Nanyang Technological University), Xi Yang (University of Science and Technology of China), Weiming Zhang (University of Science and Technology of China), NengHai Yu (University of Science and Technology of China)

Read More

GNNIC: Finding Long-Lost Sibling Functions with Abstract Similarity

Qiushi Wu (University of Minnesota), Zhongshu Gu (IBM Research), Hani Jamjoom (IBM Research), Kangjie Lu (University of Minnesota)

Read More

Towards Precise Reporting of Cryptographic Misuses

Yikang Chen (The Chinese University of Hong Kong), Yibo Liu (Arizona State University), Ka Lok Wu (The Chinese University of Hong Kong), Duc V Le (Visa Research), Sze Yiu Chau (The Chinese University of Hong Kong)

Read More

A Comparative Analysis of Difficulty Between Log and Graph-Based...

Matt Jansen, Rakesh Bobba, Dave Nevin (Oregon State University)

Read More