Cryptology ePrint Archive: Report 2009/326

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)

Short URL: ia.cr/2009/326

Discussion forum: Show discussion | Start new discussion