Structural transformation for best-possible obfuscation of sequential circuits

Obfuscation is a technique that makes comprehending a design difficult and hides the secrets in the design. An obfuscation is called best-possible if the obfuscated design leaks no more information than any other design of the same function. In this paper, we prove that any best-possible obfuscation of a sequential circuit can be accomplished by a sequence of four operations: retiming, resynthesis, sweep, and conditional stuttering. Based on this fundamental result, we also develop a key-based obfuscation scheme to protect design Intellectual Properties (IPs) against piracy. The novel obfuscation method embeds a secret key in the power-up state of IC, which is only known by the IP rights owner. Without the key, the IC still functions but its efficiency will be much degraded. Unlike existing IC metering techniques, the secret key in our approach is implicit thus it can also be used as a hidden watermark. Potential attacks and the countermeasures are thoroughly examined, and experimental results demonstrate the effectiveness of the method.