Paper 2020/202

Strong Anti-SAT: Secure and Effective Logic Locking

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


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. ISQED 2020
Logic LockingSAT attack
Contact author(s)
ytliu @ umd edu
2020-02-19: received
Short URL
Creative Commons Attribution


      author = {Yuntao Liu and Michael Zuzak and Yang Xie and Abhishek Chakraborty and Ankur Srivastava},
      title = {Strong Anti-{SAT}: Secure and Effective Logic Locking},
      howpublished = {Cryptology ePrint Archive, Paper 2020/202},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.