**The Application of Polynomials over the Field of Two Elements to a Problem in Intellectual Property**

*Gregory V. Bard*

**Abstract: **It is a routine task to convert a digital circuit to a system
of polynomial equations over GF(2). A very well-studied set
of tools called ``SAT-solvers'', which solve Conjunctive Normal
Form logical satisfiability problems, can be used to determine
if two circuits are equivalent, as is commonly done in
computer engineering. An interesting problem in intellectual
property is to determine if two circuits are identical but
subject to an unknown permutation of the inputs and outputs.
This could be of interest if a manufacturer suspects his
encryption circuit has been stolen. While this is easily shown
to be a sub-problem of the famously hard “isomorphism of
polynomials” problem, we show that in fact it can be easily
solved via conversion to a polynomial system of equations over
GF(2), and is only slightly harder than if the permutations
were in fact known.

**Category / Keywords: **implementation / Intellectual Property, Isomorphism of Polynomials, SAT-Solvers, Circuit Equivalence, Polynomial System of Equations

**Publication Info: **to be submitted soon to a journal.

**Date: **received 2 Jul 2009, last revised 18 Aug 2009

**Contact author: **bard at fordham edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20090819:021516 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]