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

From Interaction to Independence: zkSNARKs for Transparent and Non-Interactive...

Shahriar Ebrahimi (IDEAS-NCBR), Parisa Hassanizadeh (IDEAS-NCBR)

Read More

Leaking the Privacy of Groups and More: Understanding Privacy...

Jiangrong Wu (Sun Yat-sen University), Yuhong Nan (Sun Yat-sen University), Luyi Xing (Indiana University Bloomington), Jiatao Cheng (Sun Yat-sen University), Zimin Lin (Alibaba Group), Zibin Zheng (Sun Yat-sen University), Min Yang (Fudan University)

Read More

SOCs lead AI adoption: Transitioning Lessons to the C-Suite

Eric Dull, Drew Walsh, Scott Riede (Deloitte and Touche)

Read More

Merge/Space: A Security Testbed for Satellite Systems

M. Patrick Collins (USC Information Sciences Institute), Alefiya Hussain (USC Information Sciences Institute), J.P. Walters (USC Information Sciences Institute), Calvin Ardi (USC Information Sciences Institute), Chris Tran (USC Information Sciences Institute), Stephen Schwab (USC Information Sciences Institute)

Read More