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
-
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},
url = {https://eprint.iacr.org/2009/326}
}
