Candidate
Mohamed El Massad
Title
On the Complexity of the Circuit Obfuscation Problem
Supervisors
Tripunitara, Mahesh and Garg, Siddharth
Abstract
Recent work in the area of computer hardware security introduced a number of interesting computational problems in the context of graphs, which are objects of study in discrete mathematics that are used to model pairwise relations between objects. One of these problems, a combinatorial optimization problem, asks for the minimum number of wires that can be removed from an integrated circuit to make the gates in the circuit sufficiently secure; according to a specific notion of security that involves the indistinguishability of some gates in the circuit from each other. The problem is known as circuit obfuscation and the notion of security is shown by previous work to correspond to a kind of subgraph isomorphism - a well-known problem in theoretical computer science. Although previous work introduced the problem, it left some questions open regarding its computability properties and whether methods exist that can be used to solve it efficiently. In this seminar, I will present some results I was able to obtain regarding the computational complexity of the problem, including its computational intractability as well as its inapproximability within certain factors. I also report on the results of some attempts to develop an efficient solver for the problem using a class of algorithms known as SAT solvers. In addition, I show how a modified version of the problem underlying a generalized hardware security technique is also very likely to be computationally intractable, which necessitates the use of non-exact approaches for solving it as well.