Cryptology ePrint Archive: Report 2020/202

Strong Anti-SAT: Secure and Effective Logic Locking

Yuntao Liu and Michael Zuzak and Yang Xie and Abhishek Chakraborty and Ankur Srivastava

Abstract: Logic locking has been proposed as strong protection of intellectual property (IP) against security threats in the IC supply chain especially when the fabrication facility is untrusted. Such techniques use additional locking circuitry to inject incorrect behavior into the digital functionality when the key is incorrect. A family of attacks known as "SAT attacks" provides a strong mathematical formulation to find the correct key of locked circuits. Many conventional SAT-resilient logic locking schemes fail to inject sufficient error into the circuit when the key is incorrect: there are usually very few (or only one) input minterms that cause any error at the circuit output. The state-of-the-art stripped functionality logic locking (SFLL) technique provides a wide spectrum of configurations that introduced a trade-off between security (i.e. SAT attack complexity) and effectiveness (i.e. the amount of error injected by a wrong key). In this work, we prove that such a trade-off is universal among all logic locking techniques. In order to attain high effectiveness of locking without compromising security, we propose a novel secure and effective logic locking scheme, called Strong Anti-SAT (SAS). SAS has the following significant improvements over existing techniques. (1) We prove that SAS's security against SAT attack is not compromised by increases in effectiveness. (2) In contrast to prior work which focused solely on the circuit-level locking impact, we integrate SAS-locked modules into an 80386 processor and show that SAS has a high application-level impact. (3) SAS's hardware overhead is smaller than that of existing techniques.

Category / Keywords: secret-key cryptography / Logic Locking, SAT attack

Original Publication (with minor differences): ISQED 2020

Date: received 17 Feb 2020

Contact author: ytliu at umd edu

Available format(s): PDF | BibTeX Citation

Version: 20200219:163859 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]