Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. to be submitted soon to a journal.
Keywords
Intellectual PropertyIsomorphism of PolynomialsSAT-SolversCircuit EquivalencePolynomial System of Equations
Contact author(s)
bard @ fordham edu
History
2009-08-19: revised
2009-07-07: received
See all versions
Short URL
https://ia.cr/2009/326
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/326,
      author = {Gregory V.  Bard},
      title = {The Application of Polynomials over the Field of Two Elements to a Problem in Intellectual Property},
      howpublished = {Cryptology ePrint Archive, Paper 2009/326},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/326}},
      url = {https://eprint.iacr.org/2009/326}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.