University of Waterloo
On the Complexity of the Circuit Obfuscation Problem for Split Manufacturing
Abstract
dc:description.abstractRecent work in the area of computer hardware security introduced a number of interesting computational problems in the context of directed acyclic graphs (DAGs). In this thesis, we pick one of these problems, circuit obfuscation --- a combinatorial optimization problem --- and study its computational complexity. First, we prove that the problem is \cnph. Next, we show it to be in the class of MAX-SNP optimization problems, which means it is inapproximable within a certain constant (2.08) unless P=NP. We then use a reduction from the maximum common edge subgraph problem to prove a lower bound on the absolute error guarantee achievable for the problem by a polynomial-time algorithm. Given that the decision version of the problem is in NP, we investigate the possibility of efficiently solving the problem using a SAT solver and report on our results. Finally, we study a slightly modified version of the problem underlying a generalized hardware security technique and prove it to be NP-hard as well.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2014
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- El Massad, Mohamed
Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/8335