On the Impossibility of Approximation-Resilient Circuit Locking

Logic locking, and Integrated Circuit (IC) Camouflaging, are techniques that try to hide the design of an IC from a malicious foundry or end-user by introducing ambiguity into the netlist of the circuit. While over the past decade an array of such techniques have been proposed, their security has been constantly challenged by algorithmic attacks. This may in part be due to a lack of formally defined notions of security in the first place, and hence a lack of security guarantees based on long-standing hardness assumptions. In this paper we take a formal approach. We define the problem of circuit locking (cL) as transforming an original circuit to a locked one which is ``unintelligable'' without a secret key (this can model camouflaging and split-manufacturing in addition to logic locking). We define several notions of security for cL under different adversary models. Using long standing results from computational learning theory we show the impossibility of exponentially approximation-resilient locking in the presence of an oracle for large classes of Boolean circuits. We then show how exact-recovery-resiliency and a more relaxed notion of security that we coin ``best-possible'' approximation-resiliency can be provably guaranteed with polynomial overhead. Our theoretical analysis directly results in stronger attacks and defenses which we demonstrate through experimental results on benchmark circuits.