Back to search

University of Waterloo

On the Complexity of the Circuit Obfuscation Problem for Split Manufacturing

Abstract

dc:description.abstract

Recent 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

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

El Massad, Mohamed. On the Complexity of the Circuit Obfuscation Problem for Split Manufacturing. University of Waterloo, 2014. http://hdl.handle.net/10012/8335