Visible to the public On the Impossibility of Approximation-Resilient Circuit Locking

TitleOn the Impossibility of Approximation-Resilient Circuit Locking
Publication TypeConference Paper
Year of Publication2019
AuthorsShamsi, Kaveh, Pan, David Z., Jin, Yier
Conference Name2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)
Date PublishedMay 2019
ISBN Number 978-1-5386-8064-3
KeywordsAdversary Models, algorithmic attacks, approximation-resiliency, approximation-resilient Circuit locking, benchmark circuits, boolean circuits, Boolean functions, cL, Computational modeling, cryptography, digital signatures, exact-recovery-resiliency, exponentially approximation-resilient, formal approach, formally defined notions, Foundries, IC, Integrated Circuit Camouflaging, Integrated circuit modeling, learning (artificial intelligence), logic locking, long-standing hardness assumptions, malicious foundry, microscopy, original circuit, pubcrawl, relaxed notion, resilience, Resiliency, Scalability, security guarantees, signature based defense

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.

Citation Keyshamsi_impossibility_2019